Fastest algorithm to give mate with K+R vs K on infinite large board as function of starting position

Question

Consider a board with only two edges that are perpendicular.

Something like:

.------------------------------------------------------
|                                         ^
|                                         |m
|<------------n---------------->bK  wK    v
|                                        wR
|
|
|

The edge on the right-side doesn't exist (or is very far away), so the task of white is to first drive the black king to the left, into the corner (or is it?).

Assume that both kings are on the edge and opposing each other as shown. Further more assume that there are n empty squares between the left-edge and the black king.

Lets use a 8x8 board to illustrate things below.

Below n = 4 and the rook is placed such that the black king has only 1 row (m = 1). The optimal way to mate here is (with white to play):

[FEN "4k1K1/7R/8/8/8/8/8/8 w - - 0 1"]

1. Rg7 Kd8 2. Kf8 Kc8 3. Ke8 Kb8 4. Kd8 Ka8 5. Kc7 Ka7 6. Rg6 Ka8 7. Ra6#

Thus, we can conclude that it in the general case (where the rook is far to the right) it will take n+3 moves for white to give mate. But note how white began with losing a tempo by playing a rook move.

Now consider the case where the rook is on the third row from the edge (m = 2).

If black uses the strategy to walk away straight from the wK (ie, remains on the second rank), he loses as fast as in the previous case:

[Variant "From Position"]
[FEN "8/4k1K1/7R/8/8/8/8/8 w - - 0 1"]

1. Rf6 Kd7 2. Kf7 Kc7 3. Ke7 Kb7 4. Kd7 Ka7 5. Kc7 Ka8 6. Ra6#

