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

[bibtex key=BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable]

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?

15 thoughts on “The mate-in-n problem of infinite chess is decidable

    • Thanks, Sam. You might be interested to hear that we have another paper coming soon, by myself and Cory Evans (US chess master), in which we investigate $\omega_1^{\frak{Ch}}$. In particular, one of the theorems we have is that the in three-dimensional infinite chess, there are positions realizing any countable ordinal game value. So the $\omega_1^{\frak{Ch}}$ of infinite positions in three-dimensional infinite chess is true $\omega_1$. Unfortunately, we can’t fit the positions into two dimensions, although of course we would like to do so.

    • From the Wikipedia article on game theory: “In 1913, Ernst Zermelo published Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels (On an Application of Set Theory to the Theory of the Game of Chess). It proved that the optimal chess strategy is strictly determined.”

      • Yes, of course, Zermelo’s theorem. I’ve taken to attributing to Zermelo what I call the “Fundamental theorem of finite games,” namely, the assertion that in every finite two-player game of perfect information, either one of the players has a winning strategy or both players have drawing strategies. Zermelo’s argument nearly establishes this, although he was concerned with games like chess that had only finitely many game states, rather than games that always end in finitely many moves (and these are not quite the same thing). More contemporary proofs establish clopen determinacy and lead directly to the open determinacy result of the Gale-Stewart theorem.

  1. Pingback: Infinite chess: the mate-in-n problem is decidable and the omega-one of chess, Cambridge, March 2012 | Joel David Hamkins

  2. Pingback: The omega one of infinite chess, New York, 2012 | Joel David Hamkins

  3. Pingback: The mate-in-n problem of infinite chess is decidable, Cambridge, June 2012 | Joel David Hamkins

  4. Pingback: Infinite chess and the theory of infinite games, Dartmouth Mathematics Colloquium, January 2014 | Joel David Hamkins

  5. Pingback: Transfinite game values in infinite chess and other infinite games, Hausdorff Center, Bonn, May 2014 | Joel David Hamkins

  6. Pingback: The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014 | Joel David Hamkins

  7. Pingback: An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014 | Joel David Hamkins

  8. Pingback: A position in infinite chess with game value $omega^4$ | Joel David Hamkins

  9. Pingback: Transfinite game values in infinite chess, including new progress | Joel David Hamkins

  10. Pingback: Transfinite game values in infinite chess, including new progress, Bonn, January 2017 | Joel David Hamkins

Leave a Reply

Your email address will not be published. Required fields are marked *