[Math] Math and Logic of Infinite Chess

combinatorial-game-theoryinfinite-gamesrecreational-mathematics

Two players (White and Black) are playing on an infinite chess board (extending infinitely in all directions).

First, White places a certain number of queens (and no other pieces) on the board.

Second, Black places a king on any unoccupied, unattacked square of the board.

Then, both players take turns moving until Black is checkmated.

What is the minimum number of queens White needs to force a checkmate?

Answer the same problem if White starts with rooks instead of queens.

Do the same for bishops and knights.

Let $Q, R, B$, and $N$ be the minimum number of queens, rooks, bishops, and knights, respectively. What is the sum $1/Q + 1/R + 1/B + 1/N$?

Best Answer

Queens. Two queens suffice, as pointed out in the comments of Sp3000.

Rooks. Three rooks suffice, by trapping the black king between two walls, and then using the third rook to slowly close the gap between the walls. If the black king approach a rook, simply move it on the same file but further away. Two rooks do not suffice, since there is no check-mate position with two white rooks and a black king.

Bishops. Six bishops suffice, with three of each color. White can use a pair of bishops to form a wall, and thus with two pairs white can trap the black king between two walls, which gradually close and deliver checkmate with the fifth or sixth (whichever color is needed). If the black king approaches a bishop, simply move it away on the same diagonal. Five bishops do not suffice, since the black king can simply stay on the color having at most two bishops of that color, and there will always be a square available, since double check will not arise.

Knights. No finite number of white knights will suffice in this game. To see this, observe first that two white knights do not suffice, since one cannot set up a check-mated position. Now, suppose white places finitely many knights on the board. Black need only place his king on a file completely to the right of those pieces. Black's strategy is simply to move steadily to the right (that is, his every move should involve a rightward horizontal movement). Since knights move at most two units to the right, white will not be able to keep more than two knights in the vicinity of the black king, and indeed, will not be able to bring two knights so close. With one knight, to be sure, white can move at double speed and catch up to the black king; but to bring two knights close to the king, each would have had to move at a greater than one unit to the right speed, which is not possible. Finally, notice that with infinitely many knights, we can fill up the board almost completely, leaving only a few empty spots, and easily set a trap for black this way.

Conclusion. So we have $Q=2$, $R=3$, $B=6$ and $N=\infty$, giving $$\frac{1}{Q}+\frac1R+\frac1B+\frac1N=\frac12+\frac13+\frac16+\frac1{\infty}=1.$$