Answers.Body: <p>I think we can at least set a maximum for the number of knights needed.</p>
  
  <p>First off, the special cases. Checkmate is impossible on a 3x3 (or smaller) board. The knights cannot control the middle square and can thus never give checkmate. On a 4x4 board, the board is so small that if there are 4 knights and the king starts in the middle, the king is next to one of the knights and may be able to take it immediately and fork the remaining 3 for an easy draw, or if you move the king to the corner so it doesn't start in check, it starts the game immediately stalemated.</p>
  
  <p>In the following diagram, the black pawns represent squares that the king cannot cross:</p>
  
  <pre><code>[FEN "3k4/8/8/ppp2ppp/2pppp2/NN4NN/8/8 w - - 0 1"]
  </code></pre>
  
  <p>If you imagine that pattern continuing, each pair of knights is controlling 6 files.  So, to make a wall covering the entire board, you would need 2 knights for every 6 files. An additional 2 knights could ensure that the wall can slowly advance with no gaps. The wall can continue to advance until the opposing king is pinned to the back rank, and after that checkmate should be easy. So, on an NxN board of size at least 5, a maximum of <code>ceiling(N/6) * 2 + 2</code> knights should be enough to checkmate. On a 300x300 board, which contains 90,000 squares, 102 knights would therefore be sufficient. (This implies a maximum of 6 knights needed on a regulation 8x8 board, which I'm pretty sure is more than what is actually needed - 4 seems like it would be enough.)</p>
  
  <p>There are probably better methods which could reduce this number, but I give it as a starting point.</p>
  
  <blockquote>
    <p>Are they fast enough to surround opponent's king in very limited <strong>constant</strong> count for various finite board sizes</p>
  </blockquote>
  
  <p>It could never be constant (and that part won't change even if the side with the knights also has a king.) After all, only 2 knights (or a king) can chase the king, and 2 knights (or a king... or even 2 knights <em>and</em> a king) cannot force checkmate, so at the very least the opposing king could run until it hit the edge of the board, and the amount of moves that takes is a function of the board size. Therefore, no checkmating method could be faster than O(N). The method I give of advancing a wall seems to be O(N^2) since the wall has further to go and takes longer to advance the bigger the board is.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-15T03:59:45.383Z
Answers.LastActivityDate: 2019-10-15T03:59:45.383Z
Answers.UserDisplayName: D M
Answers.Body: <p>Not rigerous, however:</p>
  
  <ol>
  <li>In lateral movement two knights move as fast as one king.</li>
  <li>We know from end-game theory that two knights are not able to force the king into positions.</li>
  </ol>
  
  <p>.. thus I'd say it's very unlikely that unlimited knights+king would be able to mate a king that has a free direction to run in (unlimited board). If it's possible to corner it however (limited board and unlimited moves), unlimited knights are certainly enough, as they could simply divide up the board and slowly decrease the available space.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-25T01:52:14.213Z
Answers.Text: "unlimited knights" makes no sense on a limited board; you can't have more knights than squares after all.
Answers.UserDisplayName: D M
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-12T17:42:15.230Z
Answers.Text: Moreover, if the direction from the K's present square to its destination is more nearly diagonal than a N's move is, then a K can outrun 2 Ns. First consider a K going diagonally. In 4 moves the player with the Ns can at best move each N twice, and at best advance it 3 squares in the right diagonal direction; meanwhile, the K can go 4. Even in 3 diagonal steps and 1 orthogonal one the K covers more distance in 4 moves than a N can in 2. So long as the general direction is near enough diagonal, the K can use such diagonal runs to outrun 2 Ns.
Answers.UserDisplayName: Rosie F
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-24T05:22:02.663Z
Answers.LastActivityDate: 2017-12-24T05:22:02.663Z
Answers.UserDisplayName: dumdidum
Answers.Body: <p>[Not exactly an answer, but just to address the related question of an infinite board that was brought up by some answers and comments.]</p>
  <p>Here is a proper proof that it is impossible on an infinite board, even if only the right side of the board is infinite. Assign each piece a distance that is simply the column number. Let the (opponent) king start with distance k at least 3 more than the distance of any knight. We maintain the invariant that (k−1)·2 &gt; m+n where m,n are the two greatest distances of the knights (with m = n if there are two knights at the greatest distance). Observe that each knight move adds at most 2 to m+n. Also, if the invariant holds then there cannot be two knights that can attack the column just on the right of the king, so the king can clearly move to an unattacked square while moving rightward, preserving the invariant. Since the king can continue indefinitely, it is impossible to checkmate the king.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-10T08:58:05.077Z
Answers.LastActivityDate: 2021-11-10T08:58:05.077Z
Answers.UserDisplayName: user21820
Body: <p>How many knights would be necessary to mate opponent's king on large finite boards, like a <strong>billion times a billion squares</strong>?</p>
  <p>Are they fast enough to surround the opponent's king in a <strong>constant</strong> number of times for various finite board sizes, or would you need some <strong>f(board size)</strong> of them, let's say millions for our board? Would there be a difference if attacking side could use it's king too?</p>
  <p>It's not clear how geometry works here, but it looks like when the king starts running, it's pretty fast and only two knights are fast enough to follow it. On the other hand, knights can build setups giving additional time for some distant colleague to join slowly. We start with king in the center and knights in one corner and 50 moves rule doesn't apply...</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-23T14:14:07.870Z
Comments.Text: *"when king starts running, it's pretty fast and only two knights are fast enough to follow him..."* since when kings are pretty fast and knights are the fastest pieces? :-) Joke aside, the question as it stands is very unclear, try to maybe formulate it more concretely. In any case, what you're imagining is infinite chess (in mathematics) and whether the king can be checkmated in finite number of moves, all very difficult questions both in game theory and mathematics in general. I highly recommend looking into the [works of Joel David Hamkins](http://jdh.hamkins.org/tag/infinite-chess/).
Comments.UserDisplayName: Ellie
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-23T14:18:42.460Z
Comments.Text: These kinds of questions are every now and then discussed on mathoverflow, for instance, somewhat related to your questions, see these posts and links therein: https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board , https://mathoverflow.net/questions/229732/can-one-make-high-level-proofs-about-chess-positions/229780#229780 , https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach
Comments.UserDisplayName: Ellie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-15T21:13:34.057Z
Comments.Text: What are the constraints on the starting position of the knights ? Can I use 6 knights to box the king in a 2x1 rectangle ? Then, the answer is 8 knights. If I can't, then how far off must the knights start ?
Comments.UserDisplayName: Jeffrey
Tags: <checkmate><puzzles><knights><mathematics>
Title: Knights necessary to mate king on large finite board
ThreadText: # Knights necessary to mate king on large finite board
  
  (Asked by: username_0 on 2017-12-23)
  
  How many knights would be necessary to mate opponent's king on large finite boards, like a **billion times a billion squares**?
  
  Are they fast enough to surround the opponent's king in a **constant** number of times for various finite board sizes, or would you need some **f(board size)** of them, let's say millions for our board? Would there be a difference if attacking side could use it's king too?
  
  It's not clear how geometry works here, but it looks like when the king starts running, it's pretty fast and only two knights are fast enough to follow it. On the other hand, knights can build setups giving additional time for some distant colleague to join slowly. We start with king in the center and knights in one corner and 50 moves rule doesn't apply...
  
  **Tags:** checkmate, puzzles, knights, mathematics
  
  > **Comments:**
  > **username_1**: *"when king starts running, it's pretty fast and only two knights are fast enough to follow him..."* since when kings are pretty fast and knights are the fastest pieces? :-) Joke aside, the question as it stands is very unclear, try to maybe formulate it more concretely. In any case, what you're imagining is infinite chess (in mathematics) and whether the king can be checkmated in finite number of moves, all very difficult questions both in game theory and mathematics in general. I highly recommend looking into the [works of Joel David Hamkins](http://jdh.hamkins.org/tag/infinite-chess/).  
  > **username_1**: These kinds of questions are every now and then discussed on mathoverflow, for instance, somewhat related to your questions, see these posts and links therein: https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board , https://mathoverflow.net/questions/229732/can-one-make-high-level-proofs-about-chess-positions/229780#229780 , https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach  
  > **username_2**: What are the constraints on the starting position of the knights ? Can I use 6 knights to box the king in a 2x1 rectangle ? Then, the answer is 8 knights. If I can't, then how far off must the knights start ?  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2019-10-15. Score: 4
  
  I think we can at least set a maximum for the number of knights needed.
  First off, the special cases. Checkmate is impossible on a 3x3 (or smaller) board. The knights cannot control the middle square and can thus never give checkmate. On a 4x4 board, the board is so small that if there are 4 knights and the king starts in the middle, the king is next to one of the knights and may be able to take it immediately and fork the remaining 3 for an easy draw, or if you move the king to the corner so it doesn't start in check, it starts the game immediately stalemated.
  In the following diagram, the black pawns represent squares that the king cannot cross:
  [FEN "3k4/8/8/ppp2ppp/2pppp2/NN4NN/8/8 w - - 0 1"]
  
  If you imagine that pattern continuing, each pair of knights is controlling 6 files.  So, to make a wall covering the entire board, you would need 2 knights for every 6 files. An additional 2 knights could ensure that the wall can slowly advance with no gaps. The wall can continue to advance until the opposing king is pinned to the back rank, and after that checkmate should be easy. So, on an NxN board of size at least 5, a maximum of ceiling(N/6) * 2 + 2 knights should be enough to checkmate. On a 300x300 board, which contains 90,000 squares, 102 knights would therefore be sufficient. (This implies a maximum of 6 knights needed on a regulation 8x8 board, which I'm pretty sure is more than what is actually needed - 4 seems like it would be enough.)
  There are probably better methods which could reduce this number, but I give it as a starting point.
  
  Are they fast enough to surround opponent's king in very limited constant count for various finite board sizes
  
  It could never be constant (and that part won't change even if the side with the knights also has a king.) After all, only 2 knights (or a king) can chase the king, and 2 knights (or a king... or even 2 knights and a king) cannot force checkmate, so at the very least the opposing king could run until it hit the edge of the board, and the amount of moves that takes is a function of the board size. Therefore, no checkmating method could be faster than O(N). The method I give of advancing a wall seems to be O(N^2) since the wall has further to go and takes longer to advance the bigger the board is.
  
  
  ---
  
  ### Answer by username_4 on 2017-12-24. Score: 4
  
  Not rigerous, however:
  
  1. In lateral movement two knights move as fast as one king.
  2. We know from end-game theory that two knights are not able to force the king into positions.
  
  .. thus I'd say it's very unlikely that unlimited knights+king would be able to mate a king that has a free direction to run in (unlimited board). If it's possible to corner it however (limited board and unlimited moves), unlimited knights are certainly enough, as they could simply divide up the board and slowly decrease the available space.
  
  > **Comments:**
  > **username_3**: "unlimited knights" makes no sense on a limited board; you can't have more knights than squares after all.  
  > **username_5**: Moreover, if the direction from the K's present square to its destination is more nearly diagonal than a N's move is, then a K can outrun 2 Ns. First consider a K going diagonally. In 4 moves the player with the Ns can at best move each N twice, and at best advance it 3 squares in the right diagonal direction; meanwhile, the K can go 4. Even in 3 diagonal steps and 1 orthogonal one the K covers more distance in 4 moves than a N can in 2. So long as the general direction is near enough diagonal, the K can use such diagonal runs to outrun 2 Ns.  
  
  ---
  
  ### Answer by username_6 on 2021-11-10. Score: 1
  
  [Not exactly an answer, but just to address the related question of an infinite board that was brought up by some answers and comments.]
  
  Here is a proper proof that it is impossible on an infinite board, even if only the right side of the board is infinite. Assign each piece a distance that is simply the column number. Let the (opponent) king start with distance k at least 3 more than the distance of any knight. We maintain the invariant that (k−1)·2 > m+n where m,n are the two greatest distances of the knights (with m = n if there are two knights at the greatest distance). Observe that each knight move adds at most 2 to m+n. Also, if the invariant holds then there cannot be two knights that can attack the column just on the right of the king, so the king can clearly move to an unattacked square while moving rightward, preserving the invariant. Since the king can continue indefinitely, it is impossible to checkmate the king.
  
  
  ---
  
  