Transfinite game values in infinite chess, including new progress, Bonn, January 2017

This will be a talk January 10, 2017 for the Basic Notions Seminar, aimed at students, post-docs, faculty and guests of the Mathematics Institute, University of Bonn.

Bishop gateway terminals

Bishop cannon

 

 

 

 

 

 

 

 

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess — chess played on an infinite edgeless chessboard — as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question.  This talk will include some of the latest progress, which includes a position with game value $\omega^4$.

It happens that I shall be in Bonn also for the dissertation defense of Regula Krapf, who will defend the same week, and who is one of the organizers of the seminar.

Transfinite game values in infinite chess | The mate-in-$n$ problem of infinite chess is decidable | A position in infinite chess with game value $\omega^4$ | more on infinite chess | Slides

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

  • C.~D.~A.~Evans, J. D. Hamkins, and N. L. Perlmutter, “A position in infinite chess with game value $\omega^4$,” to appear in Integers, vol. 17, 2017. (Newton Institute preprint ni15065)  
    @ARTICLE{EvansHamkinsPerlmutter:APositionInInfiniteChessWithGameValueOmega^4,
    author = {C.~D.~A.~Evans and Joel David Hamkins and Norman Lewis Perlmutter},
    title = {A position in infinite chess with game value $\omega^4$},
    journal = {to appear in Integers},
    FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
    year = {2017},
    volume = {17},
    number = {},
    pages = {},
    eprint = {1510.08155},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/a-position-in-infinite-chess-with-game-value-omega-to-the-4},
    month = {},
    note = {Newton Institute preprint ni15065},
    abstract = {},
    keywords = {},
    source = {},
    }

Abstract.  We present a position in infinite chess exhibiting an ordinal game value of $\omega^4$, thereby improving on the previously largest-known values of $\omega^3$ and $\omega^3\cdot 4$.

This is a joint work with Cory Evans and Norman Perlmutter, continuing the research program of my previous article with Evans, Transfinite game values in infinite chess, namely, the research program of finding positions in infinite chess with large transfinite ordinal game values. In the previous article, Cory and I presented a position with game value $\omega^3$. In the current paper, with Norman Perlmutter now having joined us accompanied by some outstanding ideas, we present a new position having game value $\omega^4$, breaking the previous record.

Full position value omega^4

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

In the new position, above, the kings sit facing each other in the throne room, an uneasy détente, while white makes steady progress in the rook towers. Meanwhile, at every step black, doomed, mounts increasingly desperate bouts of long forced play using the bishop cannon battery, with bishops flying with force out of the cannons, and then each making a long series of forced-reply moves in the terminal gateways. Ultimately, white wins with value omega^4, which exceeds the previously largest known values of omega^3.

In the throne room, if either black or white places a bishop on the corresponding diagonal entryway, then checkmate is very close. A key feature is that for white to place a white-square white bishop on the diagonal marked in red, it is immediate checkmate, whereas if black places a black-square black bishop on the blue diagonal, then checkmate comes three moves later.  The bishop cannon battery arrangement works because black threatens to release a bishop into the free region, and if white does not reply to those threats, then black will be three steps ahead, but otherwise, only two.

           The throne room

The rook towers are similar to the corresponding part of the previous $\omega^3$ position, and this is where white undertakes most of his main line progress towards checkmate.  Black will move the key bishop out as far as he likes on the first move, past $n$ rook towers, and the resulting position will have value $\omega^3\cdot n$.  These towers are each activated in turn, leading to a long series of play for white, interrupted at every opportunity by black causing a dramatic spectacle of forced-reply moves down in the bishop cannon battery.

Rook towers

            The rook towers

At every opportunity, black mounts a long distraction down in the bishop cannon battery.  Shown here is one bishop cannon. The cannonballs fire out of the cannon with force, in the sense that when each green bishop fires out, then white must reply by moving the guard pawns into place.

Bishop cannon

Bishop cannon

Upon firing, each bishop will position itself so as to attack the entrance diagonal of a long bishop gateway terminal wing.  This wing is arranged so that black can make a series of forced-reply threats successively, by moving to the attack squares (marked with the blue squares). Black is threatening to exit through the gateway doorway (in brown), but white can answer the threat by moving the white bishop guards (red) into position. Thus, each bishop coming out of a cannon (with force) can position itself at a gateway terminal of length $g$, making $g$ forced-reply moves in succession.  Since black can initiate firing with an arbitrarily large cannon, this means that at any moment, black can cause a forced-reply delay with game value $\omega^2$. Since the rook tower also has value $\omega^2$ by itself, the overall position has value $\omega^4=\omega^2\cdot\omega^2$.

Bishop gateway terminal wing