That is n + constant. A better strategy is to move to the edge at the moment the white king is on the second rank (so the rook can't be played to the second rank):

[Variant "From Position"]
[FEN "8/4k1K1/7R/8/8/8/8/8 w - - 0 1"]

1. Rf6 Kd7 2. Kf7 Kc8 3. Ke7 Kc7 4. Rh6 Kb8 5. Kd7 Kb7 6. Rg6 Ka8 7. Kc7 Ka7 8. Rh6 Ka8 9. Ra6#

The pattern starts different, with 1... Kd7 as opposed to 1... Kd8 because after 1... Kd8? 2. Rf7! resulting in a much faster win for large n.

In fact, an 8x8 board is already too small to properly investigate the best algorithm for large n and m=2. At first sight the number of moves is going to be 2n + constant, but of course, white has the trick to play the rook to the left of its king!

[Variant "From Position"]
[FEN "8/5k1K/7R/8/8/8/8/8 w - - 17 9"]

1. Ra6 Ke7 2. Kg7 Kd7 3. Kf7 Kc7 4. Ke7 Kb7 5. Rh6 Kc7 6. Rg6 Kc8 7. Kd6 Kb7 8. Kd7 Kb8 9. Kc6 Ka7 10. Kc7 Ka8 11. Ra6#

Effectively still shifting one position to the left per move (or else the rook goes to the second rank), and it is in fact mate in n + 6.

Now, given the relative positions of the three pieces from the last starting position (bK and wK opposing and wR on the same file as the wK; white to move), with n empty squares on the left of the bK and the wR being m rows from the edge (m=2 in the last position).

Then in how many moves can white give mate on said infinitely large board, for large n and any m > 0 ?

One more remark though - notice this interesting zigzag strategy of white where the king goes in front of its own rook in order to achieve a 2n + c with m = 2:

[Variant "From Position"]
[FEN "4k3/6K1/7R/8/8/8/8/8 w - - 0 1"]

1. Kf6 Kd7 2. Kf7 Kd8 3. Ke6 Kc7 4. Ke7 Kc8 5. Kd6 Kb7 6. Kd7 Kb8 7. Kc6 Ka7 8. Kc7 Ka8 9. Ra6#

Which thus can be improved for large n (the above is an optimal mate in 9 though), but which returns shortly with m = 3:

[Variant "From Position"]
[FEN "8/4k3/6K1/7R/8/8/8/8 w - - 0 1"]

1. Kf5 Kd6 2. Kf6 Kd7 3. Ke5 Kc6 4. Ke6 Kc7 5. Kd5 Kd7 6. Rh7+ Ke8 7. Ke6 Kd8 8. Rf7 Kc8 9. Kd6 Kb8 10. Kc6 Ka8 11. Kb6 Kb8 12. Rf8#

where mate in 12 is indeed the fastest possible (on 8x8).

Answer 1

It is known that White can force mate from any starting position of K+R vs. K on a quarter-infinite board. It's probably too hard a problem to ask for an exact optimal strategy, but it's not too hard to show that -- as Carlo Wood suggests in a comment -- there are constants a,c such that mate can be forced in at most a*n+c moves from any position with both Kings in the in the n-by-n corner. (We needn't worry about the Rook because it can get anywhere in two moves.)

The basic idea is to use the Rook, supported by its King, to limit the defending King to a rectangle near the corner, and then to shrink that rectangle one step at a time, each step taking at most a constant number of moves. Eventually the King is confined to an Nx1 rectangle, and gets mated in about N further moves.

One wrinkle is that the Rook might be farther from its own King than from the defender's. But when the Rook is attacked, it can retreat say six squares in one direction, and then, when attacked again, turn 90 degrees and retreat another six squares. During the other 10 moves, the Rook's King approaches it diagonally, while the defender has to move on Rook lines and thus advances only six squares diagonally. So eventually the Rook is reunited with its King and the squeeze play can start.

According to Berlekamp, Conway, and Guy's Winning Ways, mathematician Simon Norton asked this problem for the specific position Ka1,Rb2/Kc3, asking "What is the smallest board (if any) that White can win on if Black is given a win if he walks off the North or East edges of the board?" The Winning Ways authors suggest that a 9x11 board already suffices. https://www.google.com/books/edition/Winning_Ways_for_Your_Mathematical_Plays/_0laDwAAQBAJ?hl=en&gbpv=1&dq=king+and+rook+%22quarter+infinite%22&pg=PA667&printsec=frontcover

I don't know whether this has been verified; it should be easy with the same algorithm that by now has completely solved all positions with at most 7 men on an 8x8 board.

P.S. It seems that White barely wins Simon Norton's position Ka1,Rb2/Kc3 on a board with 9 columns and 11 rows starting with 1 Re2 (or Rb11) Kd4 2 Re11 Kd5 3 Kb2 Kd6 (Kd4 lasts a few moves longer but ends up in much the same place after 4 Kc2 etc.) 4 Kc3 Kd7 5 Kd4 Kd8 6 Ke5 Kd9 7 Kf6 Kd10 8 Ri11 Ke10 9 Kg7 Kf10 10 Kh8 Kg10 11 Ki9. Now the Black King is securely penned in an 8-by-10 rectangle, and can be gradually restricted further, e.g. 11 . . . Kg9 (else 12 Ki8) 12 Ri10 Kg8 (else 13 Ki7) 13 Ki8! (easier than 13 Rh10 Kg9) Kg9 14 Ra10 followed by 13 Kh8 or 13 Ra9, etc.

Answer 2

One can apply a regression to this problem, and in your case you use the n and m as features.

Made an experiment on 8x8 board, generate some 50 random positions to create a dataset. Do regression with sklearn with 2 and 3 features.

Dataset

                            fen  n  m  k  dtm
 8/8/8/8/8/4k1K1/7R/8 w - - 0 1  5  6  2   12
8/8/8/2k2K2/6R1/8/8/8 w - - 0 1  3  4  3    9
 8/8/8/8/k1K5/3R4/8/8 w - - 0 1  1  5  2    2
 8/8/k4K2/6R1/8/8/8/8 w - - 0 1  1  3  5    7
 8/8/8/1k4K1/7R/8/8/8 w - - 0 1  2  4  5   11
 8/8/8/k2K4/4R3/8/8/8 w - - 0 1  1  4  3    2
 8/8/8/8/8/8/3k2K1/7R w - - 0 1  4  7  3   10
...

n = black king distance from "a" file, if black king is in a-file, n=1
m = black king distance from "8th" rank, if black king is in rank 7, m=2
k = distance between black and white kings
dtm = distance to mate

Regression results

2 features n and m

all data: 50

2 features

train r_square: 0.44598
coeff: [1.53505154 0.30384766]
interc: 2.5610937369050166

test pred: [11, 5, 10, 8, 11, 5,  9, 4, 11, 6, 6, 5, 7, 7, 6]
test true: [ 8, 7,  9, 9, 10, 8, 13, 5,  7, 7, 8, 2, 8, 5, 4]

test rmse: 2.21

formula:
dtm = 1.535 * n + 0.304 * m + 2.56

3 features n, m, k

all data: 50

3 features

train r_square: 0.78963
coeff: [2.30174642 0.48114933 1.9430957 ]
interc: -6.388479601770181

test pred: [6, 8, 9, 7, 9, 12, 4, 10, 6, 10, 6, 7, 5, 10, 9]
test true: [6, 7, 7, 7, 8, 12, 5,  8, 5, 12, 8, 8, 4, 10, 6]

test rmse: 1.43

formula:
dtm = 2.302 * n + 0.481 * m + 1.943 * k - 6.3885

Of course using 3 features is more accurate with a lower rmse (root mean squared error) of only 1.43 because king distance is critical to mate the opponent king.

From the used dataset the highest weight of 2.302 is given by the distance of black king from the edge of the board. This is then followed by the king-king distance at 1.943.

Example

8/8/3k2K1/7R/8/8/8/8 w - - 0 1
n = 4
m = 3
k = 3

formula:
dtm = 2.302 * n + 0.481 * m + 1.943 * k - 6.3885

prediction:
dtm = 2.302*4 + 0.481*3 + 1.943*3 - 6.3885
dtm = 10

fen true dtm is 9.

error = 10-9 or 1

Edit
There is a program called fairy stockfish at https://github.com/ianfab/Fairy-Stockfish where you can setup a board larger than 8x8. This can be used to generate a dataset to give distance to mate for a given position.