22日起金祥路车辆禁行 登云路机动车南往北单行

Question

Two players agree to play chess on an infinite board with no edges. White begins by placing down a bishop, a king, and some finite number of knights of their choosing, in whatever configuration they so choose. Black then places down their king somewhere. Ignoring the 50 move rule, can White always checkmate Black? I suspect not, but cannot prove it.

If White did not have a bishop, then Black can avoid mate forever by placing their king at least two squares to the right of all the White pieces, and then moving to the right each turn. One can check that White's pieces are not fast enough to guard all three squares to the right of Black's king, at best White can catch up with a single knight. With the bishop, this argument breaks down as a bishop and a knight together can easily catch the king and coordinate to prevent a move to the right. The worry is that they can do this often enough to allow the other White pieces to approach or drive the king into some trap. Perhaps the argument can be salvaged by modifying the underlying monovariant to consider vertical motion as well, or by careful tracking of the inefficient moves (bishop moves or knight moves not in the ideal direction) needed to reestablish the blockading positions.

Parity based arguments like running on the opposite color of the bishop are difficult to make work. I think this is because several similar (fairy) endgames are wins:

• If Black promises to only ever move on squares the opposite color of the bishop (So White is trying to checkmate a ferz instead of a king), White can easily catch them by eventually moving their knight adjacent to the king, after which it is trapped.
• If White places 10 or so light squared bishops instead of just one (and at least two knights), then White can always force mate by placing a knight adjacent to the Black king while controlling appropriate light squares. (EDIT: See my answer for evidence that two light squared bishops and enough knights can force checkmate. I would be interested if anyone can get a more understandable method or better bounds on the number of knights required)

These are not great evidence for the single bishop case, as both rely on a knight adjacent to the king being excellent at confining the king.

Answer 1

I have made partial progress on the second part of this question, and now believe two light squared bishops suffice given enough knights. My main piece of evidence for this is the existence of a method by which two light squared bishops and a knight can confine the king to a diamond shaped region of side length 20, while periodically gaining a move to bring other pieces closer. I found this method using a script I wrote. The kNBB_20_3_2.5_23.txt file in the linked repository is a set of 217208 positions with Black to move, encoded as tuples of four coordinates, where the first is the coordinate of the Black king, the second the knight, and the last two the bishops. The claim is that in all of these positions, no matter what Black plays, White has a response that both keeps Black in one of these positions and will eventually allow White to gain a tempo with which to approach with the other knights. One can test the trap against a computer opponent by running play_vs_trap(load_trap("kNBB_20_3_2.5_23.txt"), 22, box_size=21) in trap_tester.py. The opponent is only programmed to eventually avoid repetition, it may allow you to repeat a position many times before it finds an answer which gains a tempo.

While I do not claim to understand every last detail of the trap, the main themes are fairly understandable, and games against fellow humans suggest that it is not too difficult to force and maintain slightly larger versions of the trap (with side length say 30). For the most part, the bishops stay on the green squares, and the knight tracks the king closely, preferring to be on the side of the king closest to the edge. The knight and bishops need to always be in time to catch the king as in the below diagram, but since knights are so much faster than the king and the bishops take at most 4 moves to reposition this tends to be easy. Sometimes near the corners and edges the knight will skirt around the outside of the trap to manage this while getting ahead of the king.

This method of catching the king has a slight problem, which is that the knight interferes with his own bishop. Luckily whenever this is a problem there is a bishop move available which can keep the king controlled and eventually gains a tempo.

Finally, the play near the corner is somewhat delicate, and depending how it is approached seems to need one of several setups from White. One of the more important configurations to know is

[FEN "7K/8/8/8/3k4/3N4/8/3B1B2 b - - 0 1"]

1... Ke3 2. Kg8 Kd2 3. Bfe2 Kc3 4. Kh8 Kc4 5. Ba4

where the knight is well placed to guard most squares near the corner, but White must allow Black to slightly displace the bishops in order to gain tempi.

Given the size of the trap and my current understanding of how it works I suspect that the trap can always be forced. Even if it cannot be, a trap in the same vein but with a larger side length should exist and would allow the knight to track the king even more loosely, meaning eventually one of the traps in this family should work. If this is the case, then some amount of knights will always work (for example, one could simply threaten every square on the perimeter of some box containing the trap, then treat the endgame like KBN v K). If I get more time to work on this I will attempt to find smaller traps and hopefully arguments they are forceable, I actually suspect even two knights could be enough given a king and two light squared bishops.

Answer 2

My friends and I recently revisited this question, and were able to obtain two separate proofs that the checkmate cannot be forced. Both proofs also exclude certain positions with infinitely many knights. I will sketch here the first proof we found, which I think has some fun ideas which might be of interest for other endgames, and later my friend will post a proof (that I will accept) which avoids most of the complexity of this one by dodging the most difficult types of walls White may form.

Black begins by placing their King sufficiently North of White's pieces, on the opposite color of the bishop. To each position with Black's king on the opposite color of the bishop, we associate a number measuring Black's progress. If Black plays perfectly, the value of this number on White's turn will nearly be a monovariant (a number which never decreases). In what follows I will just call it "the monovariant". We compute the monovariant as follows:

First, we use the following table to determine the bishop's contribution to the monovariant based on its location relative to the Black king.

The intuition here is that Black most prefers the bishop to the south of the king, where it is the least well placed to prevent forward progress, and likewise Black least prefers the bishop to the north of the king.

Next, for each of the two northernmost knights (choosing at random if ties must be broken), we use the following table to determine their contribution to the monovariant based on their location relative to the Black king:

The intuition here is that the table measures the vertical distance between the king and knight, with some extra penalty for the number of "inefficient moves" this knight would need to make to form a blockade in front of the king. Outside of the entries with bolded numbers, it is just 2 plus the vertical distance between the king and the knight.

At this point we observe that both knights being close to the king implies this monovariant is small, so to force mate White needs some method to force this monovariant to permanently decrease. However, provided the monovariant was large enough to begin with, Black can meet most moves by White with a single response which either captures the bishop or restores the monovariant to at least its prior value.

We now argue that Black can play such that White never gets two consecutive turns with the monovariant less than its value at the start of the game.

If the northernmost knight is currently on a green cell, Black can simply capture it (recalling that the bishop is on the opposite color of the king).

If the northernmost knight is currently on a white cell, then one checks that White's previous move decreased the monovariant by at most 2, and that some Black king move Northeast or Northwest restores the monovariant. In practice, the Black king move is whichever option between Northeast and Northwest is both legal and takes the king the furthest from the lead knight.

Yellow squares are met similarly to White squares, the only difference being that White's prior move may have decreased the monovariant by more than 2 and Blacks response will increase it by more than 2.

If the northernmost knight is on the purple square, White's last move decreased the monovariant by at most 3. If the knight is unguarded, black may simply capture it and then move north on the next turn. Otherwise the bishop is guarding the knight, and Black then has some northward move which keeps the contribution from the lead knight the same, increases the contribution from the Bishop by 2 and increases the contribution from the trailing knight by 1.

Finally, if the lead knight is on one of the red squares, White's previous move decreased the monovariant by at most 2. If possible, Black should capture any hanging piece. Otherwise if the purple square is unguarded, Black should spend the next two moves moving Northward, and after the second such move Black will have returned to the opposite color of the bishop with the monovariant restored regardless of White's play. The final case is that the bishop guards the purple square, in which case black plays the following two move sequence, taking care to choose the direction that will increase the contribution from the bishop should it not move.

[FEN "8/3N4/8/8/3k4/8/8/K6B w - - 0 1"]

1. Kb1 Ke3 2. Ka1 Kf4

White's play again does not matter, one can check that at the end of the sequence the monovariant will be restored. White's move in the middle of this sequence is the only time it is ever White to move and the monovariant could be less than its initial value, but the awkward positions of the bishop and knight guarantee Black restores order after the second move.

The analysis here only works if capturing a knight/bishop is always beneficial and if the second northernmost knight cannot be close enough to interfere with the sequences. These things are true provided Black placed their king such that the monovariant began sufficiently large, say around 20 or so. The contribution from the knight can probably be refined to further penalize knights which are far away from the king horizontally, which might be useful if one wishes to make a serious study of positions with infinitely many knights.

Answer 3

If the black king is surrounded by white units, then surely there is an n such that white king + bishop + n knights can deliver checkmate.

However if bK can run away in some direction, and the white pieces have to catch up, then I think no value of n is sufficient. The white bishop can move arbitrarily far with a single move, so that can always keep pace with the fleeing king. But if bK stays on the opposite colour squares, it will be able to keep running away.

To deliver checkmate, 9 squares must be covered. So that means at least 3 wN, or 2wN with wK. But if bK makes zigzag NW & NE moves while trying to move in a N direction, the wK can never catch up, and only 2wN can keep up with the running bK. So checkmate can never be forced.

Can bishop & knight delay bK and slow his progress northwards? A position where delay might happen is like this, with black to move.

[FEN "8/8/8/3N4/4B3/8/3k4/8 w - - 0 1"]

Of course this is just a window onto an infinite board. There are no edges. Black King generally avoids light squares, but exceptionally can move to e2, then f2 then g3 then h4.

Being charitable to White, we may say that White might manage to make another block at:

[FEN "8/7N/6B1/8/7k/8/8/8 w - - 0 1"]

Let's do some counting. Black has made 4 king moves and advanced 2 ranks. White has made 2 knight moves and 1 bishop move, and some other distant knight has moved 2 ranks closer. So overall the distant knight is no nearer to bK.

If on the other hand, bK tried to run just in NE direction, then I think wN can move faster than bK. So that's not a good strategy for Black.

This isn't a proof at the level of pure mathematics or chess solving engine, but it does convince me. Most human chess analysis is at the level of such approximate reasoning.

A question remains, what is the smallest n for which a cage exists such that bK can always be mated? n=2 is too small to checkmate even a willing bK in the middle of the board, but with n=3 a position does exist so that whoever has the move, White can checkmate with their next move.

