Answers.Body: <p>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 <strong>Carlo Wood</strong> 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.)</p>
  <p>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.</p>
  <p>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 <em>diagonally</em>, 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.</p>
  <p>According to Berlekamp, Conway, and Guy's <em>Winning Ways</em>,
  mathematician Simon Norton asked
  this problem for the specific position Ka1,Rb2/Kc3, asking
  &quot;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?&quot;
  The <em>Winning Ways</em> authors suggest that a 9x11 board already suffices.
  <a href="https://www.google.com/books/edition/Winning_Ways_for_Your_Mathematical_Plays/_0laDwAAQBAJ?hl=en&amp;gbpv=1&amp;dq=king+and+rook+%22quarter+infinite%22&amp;pg=PA667&amp;printsec=frontcover" rel="nofollow noreferrer">https://www.google.com/books/edition/Winning_Ways_for_Your_Mathematical_Plays/_0laDwAAQBAJ?hl=en&amp;gbpv=1&amp;dq=king+and+rook+%22quarter+infinite%22&amp;pg=PA667&amp;printsec=frontcover</a></p>
  <p>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>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-28T01:09:15.693Z
Answers.LastActivityDate: 2022-03-30T14:13:08.447Z
Answers.LastEditDate: 2022-03-30T14:13:08.447Z
Answers.UserDisplayName: Noam D. Elkies
Answers.Body: <p>One can apply a regression to this problem, and in your case you use the n and m as features.</p>
  <p>Made an experiment on 8x8 board, generate some 50 random positions to create a dataset. Do regression with sklearn with 2 and 3 features.</p>
  <p><strong>Dataset</strong></p>
  <pre><code>                            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
  ...
  </code></pre>
  <pre><code>n = black king distance from &quot;a&quot; file, if black king is in a-file, n=1
  m = black king distance from &quot;8th&quot; rank, if black king is in rank 7, m=2
  k = distance between black and white kings
  dtm = distance to mate
  </code></pre>
  <h3>Regression results</h3>
  <p><strong>2 features n and m</strong></p>
  <pre><code>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
  </code></pre>
  <p><strong>3 features n, m, k</strong></p>
  <pre><code>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
  </code></pre>
  <p>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.</p>
  <p>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.</p>
  <h3>Example</h3>
  <p><a href="https://i.sstatic.net/isfSI.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/isfSI.png" alt="enter image description here" /></a></p>
  <pre><code>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
  </code></pre>
  <p><em>Edit</em><br />
  There is a program called fairy stockfish at <a href="https://github.com/ianfab/Fairy-Stockfish" rel="nofollow noreferrer">https://github.com/ianfab/Fairy-Stockfish</a> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-28T09:21:59.337Z
