Infinite-Games Workshop

Welcome to the Infinite-Games Workshop, beginning Autumn 2023. The past ten years has seen an explosion in the study of infinite games, for researchers are now investigating diverse infinite games, including infinite chess, infinite draughts, infinite Hex, infinite Othello, infinite Go, indeed, we seem to have research projects involving infinitary analogues of all our familiar finite games. It is an emerging research area with many new exciting results.

This autumn, we shall set the workshop off with talks on several exciting new results in infinite chess, results which settle what had been some of the big open questions in the topic, including the question of the omega one of chess—the supremum of the ordinal game values that arise—as well as a finite position with game value $\omega^2$.

The workshop talks will be run at a high level of sophistication, aimed for the most part at serious researchers currently working in this emerging area. Mathematicians, computer scientists, infinitary game theorists, all serious researchers are welcome.

All talks will take place on Zoom at meeting 968 0186 3645 (password = latex code for the first uncountable ordinal). Contact for further information.

Talks will be 90 minutes, with a workshop style welcoming questions. All talks will be recorded and placed on our YouTube channel. Talks will generally be held on Thursdays at 11:00 am New York time.

Add our calendar: Infinite-Games Workshop Calendar

The workshop is being organized by myself with the assistance of Davide Leonessi.

FAll 2023 Talks

21 September 2023 11am ET

Infinite draughts: a solved open game

Davide Leonessi, The Graduate Center of the City University of New York

Davide Leonessi, CUNY GC

Abstract: In this talk I will introduce open infinite games, and then define a natural generalization of draughts (checkers) to the infinite planar board. Infinite draughts is an open game, giving rise to the game value phenomenon and expressing it fully—the omega one of draughts is at least true $\omega_1$ and every possible defensive strategy of the losing player can be implemented. 

5 October 2023 11:00 am ET

Introduction to infinite games

Joel David Hamkins, Professor of Logic, University of Notre Dame

Abstract: I shall give a general introduction to the subject and theory of infinite games, drawing upon diverse examples of infinitary games, but including also infinite chess, infinite Hex, infinite draughts, and others.

2 November 2023 11:00 am ET

Complexity of the winning condition of infinite Hex

Ilkka Törmä, University of Turku, Finland

Abstract: Hex is a two-player game where the goal is to form a contiguous path of tokens from one side of a finite rectangular board to the opposite side. It is a famous classical result that Hex admits no draws: a completely filled board is a win for exactly one player. Infinite Hex is a variant introduced recently by Hamkins and Leonessi. It is played on the infinite two-dimensional grid $\mathbb{Z}^2$, and a player wins by forming a certain kind of two-way infinite contiguous path. Hamkins and Leonessi left open the complexity of the winning condition, in particular whether it is Borel. We present a proof that it is in fact arithmetic.

16 NOvember 2023 11:00 am ET

A finite position in infinite chess with game value $\omega^2+k$

Andreas Tsevas, Physics, Ludwig Maximalians Universität München

Abstract: I present a position in infinite chess with finitely many pieces and a game value of $\omega^2+k$ for $k\in\mathbb N$, thereby improving the previously known best result in the finite case of $\omega\cdot n$ for arbitrary $n \in\mathbb N$. This is achieved by exercising control over the movement of a white queen along two rows on the chessboard via precise tempo manipulation and utilization of the uniquely crucial ability of the queen to interlace horizontal threats with diagonal moves.

7 December 2023 11:00 am ET

All Countable Ordinals Arise as Game Values in Infinite Chess

Matthew Bolan, University of Toronto

Matthew Bolan, Infinite-Games Workshop

Abstract: For every countable ordinal $\alpha$, we show that there exists a position in infinite chess with infinitely many pieces having game value $\alpha$.

Infinite Games, Frivolities of the Gods, Logic at Large Lecture, May 2022

The Dutch Association for Logic and Philosophy of the Exact Sciences (VvL) has organized a major annual public online lecture series called LOGIC AT LARGE, where “well-known logicians give public audience talks to a wide audience,” and I am truly honored to have been invited to give this year’s lecture. This will be an online event, the second of the series, scheduled for May 31, 2022 (note change in date!), and further access details will be posted when they become available. Free registration can be made on the VvL Logic at Large web page.

Abstract. Many familiar finite games admit natural infinitary analogues, which often highlight intriguing issues in infinite game theory. Shall we have a game of infinite chess? Or how about infinite draughts, infinite Hex, infinite Go, infinite Wordle, or infinite Sudoku? Let me introduce these games and use them to illustrate various fascinating concepts in the theory of infinite games.

Come enjoy the lecture, and stay for the online socializing event afterwards. Hope to see you there!

The connect-infinity game!

I saw the following image on Twitter and Reddit, an image suggesting an entire class of infinitary analogues of the game Connect-Four. What fun! Let’s figure it out!

