  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, which we prove (in the relevant fragment)
is an automatic structure, whose theory is therefore decidable. Indeed, it is
definable in Presburger arithmetic. 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 is not known.
