1.Introduction
Background
Hex is a board game Hex (board game).
It can be proven that the first player wins on boards with any size n×n (without swap rule) using a non-constructive proof. But the proof cannot provide specific strategies of how to win.
Question
Original question on MathOverflow
On an n×n board, assume the first player tries to minimize the length of the game to win, and the second player tries to maximize the length to lose. Call the optimal length F(n). (F(n) is the sum of move numbers of two player, not one player).
What are the asymptotics of F(n)?
Brief results
The following results come from a strong Hex AI called KataHex. The AI and the raw data with visualization scripts are here: KataHex release. It's NOT a exhaustive search so there is a small possibility to be wrong (but probably never). And it can't be called a "proof".
F(n) for n≤9 are pretty sure:
F(1)=1, F(2)=3, F(3)=5, F(4)=9, F(5)=13, F(6)=19, F(7)=25, F(8)=31, F(9)=37
For n≥10, the results in the figure below is just an estimated value , error is about ±0.04*n²
This shows that F(n) is probably O(n²) (at least O(n^1.9)), F(n) ≈ 0.425*n² + 0.515*n
2.Method
KataGo is an opensource alphazero-like reinforcement learning AI for Go. KataGo source code
I modified KataGo to the Hex game and trained. KataHex source code KataHex release
To estimate the move number required to win the game F(n), an extra "move number limit" rule was added: If neither player can connect before m moves, then the game is a draw.
Board size n and move limit number m are randomly selected at the start of every self-play game for training. 1≤n≤27, 1≤m≤n²
After enough training, the AI become enough strong to provide relatively accurate estimations of F(n)
3.Result
3.1 Definations
For any board size n and move limit number m, AI can estimate the win-rate of the first player w(n,m), lose-rate of the first player l(n,m) (the win-rate of the second player), and draw-rate d(n,m) (no player wins before m moves).
Since the AI is strong, l(n,m) is very close to zero and can be ignored (especially for n≤19). w(n,m) ≈ 1 - d(n,m) So we use d(n,m) as the criterion for F(n) estimation.
The winner is the first player, so the last move is the first player, F(n) should be an odd number. So we can ignore even numbers for m.
Obviously, for an infinitely strong AI, d(n,m) can only be 0 or 1 because of Zermelo’s theorem. If d(n,m)=0 and d(n,m-2)=1, then F(n)=m.
3.2 Results of d(n,m) and F(n) estimation
The AI always shows d(n,m)≈0 or d(n,m)≈1 for any m with n≤9 because AI can almost exhaustively calculate every valuable strategy, so we can get very accurate F(n) estimation for n≤9.
However, with n≥10, it becomes too difficult for the current version of AI. Here I used a threhold: If d(n,m)≤threhold and d(n,m-2)>threhold, then F(n)≈m. Here I used threhold=0.5
Here is a heatmap of d(n,m). Notice that y-axis is m/n² for better visualization.
F(1)=1, F(2)=3, F(3)=5, F(4)=9, F(5)=13, F(6)=19, F(7)=25, F(8)=31, F(9)=37
For n≥10, the error range is about ±0.04*n² (transition region from blue to yellow for n≥10 is about 0.08*n²)
3.3 Example of optimal games
Optimal games means every move is the best move. The first player tries to minimize the move number before winning, and the second player tries to maximize the move number before losing. The game length should be F(n).
Optimal game of each board size is probably not unique (maybe millions or more). Here I just show one of them.
In the following games, black is the first player and black should connect up and down, white is the second player and should connect left and right.
Some of the moves near the end (after black having a "jump connection") are ignored because they are too simple.
5x5 board: F(5)=13. Black needs 4 more stones to connect fully, so the final move num is 5+2*4=13
6x6 board: F(6)=19. Black needs 4 more stones to connect fully, so the final move num is 11+2*4=19
7x7 board: F(7)=25. Black needs 3 more stones to connect fully, so the final move num is 19+2*3=25
8x8 board: F(8)=31. Black needs 6 more stones to connect fully, so the final move num is 19+2*6=31
9x9 board: F(9)=37. Black needs 7 more stones to connect fully, so the final move num is 23+2*7=37
3.4 Results of every first move on 9x9 and smaller boards
"Swap after first move" is a popular rule for Hex to make the game more balanced. So the evaluation of every first move is necessary for human or bot competitions. Here the results(win or lose) and optimal game length are estimated for n≤9. The following results of n=8 and n=9 may be NOT 100% correct!
W+number means the first player(red) wins, L+number means the second player(blue) wins. For example: W37 means the first player(red) will win in 37 moves. L38 means the second player(blue) will win in 38 moves.
Top comments (0)