Skip to main content
3 of 4
added 503 characters in body

Length of optimal play in Hex as a function of size

Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the length. Call the resulting optimal length $f(n)$.

Question: What are the asymptotics of $f(n)$?

Trivially $f$ is at least linear and at most quadratic. Campbell, On optimal play in the game of Hex give a linear lower bound with constant 2.5 (as opposed to 2 if the second player helps the first to win).

Are there better bounds on $f(n)$, or conjectured bounds? I would expect it to be superlinear, but don’t know if it’s subquadratic. An intermediate exponent would be quite interesting.

Update: Peres et al., Random-Turn Hex and other selection games estimate the exponent for the variant of Hex where the player to move is random per turn at between 1.5 and 1.6. That is, they conjecture that the optimal length in random turn Hex is between $O(n^{1.5})$ and $O(n^{1.6})$. Unclear how this corresponds to the original Hex game. Figure from the paper:

enter image description here