Guaranteed Checkmate with Rooks in High-Dimensional Chess

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb Z^n$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite number of moves?

To avoid trivial exceptions, assume the king starts a very large distance away from the nearest rook.

Rooks can change one coordinate to anything. King can change any set of coordinates by one.

And same problem with i) Bishops and ii) Queens, in place of rooks.

In 3-dimensional chess, it is possible to force checkmate starting with a finite number of rooks. As this fact still appears to be open, I'll post a method of forcing checkmate with 96 rooks, even though it should be clear that this is not optimal. You can remove some of the rooks from the method I'll give below, but I am aiming for a simple explanation of the method rather than the fewest possible number of rooks.

First, we move all of the rooks far away in the $z$ direction, so that they cannot be threatened by the king. We also move each of the rooks so that they all have distinct $z$ coordinates. That way, they are free to move any number of steps in the $x$ and $y$ directions without blocking each other. The king will be in check whenever it has the same $(x,y)$-coordinate as one of the rooks. We can project onto the $(x,y)$-plane to reduce it to a 2-dimensional board. Looked at this way, each rook can move any number of places in the $x$ or $y$ direction (and can pass through each other, can pass through the king, and you can multiple rooks in the same $(x,y)$-square). The king is in check if it is on the same square as a rook.

First, I'll describing the following "blocking move" to stop the king passing a given horizontal (or vertical) line.

In the position above, the right-most 3 rooks are stopping the king moving past the red line on the next move. Then, once the king moves, do the following. (i) If the king's $x$-coordinate does not change, do nothing. (ii) If the king's $x$-coordinate increases by one, move the left-most rook so that it is to the right of the other three. Then you are back in the same position, just moved along by one step. (iii) If the king's $x$-coordinate decreases by one step, do nothing. We are back in the same situation, except reflected (so, keep performing the same steps, but reflected in the $x$-direction on subsequent moves).

This way, we chase the king along the red line, but he can never cross it. Furthermore, if the king changes from going right to going left, we have a free move to do something elsewhere on the board. Actually, for this to work, if the king is in column $i$, we just need three rooks at positions $i-1,i,i+1$ on the row above the red line, and one more at any other position on the row. Next, if we have 4 rooks stationed somewhere on the given horizontal row, how many moves does it take to move them into the blocking position? The answer is 6. You first move one rook to have the same $x$-coordinate as the king (say, $x=i$). After the king moves, by reflection we can assume he keeps the same $x$-coordinate or moves one to the right. Then, move the next rook to position $i+2$. Then, after the next move, move a rook to position $i-2$ or $i+4$ in such a way that we have three rooks on the row, with one space between each of them, and the kings is in one of the 3 middle columns. Say, the rooks are at positions $j-2,j,j+2$ and the king is in column $j-1,j$ or $j+1$. If the king moves to column $j-1$ or $j+1$ we just move the 4th rook to this position and we have attained the blocking position. If the king moves to column $j$, we move the rook in position $j-2$ to position $j-1$ and, on the next move, we can move the 4th rook in to attain the blocking position. If the king moves to column $j+2$, we move the rook in column $j-2$ to $j+4$, then we are in the position above where there are rooks at positions $k-2,k,k+2$ and the king in position $k$, so it takes 2 more moves to attain the blocking position.

So, we just need to keep 4 rooks stationed along the row which we wish to block the king from crossing. Whenever he moves within 6 steps from this row, start moving the rooks into the blocking position, and he can never step into the given row.

Now, choose a large rectangle surrounding the king, and position 15 rooks in each corner as below.

Also, position 4 rooks in arbitrary positions along each edge of the rectangle. So, that's $4\times15+4\times4=76$ rooks used so far. I puposefully left some of the board blank in the diagram above. The point is to not specify exactly how big the rectangle is. It doesn't matter, just so long as it is large enough to be able to move the 76 rooks into position before the black king can get within 6 steps of any of the edges of the rectangle.

Now, once we are in this position, then whenever the black king moves within one of the red rectangles, use the 4 rooks positioned along the adjacent edge to perform the blocking move as described above to stop the king crossing that edge. We can keep doing this, and imprison the black king within the big rectangle. Furthermore, we keep getting free moves to do something else whenever the king moves out of the red rectangles, or whenever he changes direction within a red rectangle. Also, if the king is in one of the inside corners of a red rectangle, there is already a rook in the corresponding position at the adjacent edge of the big rectangle, giving us a free move.