I’m not sure to whom the image or the idea is due. Please comment if you have information. (See comments below for current information.)

The rules will naturally generalize those in Connect-Four. Namely, starting from an empty board, the players take turns placing their coins into the $\omega\times 4$ grid. When a coin is placed in a column, it falls down to occupy the lowest available cell. Let us assume for now that the game proceeds for $\omega$ many moves, whether or not the board becomes full, and the goal is to make a connected sequence in a row of $\omega$ many coins of your color (you don’t have to fill the whole row, but rather a connected infinite segment of it suffices). A draw occurs when neither or both players achieve their goals.

In the $\omega\times 6$ version of the game that is shown, and indeed in the $\omega\times n$ version for any finite $n$, I claim that neither player can force a win; both players have drawing strategies.

Theorem. In the game Connect-$\omega$ on a board of size $\omega\times n$, where $n$ is finite, neither player has a winning strategy; both players have drawing strategies.

Proof. For a concrete way to see this, observe that either player can ensure that there are infinitely many of their coins on the bottom row: they simply place a coin into some far-out empty column. This blocks a win for the opponent on the bottom row. Next, observe that neither player can afford to follow the strategy of always answering those moves on top, since this would lead to a draw, with a mostly empty board. Thus, it must happen that infinitely often we are able to place a coin onto the second row. This blocks a win for the opponent on the second row. And so on. In this way, either players can achieve infinitely many of their coins on each row, thereby blocking any row as a win for their opponent. So both players have drawing strategies. $\Box$

Let me point out that on a board of size $\omega\times n$, where $n$ is odd, we can also make this conclusion by a strategy-stealing argument. Specifically, I argue first that the first player can have no winning strategy. Suppose $\sigma$ is a winning strategy for the first player on the $\omega\times n$ board, with $n$ odd, and let us describe a strategy for the second player. After the first move, the second player mentally ignores a finite left-initial segment of the playing board, which includes that first move and with a odd number of cells altogether in it (and hence an even number of empty cells remaining); the second player will now aim to win on the now-empty right-side of the board, by playing as though playing first in a new game, using strategy $\sigma$. If the first player should ever happen to play on the ignored left side of the board, then the second player can answer somewhere there (it doesn’t matter where). In this way, the second player plays with $\sigma$ as though he is the first player, and so $\sigma$ cannot be winning for the first player, since in this way the second player would win in this stolen manner.

Similarly, let us argue by strategy-stealing that the second player cannot have a winning strategy on the board $\omega\times n$ for odd finite $n$. Suppose that $\tau$ is a winning strategy for the second player on such a board. Let the first player always play at first in the left-most column. Because $n$ is odd, the second player will eventually have to play first in the second or later columns, leaving an even number of empty cells in the first column (perhaps zero). At this point, the first player can play as though he was the second player on the right-side board containing only that fresh move. If the opponent plays again to the left, then our player can also play in that region (since there were an even number of empty cells). Thus, the first player can steal the strategy $\tau$, and so it cannot be winning for the second player.

I am unsure about how to implement the strategy stealing arguments when $n$ is even. I shall give this more thought. In any case, the theorem for this case was already proved directly by the initial concrete argument, and in this sense we do not actually need the strategy stealing argument for this case.

Meanwhile, it is natural also to consider the $n\times\omega$ version of the game, which has only finitely many columns, each infinite. The players aim to get a sequence of $\omega$-many coins in a column. This is clearly impossible, as the opponent can prevent a win by always playing atop the most recent move. Thus:

Theorem. In the game Connect-$\omega$ on a board of size $n\times\omega$, where $n$ is finite, neither player has a winning strategy; both players have drawing strategies.

Perhaps the most natural variation of the game, however, occurs with a board of size $\omega\times\omega$. In this version, like the original Connect-Four, a player can win by either making a connected row of $\omega$ many coins, or a connected column or a connected diagonal of $\omega$ many coins. Note that we orient the $\omega$ size column upwards, so that there is no top cell, but rather, one plays by selecting a not-yet-filled column and then occupying the lowest available cell in that column.

Theorem. In the game Connect-$\omega$ on a board of size $\omega\times\omega$, neither player has a winning strategy. Both players have drawing strategies.

Proof. Consider the strategy-stealing arguments. If the first player has a winning strategy $\sigma$, then let us describe a strategy for the second player. After the first move, the second player will ignore finitely many columns at the left, including that first actual move, aiming to play on the empty right-side of the board as though the first player using stolen strategy $\sigma$ (but with colors swapped). This will work fine, as long as the first player also plays on that part of the board. Whenever the first player plays on the ignored left-most part, simply respond by playing atop. This prevents a win in that part of the part, and so the second player will win on the right-side by pretending to be first there. So there can be no such winning strategy $\sigma$ for the first player.

