6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.