How many states in the game of hex?

Question

I am trying to calculate how many unique states are possible to be in during a game of hex.

The upper bound for an $n\times n$ board is $3^{n^2}$. This is ignoring gameplay and simply considering that each space could be any of $3$ states. That number contains many states (all black, all white, etc..) that are impossible to reach in any actual game.

In a real game, the constraint will be added that the number of black spaces can be at most one greater than the number of white spaces. I cannot think of a way to quantify that number of states. The number is also reduced by winning states for either problem, which effectively stop any subsequent paths.

I have considered that the first move can be any of $n^2$ spaces, the second $n^2-1$... This gives $(n^2)!$ number of states which is even bigger than my upper bound because of duplicate configurations happening on different paths. I don't care about the path to the state, just what the board looks like.

How many board configurations are really possible on an $n\times n$ board?

Answer 1

If there are $n$ squares on the board and each player has $i$ pieces, there are $\dbinom{n}{i}\dbinom{n-i}{i}$ different possible board-setups. If one player has one more piece than the other, then there are $\dbinom{n}{i}\dbinom{n-i}{i-1}$ possible boards. Thus, the total number of possible boards is

$$\sum_{i=0}^{n/2} \binom{n}{i}\binom{n-i}{i}+\sum_{i=1}^{n/2} \binom{n}{i}\binom{n-i}{i-1}$$

Using Pascal's rule, this can be reduced to

$$1+\sum_{i=1}^{n/2} \binom{n}{i}\binom{n-i+1}{i}$$

There is probably even a closed-form, but it will take someone much smarter than me to figure that out.

---

So for a $14\times14$ board, there are about $3.14 \times 10^{24}$, or 3 trillion trillion possible boards.

Note that this doesn't take into account that some of these positions are impossible simply because the game would have ended before the position could have ever possibly been reached. Taking those positions into account makes the problem enormously more difficult - I doubt anyone could figure that out without brute-forcing it.