Length of optimal play in Hex as a function of size

Question

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:

Answer 1

HexWiki says a typical (human) game fills roughly 1/3 of the board, but people probably resign when a virtual connection is formed or earlier.

If you want to do some empirical study, there is a version of KataGo modified for Hex by HZY, and KataGo allows training networks that work for multiple board sizes, but I don't know if the code uses the number of moves as an auxiliary target in addition to winning. Networks trained on up to 27x27 board are available here (together with GUI) and the code is here, but apparently HZY has started working on an update.

Even though all 9x9 openings and two 10x10 openings are solved (from 2013; any updates?), the solutions probably optimize the number of steps to a virtual connection (e.g. consisting of templates) rather than to an actual connection; but maybe this is close enough.

(Curiously I arrived at this question by searching "percolation theory" and "Hex". I saw HZY's empirical study of the winrates of openings on Zhihu, and wonder whether there's a percolation theoretic explanation of the observed pattern, and whether one can exhibit a winning first move on every (large enough?) board and prove it's winning; because there's always a winner, one only needs to show it's "at least as good" as all other moves. Let me mention that there's a explicit (polynomial time) winning strategy that starts with two stones on boards up to 10x10, three stones on boards up to 16x16, and so on. Moore and Shannon's resistor network is used in programs like Hexy as an evaluation function, and apparently there are papers that study resistor networks from a percolation theory perspective.)

Answer 2

https://dev.to/hzyhhzy/analysis-of-the-length-of-optimal-games-of-hex-game-using-alphazero-like-ai-16n7

I wrote a post on this question.
$f(n)\approx0.425*n^2+0.515*n$ according to KataHex

---

Updated on 2024.8.20
Recently I'm training KataHex with move limit.
We can estimate the length of optimal Hex by the win-rate and draw-rate with different move limit settings for KataHex.
Some known results until now (larger boards will be updated soon):
1x1 board: 1 moves
2x2 board: 3 moves
3x3 board: 5 moves
4x4 board: 9 moves
5x5 board: 13 moves
6x6 board: 19 moves
7x7 board: 25 moves
8x8 board: 31 moves
9x9 board: 37 moves
larger than 9x9 are not sure, the bounds are estimated by the win-rate and draw-rate of KataHex
11x11 board: 55~59 moves
13x13 board: 75~81 moves
15x15 board: 99~103 moves

$f(n)\approx0.6*n^{1.9}$
or $f(n)\approx 0.75*\frac{n^2}{ln(n)^{0.5}}$

---

I guess it is $O(n^{2})$, maybe about $n^{2}/2$ . I just guessed based on some games by KataHex. These games almost filled the full board, no area is useless. I can't give out any "mathematical" explanation for such a difficult game.
KataHex is an alphazero-like Hex AI modified by me from KataGo. I trained it on 2*RTX4090 for 3 months. It plays well on boards smaller than 37x37. (at least stronger than any human)

Some thinking:
We know that ~80% first moves for the first player are winning, which means at least 80% locations are not useless in the optimal solution.
If there exists a way to win in less than $O(n^{2})$ moves, obviously the most part of the board is not used. We can imagine that if the unused part is filled by white stones, obviously black can't win.
More strategicly, strong hex players will always trying to form multiple winning paths at the same time, making the opponent unable to block them.
The problem of this explaination is that this can't show that the most part are used in one single game. If the most part can be cut and become useless after less than $O(n^{2})$ moves, these inferences become not valid