[FEN "8/6N1/8/3B4/3k4/2NN4/2K5/8 w - - 0 1"]

1. Nf5#

Answer 4

You just said that their King has to be 'somewhere' which means that it could be a lot of squares away which would mean that it would be a draw due to 50 move rule.

But, I am assuming that you mean that the 50 move rule doesn't exist, then that means that if you place 1 bishop and an arbitrary amount of Knights, then you cannot checkmate black because:

A) You cannot bring the king in, because the other king will keep running in the opposite direction, preventing progress

B) A bishop and a knight cannot bring checkmate without a king and in the center of the board.

C) It will require something similar to this position:

[Variant "From Position"]
[FEN "8/7k/8/8/8/8/BNN5/KNN5 w - - 0 1"]

1. Nd4 Kh8 2. Ncd3 Kg7 3. Nc3 Kf6 4. Bd5 Ke7 5. Nc4 Kf6 6. Ne4+ Kg6 7. Nf4+ Kg7 8. Ncd6 Kf8 9. Nc6 Kg7

where the knights and bishop create a blockade from behind. So, theoretically, a lot of knights (could be 10, 100, 1000) could be placed extremely, nearly infinitely, far away from the 'center'. Then, wherever the opposition places the black King, you can 'push' the king from behind towards your other forces, which will assist checkmate in the center.

Answer 5

Under the given circumstances, (black can place its king anywhere after white has placed all their pieces) it is not possible.

Consider this position:

[Title ""]
[Fen "8/8/8/8/8/8/8/1k3NN1 b - - 0 1"]
[StartFlipped "0"]

1...Kb2 Nf3 Kb3 Ng3 Kb4 Ng5 Kb5 Nf5 Kb6 Nf7 Kb7 Ng7.

The king needs the same time to reach the seventh rank as the two knights do.

If two knights can not be faster, then King + bishop + two or more knights also can not.

But can bishop and knight get behind the king and block its path for a moment, so that other knights can come close? Consider this position:

[Title ""]
[Fen "8/8/8/8/8/1k6/1N6/B7 w - - 0 1"]

1.Nd3 Kc4 Ne5+ Kd5 Nf7 Ke6 Nh8 Ke7 Bg7

Black has been blocked from entering f8, f9 and e9, but that does not stop his king from advancing forward via e8-d9-e10 at vertically the same speed.

Therefore, white can not win time, and a second knight (not to speak of additional pieces necessary for mate) can not come closer faster than the king advances, see the first example. All white can do is restrict its expansion to the right or to the left a bit (but not both at the same time).

It follows that a mate is not possible on an infinite board, as long as black

• places his king at least three rows above the uppermost white piece. (three rows to prevent Kd2 vs Nd1, Ne1)
• has the first move (to prevent 1.Nd3 in Kd4 vs Bh1, Nc1, Ne1)
• runs away vertically or diagonally upwards.

Update

We have discussed in the comments if it is at least possible to prevent that the black king can go up one row on every move. My first impression was "no", but it is not so trivial.

A critical position is position A:

[Title ""]
[Fen "8/8/8/8/3B4/3N4/8/3k4 b - - 0 1"]
[StartFlipped "0"]

1...Kd2 2.Ne5 (2.Nf4) Kc2

Black's king has been stopped vertically for one move. (they needed to play 2.Kc2).

If we move the knight and bishop up two rows (= position B), we can enforce position A:

[Title ""]
[Fen "8/8/3B4/3N4/8/8/8/3k4 b - - 0 1"]
[StartFlipped "0"]

1...Ke2 2.Nf6 Kd3 3.Nd5

And if we move the knight and bishop two more rows up (= position C), then we can enforce position B:

[Title ""]
[Fen "3B4/3N4/8/8/8/8/8/3k4 b - - 0 1"]
[StartFlipped "0"]

1...Ke2 2.Nf6 Kd3 (2...Kf3 3.Bc7) 3.Nd7

If we move the King to e1 in C (= Position D) we can enforce A or an earlier barrier:

[Title ""]
[Fen "3B4/3N4/8/8/8/8/8/4k3 b - - 0 1"]
[StartFlipped "0"]

1...Kf2 2.Bc7! Ke3 (2...Kf3 3.Nf6) 3.Nf6 Kd4 4.Nd7 (4.Bd6) Kd5 5.Bd8

But I do not think it works when we move the king to f1 (= position E, moved two columns to the left to have enough space):

[Title ""]
[Fen "1B6/1N6/8/8/8/8/8/3k4 b - - 0 1"]
[StartFlipped "0"]

1...Ke2 Nd6 Kf3 Nf7 Kg4 Nh8 Kf5

... and the king escapes.

So, the questions are:

1. Can white reach one of the positions A, B, C, D? Or can black reach E?
2. Should white succeed with their plan, will this tempo be enough to bring other white pieces close enough to create a mate net over time?

In my opinion the answer to 1) is, black can reach E, because the bishop needs two moves to go to that specific location. In that time the black king can step aside.

Even if white can reach of A, B, C, D, then the answer to 2) is, that the two rows won for another knight to come closer will have been consumed by the rows which were needed to construct that barrier.