7
$\begingroup$

On an infinite chessboard there's a single white king and N black kings. The nearest black king must be K moves away from the white king. Given N, white dictates the value of (finite) K, then black places their kings.

Question 1: Can white always force a draw without capturing any black kings? (by forcing a draw I mean white king is never captured if the game goes on forever)

Question 2: If instead of kings we have power-one rooks, which can only move one square, can white rook avoid being captured without capturing black pieces?


Related: Can the fugitive escape? (continuous version dual problem)

$\endgroup$
8
  • $\begingroup$ does 'infinite chessboard' mean it is infinite in all 4 directions? I.e. there is no corner or no 'back row' (which you can still have in an infinite board) $\endgroup$
    – JimN
    Apr 14, 2021 at 16:18
  • $\begingroup$ @JimN It's infinite in all 4 directions. This is actually a dual problem of the escaping fugitive problem, in discrete version. $\endgroup$
    – Eric
    Apr 14, 2021 at 16:22
  • 2
    $\begingroup$ As you mention the possibility of capturing a king with a king I take it that certain rules of chess are suspended (like a king cannot move into check)? $\endgroup$
    – loopy walt
    Apr 14, 2021 at 16:47
  • $\begingroup$ @loopywalt Yeah, let's ignore those laws. They're just officers and fugitive dressing and acting like chess kings ;-) $\endgroup$
    – Eric
    Apr 14, 2021 at 16:52
  • 2
    $\begingroup$ Who goes first? $\endgroup$
    – gbe
    May 18, 2021 at 19:40

2 Answers 2

4
$\begingroup$

figures

In figures (1a), (1b), (2a), and (2b), the white cells are empty and the red cells may or may not contain black pieces. The pattern continues in the obvious way out to the infinities. In figures (3a) and (3b), the blue cells (and other diagramming) are used in the description.

I'm going to assume white goes first. It's supposed to be that way, but if not just add $1$ to every $K$ below and all the conclusions are the same. One assumes "K moves away" means $K$ cells away, and it turns out not to be helpful to black to be allowed to place pieces farther than $K$.

I'm not going to be be absolutely rigorous, because this was already quite a lot of work and detailing all cases would exhaust both you and me. However, this will still be proof-like, and I'll give intuition for the handwaved cases. Nevertheless, a disclaimer:

Owing to the complexity of this problem, my analysis below is abbreviated, not bulletproof, and may actually be wrong.


Question 1 Answer: King Escapes Iff $N\!\leq\!3$


Escape for $N\!\leq\!2$

White can escape if they can put their king into the position in figure (1a) or (1b), or any rotation of those positions. This is pretty obvious by inspection: if a black king moves (necessarily out of a red cell) into a white cell, the white king can always move so that the original situation is restored.

When $N\!=\!1$, white can pick $K\!\geq\!1$, and no matter how black places their king, white will be able to move into figure (1a) and escape. If $K\!\gt\!1$, white starts in figure (1a) automatically.

When $N\!=\!2$, white can pick $K\!\geq\!2$, and will reach figure (1a) in at most one move. For $K\!=\!2$, there are 20 unique configurations (up to symmetry), most of them obviously terrible for black. The most challenging is if black places one king two cells north and the other two cells south, but then white can then just move east. In the other 19 cases, escape by figure (1b) is also reachable in at most one move. Often the king in fact starts in (1a), (1b), or both.


Escape for $N\!=\!3$

By using similar arguments as the $N\!=\!2$ case, we notice that the best position for black is as suggested by figure (3a).

Escape for white is possible, but requires slightly careful play. The gist of the solution is for white to run toward one of the wider gaps, seeking to achieve figure (1a).

Let's assume the situation is as depicted. White's figure (1a) eastern escape contour is shown in black. Notice that the southeast king is inside it while the north king is outside it. The north king requires two moves to move inside it, while the southeast king is two moves from being excluded by it diagonally or three orthogonally. White starts by moving northeast or east, reducing that by 1.

Intuitively, white tries to run east, trying to exclude both kings from the boundary. Notice that if black only races southeast with the north king, the white king can just keep walking east and will achieve the goal on move 3 when the southeast king is excluded. Thus, black must try to use the southeast king too. However, if black marches the southeast king upward, white can move northeast, maintaining the distance to both kings, but moving east of the north king, eventually resulting in an escape by figure (1b).

In short, black has two kings to keep inside the boundary of figure (1a) and, although one starts inside, white can exclude it in just a few moves or else stall until escaping by figure (1b). An example game is shown in magenta.

One might wonder about different configurations for black's kings. Exploring these is a bunch of boring case work, but intuitively speaking, shifting the north king east one or two cells doesn't change the outcome because the white king can run south instead of east. Shifting the north king east and the west king south opens an immediate escape by figure (1b) to the northwest instead. Shifting the southeast king doesn't help. Finally, everything besides these is trivially worse.


Capture for $N\!\geq\!4$

When $N\!=\!4$, black can place their kings in an arrangement as suggested by figure (3b): one king north, one west, one east, and one south, no matter what $K$ white chooses.

Proving that this traps the white king is a bit tricky. Imagine that we have 'lines of force' emanating diagonally from each of the four black kings, as shown. We now define an invariant: for every blue square (covered by a line of force from a black king), that black king can intercept an attempt by the white king to move into it. That is, the white king might be able to move into a blue square, but a black king would be able to capture it.

The white king begins completely surrounded by blue cells, and the invariant is true by inspection. Note: I haven't filled in the diagonals, but the cells on the outside could be filled in too, pretty clearly; I'm omitting them for clarity, and because with a little more caution they aren't needed anyway.

