This talk is a more detailed version of the presentation that I gave on set theory day.

I present a position in infinite chess with game value $\omega^4$. Informally speaking, this means that one side can force a win in $\omega^4$ many moves, or that the game is equivalent to the game of counting down from $\omega^4$. This result, joint with Hamkins and Evans, improved on the previous best result of $\omega^3$.

I present a position in infinite chess with game value $\omega^4$. Informally speaking, this means that one side can force a win in $\omega^4$ many moves, or that the game is equivalent to the game of counting down from $\omega^4$. This result, joint with Hamkins and Evans, improved on the previous best result of $\omega^3$.

Slides

More information can be found at: http://jdh.hamkins.org/tag/infinite-chess.

This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the Yeshiva University Philosophy Club. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers. What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game? Is there any reason to think that every game should have a winning strategy for one player or another? Could there be a game, such that neither player has a way to force a win? Must every computable game have a computable winning strategy? I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.

This talk will be based on my recent paper with C. D. A. Evans, Transfinite game values in infinite chess.

Infinite chess is chess played on an infinite chessboard.  Since checkmate, when it occurs, does so after finitely many moves, this is technically what is known as an open game, and is therefore subject to the theory of open games, including the theory of ordinal game values.  In this talk, I will give a general introduction to the theory of ordinal game values for ordinal games, before diving into several examples illustrating high transfinite game values in infinite chess.  The supremum of these values is the omega one of chess, denoted by $omega_1^{mathfrak{Ch}}$ in the context of finite positions and by $omega_1^{mathfrak{Ch}_{hskip-2ex atopsim}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we have specific positions with transfinite game values of $omega$, $omega^2$, $omega^2cdot k$ and $omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $omega_1$.

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, in joint work with Dan Brumleve and Philipp Schlicht, confirming a conjecture of myself and C. D. A. Evans, we establish 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. An equivalent account of the result arises from the realization that the structure of chess is interpretable in the standard model of Presburger arithmetic $langlemathbb{N},+rangle$. 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. I will also discuss recent joint work with C. D. A. Evans and W. Hugh Woodin showing that the omega one of infinite positions in three-dimensional infinite chess is true $omega_1$: every countable ordinal is realized as the game value of such a position.