Now, suppose that we have an extra 20 rooks. During the free moves we get while chasing the king around the edge of the big square, we can move these to any position we like. With 20 rooks, we can position 16 of to the left of each of the 16 rooks near the right-hand corners of the big rectangle which have an empty square to their left. Also, position 4 rooks along the column one step to the left of the right-hand edge of the big rectangle. This way, we create a new rectangle one square smaller in the $x$-direction. If the king ever enters the right-hand red rectangle or one step to the left of this, we use the new 4 blocking rooks to stop him from reaching the right-hand edge of the new big rectangle. If he is already within the red rectangle, and stays there then, when we get a free move, we can move one of the new blocking rooks to the position one above or below the row in which the king is. Then we can bring the other 3 rooks in, blocking him out of this column. In this way, we create a new big rectangle one step smaller in the $x$-direction and with the king still trapped inside. Similarly, we can reduce the height of the big rectangle by 1. Repeat this, enclosing the king in ever smaller rectangles until, eventually, he gets trapped in the single square within a 3x3 rectangle surrounded by 8 rooks. Then bring one of the other rooks in to cover this square, which is checkmate.

As the beginnings of an impossibility proof, let's consider the possibility of blocking off one direction of motion to the king in three dimensions. Consider the following game:

.............
 ...........
  .........
   .......
    .....
     ...
      K

Each turn, you get to place one # on the top row, and then the king gets to move his K one space forward, either straight or diagonally, but cannot pass through a #. If the K reaches the back row, you lose. This game is actually winnable with this size grid or larger, but not with a smaller grid.

How does this compare to the chess game? Well, if we just consider one direction of motion, we can project from 3 dimensions down to two. If the king is not in the same plane as any of your rooks, then each of your rooks can block off a single square in the projected game.

Unfortunately, you can't really guarantee being able to place one rook per turn in the correct position (and don't forget in the real game, we are trying to block 3 directions of motion at once!) So now consider the same game, but the king gets to make two moves for every move you make.

I don't think you can win this version of the game.

Now, a better version of the game would be to let you place one # per turn anywhere, and the king gets two moves (or less, if he wants) per turn in any direction. I don't know if this game might be winnable; it's not quite the Conway Angel problem that was mentioned (jumping isn't allowed).

But again, you're trying to bound the king in three directions at once. So you're playing three games at once, and on your turn you get to place one piece on any of the three boards, but your opponent gets two moves (or less if he likes) on all boards at once. It seems... unlikely that this game is winnable.

So, in order to actually force a checkmate, you're going to have to do one of:

• Take some advantage of the initial arrangement of your rooks
• Find some way to make useful moves on two or three of the projected boards at once
• Get your rooks in the same plane as the king frequently enough to be meaningful

It's not clear that this can be done.

Update: you don't need to win in 3 directions at once, just two. More precisely, consider a game on an infinite two-dimensional grid where you have pieces # and your opponent has a piece K. You and your opponent alternate turns, and the rules are:

• You can move a # horizontally or vertically any distance.
• You are allowed to move a # onto the K.
• Your opponent can move one space in any of the 8 directions or remain still.
• Your opponent is not allowed to end his turn on a #.

You win if your opponent has no legal moves. If you can win this game in N moves with M #'s, then you can force a checkmate as follows:

• Imagine the above two-dimensional grid as a projection of the three-dimensional chessboard.
• Move your rooks vertically 2M + N + lots more spaces away from the king, all with different vertical coordinates.
• Play the above game, where the #'s are rooks and the K is the king.

If you can build walls quickly enough in just two dimensions, of course, that would give a winning strategy for the above game (given enough #'s): wall in the K, then move #'s to fill all of the interior squares.

Here is a rough sketch of how I think it goes. Clearly $3^{d-1}$ rooks can always create a checkmate situation in a finite number of moves.

Now suppose that we have $3^{d-1} - 1$ rooks and that the king is in check by one of them. We must show that the king can always escape.

Now there are at most $3^d - 1$ possible moves for the king in general. But the king is in check by one rook, so that actually the king has $3^d - 3$ possible moves (ignoring the position of the other rooks).

But the other $3^{d-1} - 2$ rooks can threaten at most $3$ adjacent squares of the king each (by the linear nature of the rooks attack) so that at most $3^d - 6$ of the $3^d - 3$ squares can be threatened. Thus there must exist squares adjacent to the king that are not threatened by any of the rooks.