Skip to main content
2 of 3
Changed stray occurrences of $n$ to $\alpha$
gmvh
  • 3.1k
  • 6
  • 27
  • 45

Who wins infinite Hex?

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 discussion (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.)
Christopher King
  • 6.4k
  • 1
  • 32
  • 60