Davide Leonessi

Infinite Hex is a draw

In this second joint paper with Prof. Joel David Hamkins, we expand the results achieved for infinite Hex in chapter 2 of my MSc dissertation, and present new open questions.

You can read this article at arXiv:2201.06475. (revised and expanded in December 2022)

Abstract

We introduce the game of infinite Hex, extending the familiar finite game to natural play on the infinite hexagonal lattice. Whereas the finite game is a win for the first player, we prove in contrast that infinite Hex is a draw—both players have drawing strategies.

Meanwhile, the transfinite game-value phenomenon, now abundantly exhibited in infinite chess and infinite draughts, regrettably does not arise in infinite Hex; only finite game values occur. Indeed, every game-valued position in infinite Hex is intrinsically local, meaning that winning play depends only on a fixed finite region of the board. This latter fact is proved under very general hypotheses, establishing the conclusion for all simple stone-placing games.

Transfinite game values in infinite draughts

In this joint paper with Prof. Joel David Hamkins, we prove that every countable ordinal is realised as the game value of a position in infinite draughts, simplifying further the constructions in chapter 3 of my MSc dissertation.

Joel David Hamkins and Davide Leonessi. “Transfinite game values in infinite draughts” Integers 22 (2022), #G5.

You can also read this article at arXiv:2111.02053.

Abstract

Infinite draughts, or checkers, is played just like the finite game, but on an infinite checkerboard extending without bound in all four directions. We prove that every countable ordinal arises as the game value of a position in infinite draughts. Thus, there are positions from which Red has a winning strategy enabling her to win always in finitely many moves, but the length of play can be completely controlled by Black in a manner as though counting down from a given countable ordinal.

Transfinite game values in infinite games

Over the summer 2021 I completed my master’s dissertation under the supervision of Prof. Joel David Hamkins, achieving a Distinction in my MSc in Mathematics and Foundations of Computer Science at Oxford.
This work is presented and expanded in the papers co-authored with my supervisor on infinite Draughts and infinite Hex.

You can read my dissertation here, and at arXiv:2111.01630.

Abstract

The object of this study are countably infinite games with perfect information that allow players to choose among arbitrarily many moves in a turn; in particular, we focus on the generalisations of the finite board games of Hex and Draughts.

In chapter 1 we develop the theory of transfinite ordinal game values for open infinite games following Evans and Hamkins (2014), and we focus on the properties of the omega one, that is the supremum of the possible game values, of classes of open games; we moreover design the class of climbing-through-T games as a tool to study the omega one of given game classes.

The original contributions of this research are presented in the following two chapters.

In chapter 2 we prove classical results about finite Hex and present Infinite Hex, a well-defined infinite generalisation of Hex. We then introduce the class of stone-placing games, which captures the key features of Infinite Hex and further generalises the class of positional games already studied in the literature within the finite setting of Combinatorial Game Theory.

The main result of this research is the characterization of open stone-placing games in terms of the property of essential locality, which leads to the conclusion that the omega one of any class of open stone-placing games is at most ꞷ.

In particular, we obtain that the class of open games of Infinite Hex has the smallest infinite omega one, that is $\omega_1^{\rm Hex}=\omega$

In chapter 3 we show a dual result; we define the class of games of Infinite Draughts and explicitly construct open games of arbitrarily high game value with the tools of chapter 1, concluding that the omega one of the class of open games of Infinite Draughts is as high as possible, that is $\omega_1^{\rm Draughts}=\omega_1$