3

How many knights would be necessary to mate opponent's king on large finite boards like billion times billion squares?

Are they fast enough to surround opponent's king in very limited constant count 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 that when king starts running, it's pretty fast and only two knights are fast enough to followhim. 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...

  • 4
    "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. – Phonon Dec 23 '17 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/… – Phonon Dec 23 '17 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 supports Monica Oct 15 '19 at 21:13
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.

  • 1
    "unlimited knights" makes no sense on a limited board; you can't have more knights than squares after all. – D M Aug 25 '19 at 1:52
1

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.

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.