The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an infinite board decidable? In other words, given a position on an infinite board (say $\mathbb{Z}\times \mathbb{Z}$, though now pawn promotion is not possible) with finitely many men, say with White to move, is there an algorithm to determine whether White can checkmate Black (or prevent Black from checkmating White) against any Black defense?
[Math] Decidability of chess on an infinite board
chesscombinatorial-game-theoryinfinite-gameslo.logic
Related Solutions
Here is a summary of solution proposed in this arXiv paper. A pair of positions on the $n\times n$ chessboard is constructed for which (1) there is a sequence $\sigma$ of legal chess moves leading from $P$ to $P'$; (2) the length of $\sigma$ cannot be less than $\exp\Theta(n)$.
The idea is to construct a position which consists essentially of $m$ tracks each of which is in some state in every moment. The set of possible states of $i$th track is a cycle group of order equal to $(i+3)$rd prime, and the position is defined uniquely by states of all tracks. A "move" increases every state by $1$ or decreases every state by $1$. Transforming $(0,0,\ldots,0)$ to $(1,0,\ldots,0)$ is possible by Chinese remainders but requires at least $p_5\ldots p_{m}=\exp(p_m+o(p_m))$ "moves".
(source)
The chess positions representing tracks use the above pattern, which is a specific example corresponding to $m=3$. The dots denote pawns, and we assume that the kings are located somewhere else on the board. In the paper it is explained (in different terms) why we can think of dark cycles as tracks, the positions of white bishops on them as states, and "moves" as minimal sequences of legal chess moves whose initial and resulting positions coincide up to a color of pieces.
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.
Best Answer
There is a positive solution for the decidability of the mate-in-$n$ version of the problem.
Many of us are familiar with the White to mate in 3 variety of chess problems, and we may consider the natural analogue in infinite chess. Thus, we refine the winning-position problem, which asks whether a designated player has a winning strategy from a given position, to the mate-in-$n$ problem, which asks whether a designated player can force a win in at most $n$ moves from a given finite position. (And note that as discussed in Johan Wästlunds's question checkmate in $\omega$ moves?, there are finite winning positions in infinite chess which are not mate-in-$n$ for any finite $n$.) Even so, the mate-in-$n$ problem appears still to be very complicated, naturally formulated by assertions with $2n$ many alternating quantifiers: there is a move for white, such that for every black reply, there is a countermove by white, and so on. Assertions with such quantifier complexity are not generally decidable, and one cannot expect to search an infinitely branching game tree, even to finite depth. So one might naturally expect the mate-in-$n$ problem to be undecidable.
Despite this, the mate-in-n problem of infinite chess is computably decidable, and uniformly so. Dan Brumleve, myself and Philipp Schlicht have just submitted an article establishing this to the CiE 2012, and I hope to speak on it there in June.
The solution can also be cast in terms of Presburger arithmetic, in a manner close to Dan Brumleve's answer to this question. Namely, once we restrict to a given collecton of pieces $A$, then we may represent all positions using only pieces in $A$ as a fixed-length tuple of natural numbers, and the elementary movement, attack and in-check relations are expressible for this representation in the language of Presburger arithmetic, essentially because the distance pieces---rooks, bishops and queens---all move on straight lines whose equations are expressible in Presburger arithmetic. (There is no need to handle sequence coding in general, since the number of pieces does not increase during play.) Since the mate-in-$n$ problem is therefore expressible in Presburger arithmetic, it follows that it is decidable.