King & Rook vs King

Rooks are built for survival to the endgame, which is why the basic endgame of king and rook versus a lone king is one of the first that players learn. On a standard 8×8 chessboard a king and rook can always force a checkmate against a lone king from every one of the 175,168 legal positions where it is the stronger side’s turn to move. The king and rook also win in 90% of the 223,944 legal positions where it is the lone king’s turn to move, but in 22,244 of them the lone king is either already stalemated or can immediately capture the rook. Starting from any winning position the king and rook can force checkmate in at most 16 moves with perfect play by both sides.

What about larger boards? A recently published paper defined a general strategy for n×n boards and formally proved that by following it the king and rook will always force checkmate against any defence by the lone king. The strategy in the paper works for any n greater than 3—there are no legal positions on 1×1 or 2×2 boards and the winning strategy on a 3×3 board is easy to discover. At this point we need to specify that the 50 move rule is not in force, or else the proportion of legal positions that are winning for the king and rook will become vanishingly small as the board size increases.

What about infinite boards? For a board stretching to infinity in all directions there is no hope of checkmate: from any square a lone king can move to 8 adjacent squares, and a king and rook together cannot control more than 6 of them. For the same reason a king and rook cannot checkmate a lone king on a finite board in the shape of a torus. But what about an infinite quadrant, where there is a square for every pair (x,y) of natural numbers and (1,1) is the single corner square?

A natural plan for the lone king is to run away from the corner as fast as possible, and if the rook tries to box it in then the king can move to the square diagonally adjacent to the rook and threaten to capture it, forcing it further away. The only way to stop the lone king from chasing the rook further and further away from the corner is for it to be defended by its king, and surprisingly there is a neat strategy to achieve this from any starting position. The strategy is to use the rook to box in the lone king to make it traverse two sides of a large square drawn on the board, while the other king moves along the diagonal which takes half as many moves to get to the same end point. Here are the gory details:

1. Suppose the lone king starts on the square (x,y) and the other king starts on the square (p,q).
2. The rook first makes two moves to get to the square (x + 2, n) boxing in the lone king (where n is a large number we will define later).
3. The lone king makes ny moves to get to the square (x + 1, n – 1).
4. Meanwhile, the other king makes max((n + 1) – p, (n + 1) – q) moves to get to the square (n + 1, n + 1).
5. When the lone king arrives at the square (x + 1, n – 1) to attack the rook at (x + 2, n), the rook makes one move to the square (n,n).
6. The long king makes n – (x + 2) moves to get to the square (n – 1, n – 1).

In total the king and rook together make n + 4 – min(p, q) moves, and the lone king makes 2n – (x + y + 2) moves. Thus by choosing any n ≥ 6 + x + y – min(p,q) the king and rook can arrange that when the lone king arrives at the square (n – 1, n – 1) to attack the rook at (n,n), the rook is defended by its king at (n + 1, n + 1).

Instead of immediately running toward the rook the lone king can complicate matters by trying to pin the other king to an edge and stop it moving to its rendezvous square, but the rook can always help its king to escape and once free the strategy above can be restarted. And once the lone king is boxed in by a rook defended by a king, it can be driven to the corner and checkmated with a technique similar to the one used on a standard 8×8 chessboard.

We have shown that a king and rook can force a checkmate against a lone king from any initial position on an infinite quadrant, but what about a half-infinite board that has one edge and no corners? From what starting positions can a king and rook force a checkmate against a lone king?