Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for every $n$?
This question is motivated by a question posed here a few months ago by Richard Stanley. He asked whether chess with finitely many pieces on $\mathbb{Z}^2$ is decidable.
A compactness observation is that if Black has only short-range pieces (no bishops, rooks or queens), then the statement "White can force mate" is equivalent to "There is some $n$ such that White can force mate in at most $n$ moves".
This probably won't lead to an answer to Stanley's question, because even if there are only short-range pieces, there is no general reason the game should be decidable. It is well-known that a finite automaton with a finite number of "counters" can emulate a Turing machine, and there seems to be no obvious reason why such an automaton could not be emulated by a chess problem, even if we allow only knights and the two kings.
But it might still be of interest to have an explicit counterexample to the idea that being able to force a win means being able to do so in some specified number of moves. Such an example must involve a long-range piece for the losing side, and one idea is that Black has to move a rook (or bishop) out of the way to make room for his king, after which White forces Black's king towards the rook with a series of checks, finally mating thanks to the rook blocking a square for the king.
If there are such examples, we can go on and define "mate in $\alpha$" for an arbitrary ordinal $\alpha$. To say that White has a forced mate in $\alpha$ means that White has a move such that after any response by Black, White has a forced mate in $\beta$ for some $\beta<\alpha$.
For instance, mate in $\omega$ means that after Black's first move, White is able to force mate in $n$ for some finite $n$, while mate in $2\omega + 3$ means that after Black's fourth move, White will be able to specify how many more moves it will take until he can specify how long it will take to mate.
With this definition, we can ask exactly how long-winded the solution to a chess problem can be:
What is the smallest ordinal $\gamma$ such that having a forced mate implies having a forced mate in $\alpha$ for some $\alpha<\gamma$?
Obviously $\gamma$ is infinite, and since there are only countably many positions, $\gamma$ must be countable. Can anyone give better bounds?
Best Answer
Here is my first try at a solution. Your idea was a good one, but bishops are better than rooks, I surmise.
The two pictures here are placed in some distinct parts of the infinite board. The first just ensures it is White to move (in check), and that White's king will never play a role, as capturing a black unit, which are nearly stalemated as is, will release heavy pieces.
alt text http://www.freeimagehosting.net/uploads/3c8e277e7d.jpg alt text http://www.freeimagehosting.net/uploads/72ef1c9b7e.jpg
So White is left to checkmate with the four bishops and pawns. White threatens checkmate via a check from below on the northwest diagonal, and Black can only avoid this by moving the bishop northeast some amount. Upon Black moving this bishop, White then makes the bishop check anyways, the Black king moves where the Black bishop was, the pawn moves with check, the Black king again retreats northeast along the diagonal, and then White alternately moves the dark-square bishops, giving checks until the Black bishop is reached when it is mate.
The point of this second picture is that White cannot checkmate Black unless the Black bishop plays a role. Four bishops are not enough to checkmate a king on an infinite board, and hopefully I have set it up so that the White pawns play no part once Black starts the king running northeast. Pawns are not too valuable when they cannot become queens.
In extended chess notation, White plays 1. Ke5 on board A, then Black plays 1...Bz26 on board B, followed by 2. Bg3+ Kf6 3. e5+ Kg7 3. Bi5+ Kh8 4. Bf10+ Ki9 5. Bk7+ Kj10 6. Bh12+ ..., as White successively cuts off NW-SE diagonals until the Black bishop is reached. By moving the bishop X squares northeast on move 1, Black can delay the checkmate for X moves, if I set this up proper.
Other plans by White should be beatable by moving the Black king off the long diagonal or capturing the light White bishop with the pawn. Once Black's king exits the area with the pawns, the Black bishop must be a part of the mating pattern. I don't think the Black king can be forced back to that area.
Well, this is a first try.