The mate-in-n problem of infinite chess is decidable, Cambridge, June 2012

This will be a contributed talk at the Turing Centenary Conference CiE 2012 held June 18-23, 2012 in Cambridge, UK.

Abstract.  The mate-in-$n$ problem of infinite chess—chess played on an infinite edgeless board—is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. Although a straightforward formulation of this problem leads to assertions of high arithmetic complexity, with $2n$ alternating quantifiers,  the main theorem of this article nevertheless confirms a conjecture of the second author and C. D. A. Evans by establishing that it 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. The structure is also 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 $\omega_1^{\rm chess}$ is not known.

Article | Slides | CiE 2012 | Contributed talk schedule

The mate-in-n problem of infinite chess is decidable

  • D. Brumleve, J. D. Hamkins, and P. Schlicht, “The Mate-in-$n$ Problem of Infinite Chess Is Decidable,” in How the World Computes, S. Cooper, A. Dawar, and B. Löwe, Eds., Springer Berlin Heidelberg, 2012, vol. 7318, pp. 78-88.  
    @incollection{BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable,
    year= {2012}, isbn= {978-3-642-30869-7}, booktitle= {How the World Computes},
    volume= {7318}, series= {Lecture Notes in Computer Science}, editor= {Cooper,
    S.~Barry and Dawar, Anuj and L{\"o}we, Benedikt}, doi=
    {10.1007/978-3-642-30870-3_9}, title= {The Mate-in-$n$ Problem of Infinite
    Chess Is Decidable}, url= {http://dx.doi.org/10.1007/978-3-642-30870-3_9},
    publisher= {Springer Berlin Heidelberg}, author= {Brumleve, Dan and Hamkins,
    Joel David and Schlicht, Philipp}, pages= {78-88},
    eprint = {1201.5597},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

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 countermove 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. 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^{\frak{Ch}}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?