# Topic Archive: infinite chess

Set theory seminarFriday, May 6, 201610:00 amGC 6417

# A position in infinite chess with game value $\omega^4$

LaGuardia Community College, CUNY

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$.

Set Theory DayFriday, March 11, 20163:30 pmGC 4102 (Science Center)

# A position in infinite chess with game value $\omega^4$

LaGuardia Community College, CUNY

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

Tuesday, April 30, 20134:00 pmYeshiva UniversityFurst Hall, Amsterdam Ave. & 185th Street.

# The theory of infinite games, with examples, including infinite chess

The City University of New York

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.

Set theory seminarFriday, March 1, 201312:00 amGC 5383

# The omega one of chess

The City University of New York

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$.

Set theory seminarFriday, May 18, 201212:00 amGC 6417

# The omega one of infinite chess

The City University of New York

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.

The City University of New York
Professor Hamkins (Ph.D. 1994 UC Berkeley) conducts research in mathematical and philosophical logic, particularly set theory, with a focus on the mathematics and philosophy of the infinite.  He has been particularly interested in the interaction of forcing and large cardinals, two central themes of contemporary set-theoretic research.  He has worked in the theory of infinitary computability, introducing (with A. Lewis and J. Kidder) the theory of infinite time Turing machines, as well as in the theory of infinitary utilitarianism and, more recently, infinite chess.  His work on the automorphism tower problem lies at the intersection of group theory and set theory.  Recently, he has been preoccupied with various mathematical and philosophical issues surrounding the set-theoretic multiverse, engaging with the emerging debate on pluralism in the philosophy of set theory, as well as the mathematical questions to which they lead, such as in his work on the modal logic of forcing and set-theoretic geology.