Who wins infinite Hex?

Question

In this game, you start with a square. Alice tries to connect the top side to the bottom side, and Bob tries to connect the left side to the right side, like in Hex. Unlike in Hex, Alice and Bob use points instead of hexagons.

Now you might say that neither Alice nor Bob can win, since it is impossible to form a line using only finitely many points. Not so, for Alice and Bob can move infinitely many times!

In particular, let $S_\alpha$ be the state of the board, where $\alpha$ is an ordinal. Then:

• If $\alpha=0$, then $S_\alpha=\emptyset$.
• If $\alpha$ is a successor ordinal, then Alice adds $(\alpha,p,Alice)$, where $p$ is some point in $[0,1] \times [0,1]$ that has not already been played, to $S_{\alpha-1}$, unless $S_{\alpha-1}=[0,1] \times [0,1]$. She can use $S_{\alpha-1}$ to inform her decision (in other words, Alice has a strategy function that given $S_{\alpha-1}$, gives her move). Bob does likewise.
• If $\alpha$ is a limit ordinal, then $S_\alpha = \bigcup_{\beta<\alpha}S_\beta$.

We say Alice has won if there for some $\alpha$, there is a path in $[0,1] \times [0,1]$, composed of points corresponding to Alice's moves, connecting the top and bottom. Bob wins likewise, (connecting the left and right side of the boards).

Since there are ordinals $\alpha$ such that $|\alpha| > |[0,1]\times[0,1]|$, the board must eventually be filled (in particular, it will happen before such an ordinal).

One thing to note is that Alice and Bob cannot both win, due to the Jordan curve theorem. On the other hand, it is possible for neither of them to win. In this case, Alice would have no curve connecting the top and bottom, and Bob would have no curve connecting the sides.

My question is:

• Does Alice have a winning strategy? (Bob doesn't, due to a strategy stealing argument.)
• Does Alice or Bob have a drawing strategy (a strategy that guarantees either a win or a draw)? (If Bob does, so does Alice.)

Answer 1

Let $\mathfrak{c}$ denote the cardinality of real numbers and let $(C_{\alpha}: \alpha < \mathfrak{c})$ be an enumeration of uncountable closed subsets of the unit square.

Let Bob's strategy be playing a point $q_{\alpha} \in C_{\alpha}$ not already chosen at stage $\alpha$ for $\alpha < \mathfrak{c}$. This is possible since, at stage $\alpha < \mathfrak{c}$, the players could have chosen only less than $\mathfrak{c}$ many points of the set $C_{\alpha}$ which has cardinality $\mathfrak{c}$. Bob can do whatever he feels like for other ordinals.

Note that the game will proceed at least $\mathfrak{c}$ stages since any curve connecting opposite sides contains $\mathfrak{c}$ many points. Any curve $C$ witnessing the victory of a player would be necessarily of the form $C_{\beta}$ for some $\beta < \mathfrak{c}$ and hence contains the point $q_{\beta}$. Thus Bob guarantees not losing if he plays with this strategy. (Of course, by using this strategy, Alice can guarantee not losing as well.)

Answer 2

This doesn't answer the question that was asked, but rather an alternative kind of infinite Hex, played on the infinite hexagonal lattice board as shown below. I am posting it because people interested in infinite Hex might find this question and I would think they might want to know about this natural alternative version of the game. The players take turns placing stones on the infinite hexagonal board, and Red aims to connect lower left to upper right, and Blue on the other diagonal.

In joint work, my student Davide Leonessi and I proved that infinite Hex is a draw.

Theorem. Infinite Hex is a draw. Neither player has a winning strategy; both players have draw-or-better strategies.

The work was part of Leonessi's masters thesis for the MSc in the Mathematics and the Foundations of Computer Science at Oxford. You can find our paper at:

• Joel David Hamkins, Davide Leoness, Infinite Hex is a draw, arxiv:2201.06475, 2022.

The main theorem is proved by noticing first that a strategy-stealing argument shows that the second player can have no winning strategy. But the second-player (blue) has a drawing strategy (and hence the first also) by a mirroring strategy as follows: Blue will fix a horizontal line (green), and then copy the red plays reflected across that line, shifted by a half square. If Red would have connected to the upper right, then the correspondingly reflected blue play would trap the rest of the line to the right, preventing it from connected to the lower left. So this strategy is draw or better for Blue.

The paper has many other interesting results, including the fact that infinite game values do not arise in infinite Hex in any position. In any position, if Red can force a win in finitely many moves, then there is a uniform bound on the number of moves required.

There is also this related (unanswered!) question concerning the logical complexity of the winning condition in this version of infinite Hex:

What is the complexity of the winning condition in infinite Hex?.

Please figure it out and post an answer — I will be grateful