Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from boardgames.stackexchange.com Dec 7 '11 at 3:52

This question came from our site for people who like playing board games, designing board games or modifying the rules of existing board games.

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
1  
"There is probably even a closed-form..." - it's a (terminating) ${}_3 F_2$ hypergeometric function, but the sum expression you have is more practical. –  J. M. Dec 7 '11 at 4:13
    
@J.M. Thanks for the edit. When I wrote this, it was for a site that doesn't have LaTeX support. I didn't realize it was migrated. –  BlueRaja - Danny Pflughoeft Dec 7 '11 at 5:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.