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.
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.
D. Brumleve, J. D. Hamkins and P. Schlicht, "The mate-in-n problem of infinite
chess is decidable," 10 pages, arxiv pre-print, submitted to CiE 2012.
Abstract. Infinite chess is chess played on an infinite
edgeless chessboard. The familiar chess pieces move about according
to their usual chess rules, and each player strives to place the
opposing king into checkmate. The mate-in-$n$ problem of infinite
chess is the problem of determining whether a designated player can
force a win from a given finite position in at most n moves. A
naive formulation of this problem leads to assertions of high
arithmetic complexity with $2n$ alternating quantifiers---there is
a move for white, such that for every black reply, there is a counter-move
for white, and so on. In such a formulation, the problem does not
appear to be decidable; and one cannot expect to search an
infinitely branching game tree even to finite depth. Nevertheless,
the main theorem of this article, confirming a conjecture of the
first author and C. D. A. Evans, establishes that the mate-in-$n$
problem of infinite chess is computably decidable, uniformly in the
position and in $n$. Furthermore, there is a computable strategy
for optimal play from such mate-in-$n$ positions. The proof
proceeds by showing that the mate-in-$n$ problem is expressible in
what we call the first-order structure of chess $\frak{Ch}$, which
we prove (in the relevant fragment) is an automatic structure,
whose theory is therefore decidable. Unfortunately, this resolution
of the mate-in-$n$ problem does not appear to settle the
decidability of the more general winning-position problem, the
problem of determining whether a designated player has a winning
strategy from a given position, since a position may admit a
winning strategy without any bound on the number of moves required.
This issue is connected with transfinite game values in infinite
chess, and the exact value of the omega one of chess $\omega_1^{\rm
chess}$ is not known.
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.
Best Answer
Here's an "irreversible chess" construction that's fundamentally different from the ones so far based on Ed Dean's scheme. The essential pieces and pawns are in boldface:
Position A: White Kh1, Ra1, Nd1, pawns b2,b3,c3,d2,e3,f2,g2,h7, Bg8; Black Kh8, Bb1, Bg1, pawns f7,g7,h2.
(source: janko.at)
Position D = Position A after 1...Ba2 2 Rc1 Bb1, i.e. with the Rook on c1 and White to move:
(source: janko.at)
I call it D rather than B because the two intermediate positions can be called B and C, and then each arrow in A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D is irreversible. [This was also possible in some of the previous examples, including Ed's original one; I don't think we've seen "A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D $\rightarrow$ E" yet.]
In Position A, the rook and a1 and bishop on b1 can reversibly roam the board. But after 1...Ba2 (Position B) the only locally reversible continuation is 2 Rc1 (Position C; if 2 Rb1 Black has no reversible reply) 2...Bb1 (Position D) 3 Rc2 Ba2 4 Rc1 Bb1 and we're back to D; the White rook and Black bishop can no longer escape the corner because they keep getting in each other's way.
The previous constructions all exploit the special behavior of kings, which must not be in check on the opponents' move. This new approach does not need kings at all — it would still work if we removed the kings and their un-boldfaced retinues, except that the problem as posed required each side to have a king. The key ingredient here instead of the check rule is move alternation: if either side were allowed to skip a turn it would be easy to get back to Position A — whereas in several of the check-based constructions, skipping turns would not help as long as neither side is allowed to make a move (even as part of an unanswered series) that leaves its own king in check.