If the second player has a winning strategy $\tau$, then as before let the first player always play in the first column, until $\tau$ directs the second player to play in another column, which must eventually happen if $\tau$ is winning. At that moment, the first player can pretend to be second on the subboard omitting the first column. So $\tau$ cannot have been winning after all for the second player. $\Box$

In the analysis above, I was considering the game that proceeded in time $\omega$, with $\omega$ many moves. But such a play of the game may not actually have filled the board completely. So it is natural to consider a version of the game where the players continue to play transfinitely, if the board is not yet full.

So let us consider now the transfinite-play version of the game, where play proceeds transfinitely through the ordinals, until either the board is filled or one of the players has achieved the winning goal. Let us assume that the first player also plays first at limit stages, at $\omega$ and $\omega\cdot 2$ and $\omega^2$, and so on, if game play should happen to proceed for that long.

The concrete arguments that I gave above continue to work for the transfinite-play game on the boards of size $\omega\times n$ and $n\times\omega$.

Theorem. In the transfinite-play version of Connect-$\omega$ on boards of size $\omega\times n$ or $n\times\omega$, where $n$ is finite, neither player can have a winning strategy. Indeed, both players can force a draw while also filling the board in $\omega$ moves.

Proof. It is clear that on the $n\times\omega$ board, either player can force each column to have infinitely many coins of their color, and this fills the board, while also preventing a win for the opponent, as desired.

On the $\omega\times n$ board, consider a variation of the strategy I described above. I shall simply always play in the first available empty column, thereby placing my coin on the bottom row, until the opponent also plays in a fresh column. At that moment, I shall play atop his coin, thereby placing another coin in the second row; immediately after this, I also play subsequently in the left-most available column (so as to force the board to be filled). I then continue playing in the bottom row, until the opponent also does, which she must, and then I can add another coin to the second row and so on. By always playing the first-available second-row slot with all-empty second rows to the right, I can ensure that the opponent will eventually also make a second-row play (since otherwise I will have a winning condition on the second row), and at such a moment, I can also make a third-row play. By continuing in this way, I am able to place infinitely many coins on each row, while also forcing that the board becomes filled. $\Box$

Unfortunately, the transfinite-play game seems to break the strategy-stealing arguments, since the play is not symmetric for the players, as the first player plays first at limit stages.

Nevertheless, following some ideas of Timothy Gowers in the comments below, let me show that the second player has a drawing strategy.

Theorem. In the transfinite-play version of Connect-$\omega$ on a board of size $\omega\times\omega$, the second player has a drawing strategy.

Proof. We shall arrange that the second player will block all possible winning configurations for the first player, or to have column wins for each player. To block all row wins, the second player will arrange to occupy infinitely many cells in each row; to block all diagonal wins, the second player will aim to occupy infinitely many cells on each possible diagonal; and to block the column wins, the second player will aim either to have infinitely many cells on each column or to copy a winning column of the opponent on another column.

To achieve these things, we simply play as follows. Take the columns in successive groups of three. On the first column in each block of three, that is on the columns indexed $3m$, the second player will always answer a move by the first player on this column. In this way, the second player occupies every other cell on these columns—all at the same height. This will block all diagonal wins, because every diagonal winning configuration will need to go through such a cell.

On the remaining two columns in each group of three, columns $3m+1$ and $3m+2$, let the second player simply copy moves of the opponent on one of these columns by playing on the other. These moves will therefore be opposite colors, but at the same height. In this way, the second player ensures that he has infinitely many coins on each row, blocking the row wins. And also, this strategy ensures that in these two columns, at any limit stage, either neither player has achieved a winning configuration or both have.

Thus, we have produced a drawing strategy for the second player. $\Box$

Thus, there is no advantage to going first. What remains is to determine if the first player also has a drawing strategy, or whether the second player can actually force a win.

Gowers explains in the comments below also how to achieve such a copying mechanism to work on a diagonal, instead of just on a column.

I find it also fascinating to consider the natural generalizations of the game to larger ordinals. We may consider the game of Connect-$\alpha$ on a board of size $\kappa\times\lambda$, for any ordinals $\alpha,\kappa,\lambda$, with transfinite play, proceeding until the board is filled or the winning conditions are achieved. Clearly, there are some instances of this game where a player has a winning strategy, such as the original Connect-Four configuration, where the first player wins, and presumably many other instances.

Question. In which instances of Connect-$\alpha$ on a board of size $\kappa\times\lambda$ does one of the players have a winning strategy?

It seems to me that the groups-of-three-columns strategy described above generalizes to show that the second player has at least a drawing strategy in Connect-$\alpha$ on board $\kappa\times\lambda$, whenever $\alpha$ is infinite.

Stay tuned…