With future developments in mind, we found that one can make a more compact arrangement of the bishop cannon battery, freeing up a quarter board for perhaps another arrangement that might lead to a higher ordinal values.

Alternative compact version of bishop cannon battery

 

Read more about it in the article, which is available at the arxiv (pdf).

 

See also:

An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014


This will be a talk for the interdisciplinary Group in Philosophical and Mathematical Logic at the University of Connecticut in Storrs, on December 5, 2014.

Value omega cubedAbstract. I shall give a general introduction to the theory of infinite games, with a focus on the theory of transfinite ordinal game values. These ordinal game values can be used to show that every open game — a game that, when won for a particular player, is won after finitely many moves — has a winning strategy for one of the players. By means of various example games, I hope to convey the extremely concrete game-theoretic meaning of these game values for various particular small infinite ordinals. Some of the examples will be drawn from infinite chess, which is chess played on a chessboard stretching infinitely without boundary in every direction, and the talk will include animations of infinite chess positions having large numbers of pieces (or infinitely many) with hundreds of pieces making coordinated attacks on the chessboard. Meanwhile, the exact value of the omega one of chess, denoted $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, is not currently known.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014

Releasing the hordesI shall speak at the Virginia Commonwealth University Math Colloquium on November 21, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite chessboard stretching without bound in every direction—as a central example. Since chess, when won, is always won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values, which provide a measure in a position of the distance remaining to victory. I shall exhibit several interesting positions in infinite chess with very high transfinite ordinal game values. Some of these positions involve large numbers of pieces, and the talk will include animations of infinite chess in play, with hundreds of pieces (or infinitely many) making coordinated attacks on the board. Meanwhile, the precise ordinal value of the omega one of chess is an open mathematical question.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

Transfinite game values in infinite chess and other infinite games, Hausdorff Center, Bonn, May 2014

Releasing the hordesI shall be very pleased to speak at the colloquium and workshop Infinity, computability, and metamathematics, celebrating the 60th birthdays of Peter Koepke and Philip Welch, held at the Hausdorff Center for Mathematics May 23-25, 2014 at the Universität Bonn.  My talk will be the Friday colloquium talk, for a general mathematical audience.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite edgeless chessboard—as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question.

 

Slides | Schedule | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

Infinite chess and the theory of infinite games, Dartmouth Mathematics Colloquium, January 2014

Releasing the hordesThis will be a talk for the Dartmouth Mathematics Colloquium on January 23rd, 2014.

Dartmouth Green

Abstract. Using infinite chess as a central example—chess played on an infinite edgeless board—I shall give a general introduction to the theory of infinite games. Infinite chess is an example of what is called an open game, a potentially infinite game which when won is won at a finite stage of play, and every open game admits the theory of transfinite ordinal game values. These values provide a measure of the distance remaining to an actual victory, and when they are known, the game values provide a canonical winning strategy for the winning player. I shall exhibit

several interesting positions in infinite chess with high transfinite game values. The precise value of the omega one of chess, however, the supremum of all such ordinal game values, is an open mathematical question; in the case of infinite three-dimensional chess, meanwhile, Evans and I have proved that every countable ordinal arises as a game value. Infinite chess also illustrates an interesting engagement with computability issues. For example, there are computable infinite positions in infinite chess that are winning for white, provided that the players play according to a computable procedure of their own choosing, but which is no longer winning for white when non-computable play is allowed. Also, the mate-in-n problem for finite positions in infinite chess is computably decidable (joint work with Schlicht, Brumleve and myself), despite the high quantifier complexity of any straightforward representation of it. The talk will be generally accessible for mathematicians, particularly those with at least rudimentary knowledge of ordinals and of chess.

Poster | Slides (8mb) | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

The theory of infinite games, with examples, including 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.  The event will take place in 5:45 pm in Furst Hall, on the corner of Amsterdam Ave. and 185th St.

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

NYlogic entry | Yeshiva University | Infinite chess | Video

 

The omega one of chess, CUNY, March, 2013

This is a talk for the New York Set Theory Seminar on March 1, 2013.

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-1.5ex {\ \atop\sim}}}$ 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^2\cdot 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$.

Transfinite game values in infinite chess

  • C.~D.~A.~Evans and J. D. Hamkins, “Transfinite game values in infinite chess,” Integers, vol. 14, p. Paper No.~G2, 36, 2014.  
    @ARTICLE{EvansHamkins2014:TransfiniteGameValuesInInfiniteChess,
    AUTHOR = {C.~D.~A.~Evans and Joel David Hamkins},
    TITLE = {Transfinite game values in infinite chess},
    JOURNAL = {Integers},
    FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
    YEAR = {2014},
    volume = {14},
    number = {},
    pages = {Paper No.~G2, 36},
    month = {},
    note = {},
    eprint = {1302.4377},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/game-values-in-infinite-chess},
    ISSN = {1553-1732},
    MRCLASS = {03Exx (91A46)},
    MRNUMBER = {3225916},
    abstract = {},
    keywords = {},
    source = {},
    }

