4

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...

3
  • 5
    "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.
    – Ellie
    Dec 23, 2017 at 14:14
  • 4
    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: mathoverflow.net/questions/27967/… , mathoverflow.net/questions/229732/… , mathoverflow.net/questions/27944/…
    – Ellie
    Dec 23, 2017 at 14:18
  • 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 ?
    – Jeffrey
    Oct 15, 2019 at 21:13

3 Answers 3

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.

2
  • 1
    "unlimited knights" makes no sense on a limited board; you can't have more knights than squares after all.
    – D M
    Aug 25, 2019 at 1:52
  • 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.
    – Rosie F
    Nov 12, 2021 at 17:42
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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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