Answers.Text: I doubt that the factors for n and m will be fractions - it seems even unlikely that they will be different? I am writing a C++ program right not to brute force it, so I guess I'll know soon ;).
Answers.UserDisplayName: Carlo Wood
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-28T10:43:00.443Z
Answers.Text: @CarloWood: It is also known that the fastest strategy on 8*8 usually is a mix of the two basics (checking back and boxing in), so I don't expect a "neat" formula beyond some guaranteed O(n) Noam already mentioned.
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-29T00:49:43.640Z
Answers.Text: @CarloWood looking forward to the result of your attempt to solve it.
Answers.UserDisplayName: ferdy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-29T08:56:32.067Z
Answers.Text: @ferdy Right now I am here - lol: https://math.stackexchange.com/questions/4414986/algorithm-to-find-loops-in-directed-bipartite-graph-with-a-stable-weight-under  which is an interesting puzzle all by itself!
Answers.UserDisplayName: Carlo Wood
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-29T11:14:10.480Z
Answers.Text: @ferdy Right now I wouldn't be surprised if it takes white 12 moves to make 3 rows advancement - which would be a loop (see above link) of 24 ply! :(.  This doesn't look like something that can be brute forced :/
Answers.UserDisplayName: Carlo Wood
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-30T12:19:54.750Z
Answers.Text: I changed the name of the math question - maybe the link changed, so here it is again: https://math.stackexchange.com/questions/4414986/algorithm-to-find-a-stable-minimum-cycle-mean-in-a-bipartite-digraph-under-compe   Also, I gave up on this problem. The math problem as stated does not appear to be solved even remotely, and related studies that have been done are over my head (use math notations that I do not understand; for example https://www.sciencedirect.com/science/article/pii/0012365X78900110).
Answers.UserDisplayName: Carlo Wood
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-28T07:51:37.303Z
Answers.LastActivityDate: 2022-04-01T01:55:52.267Z
Answers.LastEditDate: 2022-04-01T01:55:52.267Z
Answers.UserDisplayName: ferdy
Body: <p>Consider a board with only two edges that are perpendicular.</p>
  <p>Something like:</p>
  <pre><code>.------------------------------------------------------
  |                                         ^
  |                                         |m
  |&lt;------------n----------------&gt;bK  wK    v
  |                                        wR
  |
  |
  |
  </code></pre>
  <p>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?).</p>
  <p>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.</p>
  <p>Lets use a 8x8 board to illustrate things below.</p>
  <p>Below <code>n = 4</code> and the rook is placed such that the black king has only 1 row (<code>m = 1</code>).
  The optimal way to mate here is (with white to play):</p>
  <pre><code>[FEN &quot;4k1K1/7R/8/8/8/8/8/8 w - - 0 1&quot;]
  
  1. Rg7 Kd8 2. Kf8 Kc8 3. Ke8 Kb8 4. Kd8 Ka8 5. Kc7 Ka7 6. Rg6 Ka8 7. Ra6#
  </code></pre>
  <p>Thus, we can conclude that it in the general case (where the rook is far to the right) it will take <code>n+3</code> moves for white to give mate. But note how white began with losing a tempo by playing a rook move.</p>
  <p>Now consider the case where the rook is on the third row from the edge (<code>m = 2</code>).</p>
  <p>If black uses the strategy to walk away straight from the <code>wK</code> (ie, remains on the second rank), he loses as fast as in the previous case:</p>
  <pre><code>[Variant &quot;From Position&quot;]
  [FEN &quot;8/4k1K1/7R/8/8/8/8/8 w - - 0 1&quot;]
  
  1. Rf6 Kd7 2. Kf7 Kc7 3. Ke7 Kb7 4. Kd7 Ka7 5. Kc7 Ka8 6. Ra6#
  </code></pre>
  <p>That is <code>n + constant</code>. 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):</p>
  <pre><code>[Variant &quot;From Position&quot;]
  [FEN &quot;8/4k1K1/7R/8/8/8/8/8 w - - 0 1&quot;]
  
  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#
  </code></pre>
  <p>The pattern starts different, with <code>1... Kd7</code> as opposed to <code>1... Kd8</code> because after <code>1... Kd8? 2. Rf7!</code> resulting in a much faster win for large <code>n</code>.</p>
  <p>In fact, an 8x8 board is already too small to properly investigate the best algorithm for large <code>n</code> and <code>m=2</code>. At first sight the number of moves is going to be <code>2n + constant</code>, but of course, white has the trick to play the rook to the <em>left</em> of its king!</p>
  <pre><code>[Variant &quot;From Position&quot;]
  [FEN &quot;8/5k1K/7R/8/8/8/8/8 w - - 17 9&quot;]
  
  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#
  </code></pre>
  <p>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 <code>n + 6</code>.</p>
  <p>Now, given the relative positions of the three pieces from the last starting position (<code>bK</code> and <code>wK</code> opposing and <code>wR</code> on the same file as the <code>wK</code>; white to move), with <code>n</code> empty squares on the left of the <code>bK</code> and the <code>wR</code> being <code>m</code> rows from the edge (<code>m=2</code> in the last position).</p>
  <p><strong>Then in how many moves can white give mate on said infinitely large board, for large <code>n</code> and any <code>m &gt; 0</code> ?</strong></p>
  <p>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 <code>2n + c</code> with <code>m = 2</code>:</p>
  <pre><code>[Variant &quot;From Position&quot;]
  [FEN &quot;4k3/6K1/7R/8/8/8/8/8 w - - 0 1&quot;]
  
  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#
  </code></pre>
  <p>Which thus can be improved for large <code>n</code> (the above <em>is</em> an optimal mate in 9 though), but which returns shortly with <code>m = 3</code>:</p>
  <pre><code>[Variant &quot;From Position&quot;]
  [FEN &quot;8/4k3/6K1/7R/8/8/8/8 w - - 0 1&quot;]
  
  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#
  </code></pre>
  <p>where mate in 12 is indeed the fastest possible (on 8x8).</p>
  <p><a href="https://i.sstatic.net/J8cp6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/J8cp6.png" alt="It looks awesome anyway" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-03-27T20:17:15.020Z