Any move white makes, we claim that black can make a move that both (re-)enforces the invariant as necessary, and shrinks the number of cells available to the white king. Since the king starts with a finite number of cells, it follows that white is eventually captured.

If the white king moves northeast, it moves closer to the northeast cells. If the north king is closer, then the north king moves southeast, counteracting the distance decrease on all cells, and so re-enforcing the invariant, while also decreasing the area available to white's king (by the movement of the other cells behind). Similarly, if the east king is closer, the east king moves northwest, re-enforcing the invariant and decreasing the area.

If the white king moves east, the east king can move west (possibly with an additional deflection north or south according to the position of the white king), re-enforcing the invariant and reducing the area available to the white king.

Both arguments apply symmetrically with respect to rotation, so we conclude that the white king cannot viably flee in any direction!

For $N\!\gt\!4$, capture follows trivially by black placing their extra kings somewhere else and proceeding as if they had only $N\!=\!4$.


Question 2 (Partial) Answer: Rook Escapes If $N\!\leq\!3$ (Conjecture: all $N$)

I appreciate the superficial similarity of the scenarios but, given the complexity of each, it would have been better if this had been a separate question. For this reason, my answer in this section will be partial, and focus only on the similarities.


Escape for $N\!\leq\!2$

The proof for these cases proceeds exactly as for the kings case.


Escape for $N\!=\!3$

The proof for this is significantly easier than for the kings case. The white rook simply has to walk east. The southeast rook is forced to walk north to intercept in time.

Once they are catercorner from each other, rather than continuing on to move in front of the southeast rook, the white rook now runs north. The southeast rook is forced to pursue north (if it doesn't, e.g. if the north rook moves instead, then the white rook can escape east. This can continue indefinitely, so the white rook is considered to have escaped.


Escape for $N\!=\!4$

White selects a sufficiently large $K$, and black arranges their rooks in the same cardinal-directions configuration as in the kings scenario.

White now walks toward a corner (say, the northwest). The west and north rooks must also march north and west, respectively, in order to keep pace, or else white will escape by figure (2b).

However, at a certain point, white can then run east instead. The east rook is to the south. If it starts moving north to intercede, the white rook can get ahead of the north rook, escaping by (2b). If the east rook doesn't move north, then white will just be able to run east indefinitely, with the north rook only able to run along above.

The other arrangement of interest is if the black rooks start at the diagonal directions. In this case, white runs east, seeking an escape by figure (2a).

The northeast and southeast rooks begin inside the contour, but can be excluded in two moves each. Each move by white moves both rooks closer to exclusion, but each move by black can only bring one rook further inside. Therefore, if black tries to keep both rooks in the contour, in five moves, they will both be excluded. Thus, black can only keep up with one rook, in which case white eventually escapes by figure (2b) (possibly after a turn to north or south, depending on how much black commits).


Escape for $N\!\gt\!4$?

Anecdotally, it seems like white can always set up a situation similar to the $N\!=\!4$ case, where the other rooks simply don't matter. So, I conjecture escape is possible for any $N$ when white selects a big enough $K$.

$\endgroup$
1
  • $\begingroup$ Can you address the escape strategy for N=4 in Retudin's answer? $\endgroup$
    – Eric
    Mar 21 at 1:09
2
$\begingroup$

Partial answer for N=4

with N=4 and the black kings at distance 7 (or more) on the cardinal directions, white can force a draw:
1/ Move 3 times NE. The north or east king must move to block a NE escape(assume east).
2/ Move 1 time NW; the east king must follow. Then move N,S,N,S.. until black moves into the pink region. note: The east king must match its row each time to block a NW or SW escape.
3/ Move 3 times SE.
4a/ As soon the east king does not follow, move 4 times SE and escape to the east.
4b/ If the east king does follow 3 times, escape NW.
See the left picture for the initial moves; the right picture for some potential escape routes; which cannot all be blocked. enter image description here

$\endgroup$
7
  • $\begingroup$ I don't understand your argument. E.g. in step (2) you seem to have the white king and the black king stepping back and forth north/south? In this case, black just captures white diagonally, game over . . . ? ¶ After move (6), white must move west (possibly north/southwest), pushing it toward the other kings where, in my analysis, it gets cornered (e.g. if white continues northwest, it dies move (12)). $\endgroup$
    – geometrian
    Mar 21 at 5:48
  • $\begingroup$ If white moves to 7; black does not have to move into the pink area; it can move the east king N or NE and still block the NE escape. White will move N-S-N-S until black moves into the pink area. As soon as that happens, white moves 3 times SW (i.e. starts step 3, as show in picture 2.) --With 'attacks' I meant moves adjacent to it ; I hope this clarifies it. $\endgroup$
    – Retudin
    Mar 21 at 7:27
  • $\begingroup$ As soon as white is at picture2-position5 and black to move with its east king at 4: Black cannot prevent all 3 escape routes shown. $\endgroup$
    – Retudin
    Mar 21 at 7:29
  • $\begingroup$ Okay I understand what you're saying, but still not how this makes sense. In the first part, black should not move N (NW is clearly better). But stipulating that, if afterward white-king cuts SW, there's no particular necessity for east-king to pursue (white-king is obligingly moving inward from all boundaries!). East-king could move S, reinforcing south escape, or (2) could be north-king SW instead. All kings should be moving in, adjusting any distances in response to what the white king does. And none of this addresses / refutes my 'capture' solution above (which may indeed be wrong!). $\endgroup$
    – geometrian
    Mar 21 at 8:12
  • $\begingroup$ You are right that position 4 (2nd picture) of the east king can be up to 3 places further east (and that that makes more sense defensively). But he needs to be 5 further east to prevent the escape though 13 after the mandatory northking-move 6. $\endgroup$
    – Retudin
    Mar 21 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.