In this article, C. D. A. Evans  and I investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values—the omega one of chess—denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot 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$.

The article is 38 pages, with 18 figures detailing many interesting positions of infinite chess. My co-author Cory Evans holds the chess title of U.S. National Master.

Wästlund’s MathOverflow question | My answer there

Let’s display here a few of the interesting positions.

First, a simple new position with value $\omega$.  The main line of play here calls for black to move his center rook up to arbitrary height, and then white slowly rolls the king into the rook for checkmate. For example, 1…Re10 2.Rf5+ Ke6 3.Qd5+ Ke7 4.Rf7+ Ke8 5.Qd7+ Ke9 6.Rf9#.  By playing the rook higher on the first move, black can force this main line of play have any desired finite length.  We have further variations with more black rooks and white king.

Value omega

Next, consider an infinite position with value $\omega^2$. The central black rook, currently attacked by a pawn, may be moved up by black arbitrarily high, where it will be captured by a white pawn, which opens a hole in the pawn column. White may systematically advance pawns below this hole in order eventually to free up the pieces at the bottom that release the mating material. But with each white pawn advance, black embarks on an arbitrarily long round of harassing checks on the white king.

Value omega squared

Here is a similar position with value $\omega^2$, which we call, “releasing the hordes”, since white aims ultimately to open the portcullis and release the queens into the mating chamber at right. The black rook ascends to arbitrary height, and white aims to advance pawns, but black embarks on arbitrarily long harassing check campaigns to delay each white pawn advance.

Releasing the hoards

Next, by iterating this idea, we produce a position with value $\omega^2\cdot 4$.  We have in effect a series of four such rook towers, where each one must be completed before the next is activated, using the “lock and key” concept explained in the paper.

Omega-squared-times-4

We can arrange the towers so that black may in effect choose how many rook towers come into play, and thus he can play to a position with value $\omega^2\cdot k$ for any desired $k$, making the position overall have value $\omega^3$.

Value omega cubed

Another interesting thing we noticed is that there is a computable position in infinite chess, such that in the category of computable play, it is a win for white—white has a computable strategy defeating any computable strategy of black—but in the category of arbitrary play, both players have a drawing strategy. Thus, our judgment of whether a position is a win or a draw depends on whether we insist that players play according to a deterministic computable procedure or not.

The basic idea for this is to have a computable tree with no computable infinite branch. When black plays computably, he will inevitably be trapped in a dead-end.

Infinite tree

In the paper, we conjecture that the omega one of chess is as large as it can possibly be, namely, the Church-Kleene ordinal $\omega_1^{CK}$ in the context of finite positions, and true $\omega_1$ in the context of all positions.

Our idea for proving this conjecture, unfortunately, does not quite fit into two-dimensional chess geometry, but we were able to make the idea work in infinite **three-dimensional** chess. In the last section of the article, we prove:

Theorem. Every countable ordinal arises as the game value of an infinite position of infinite three-dimensional chess. Thus, the omega one of infinite three dimensional chess is as large as it could possibly be, true $\omega_1$.

Here is a part of the position. Imagine the layers stacked atop each other, with $\alpha$ at the bottom and further layers below and above. The black king had entered at $\alpha$e4, was checked from below and has just moved to $\beta$e5. Pushing a pawn with check, white continues with 1.$\alpha$e4+ K$\gamma$e6 2.$\beta$e5+ K$\delta$e7 3.$\gamma$e6+ K$\epsilon$e8 4.$\delta$e7+, forcing black to climb the stairs (the pawn advance 1.$\alpha$e4+ was protected by a corresponding pawn below, since black had just been checked at $\alpha$e4).

Climbing the stairs

The overall argument works in higher dimensional chess, as well as three-dimensional chess that has only finite extent in the third dimension $\mathbb{Z}\times\mathbb{Z}\times k$, for $k$ above 25 or so.

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

Infinite chess: the mate-in-n problem is decidable and the omega-one of chess, Cambridge, March 2012

I have just taken up a visiting fellow position at the Isaac Newton Institute for mathematical sciences in Cambridge, UK, where I am participating in the program Syntax and Semantics:  the legacy of Alan Turing.   I was asked to give a brief introduction to some of my current work, and I chose to speak about infinite chess.

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

 

article | slides | streaming videoprogram of abstracts

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?