Comments.Text: The question is above the second chess board from the bottom :-D "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 ?"
Comments.UserDisplayName: Carlo Wood
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-03-27T20:19:21.937Z
Comments.Text: I am not really interested in a constant offset. The answer is probably `a*n + b*m + c` and then only `a` and `b` are interesting - plus the argumentation (algorithm / strategy) that leads to that conclusion, of course.
Comments.UserDisplayName: Carlo Wood
Tags: <problems><mathematics><rook-endgame>
Title: Fastest algorithm to give mate with K+R vs K on infinite large board as function of starting position
ThreadText: # Fastest algorithm to give mate with K+R vs K on infinite large board as function of starting position
  
  (Asked by: username_0 on 2022-03-27)
  
  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).
  
  [![It looks awesome anyway](https://i.sstatic.net/J8cp6.png)](https://i.sstatic.net/J8cp6.png)
  
  **Tags:** problems, mathematics, rook-endgame
  
  > **Comments:**
  > **username_0**: The question is above the second chess board from the bottom :-D "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 ?"  
  > **username_0**: I am not really interested in a constant offset. The answer is probably `a*n + b*m + c` and then only `a` and `b` are interesting - plus the argumentation (algorithm / strategy) that leads to that conclusion, of course.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2022-03-28. Score: 5
  
  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 **username_0 username_0** 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 by username_2 on 2022-03-28. Score: 0
  
  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
  
  [![enter image description here](https://i.sstatic.net/isfSI.png)](https://i.sstatic.net/isfSI.png)
  
  ```
  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.
  
  > **Comments:**
  > **username_0**: I doubt that the factors for n and m will be fractions - it seems even unlikely that they will be different? I am writing a C++ program right not to brute force it, so I guess I'll know soon ;).  
  > **username_3**: @username_0: It is also known that the fastest strategy on 8*8 usually is a mix of the two basics (checking back and boxing in), so I don't expect a "neat" formula beyond some guaranteed O(n) username_1 already mentioned.  
  > **username_2**: @username_0 looking forward to the result of your attempt to solve it.  
  > **username_0**: @username_2 Right now I am here - lol: https://math.stackexchange.com/questions/4414986/algorithm-to-find-loops-in-directed-bipartite-graph-with-a-stable-weight-under  which is an interesting puzzle all by itself!  
  > **username_0**: @username_2 Right now I wouldn't be surprised if it takes white 12 moves to make 3 rows advancement - which would be a loop (see above link) of 24 ply! :(.  This doesn't look like something that can be brute forced :/  
  > **username_0**: I changed the name of the math question - maybe the link changed, so here it is again: https://math.stackexchange.com/questions/4414986/algorithm-to-find-a-stable-minimum-cycle-mean-in-a-bipartite-digraph-under-compe   Also, I gave up on this problem. The math problem as stated does not appear to be solved even remotely, and related studies that have been done are over my head (use math notations that I do not understand; for example https://www.sciencedirect.com/science/article/pii/0012365X78900110).  
  
  ---
  
  