Feeds:
Posts

Introduction:

I recently found myself interested in the calculation of the state space, particularly the size, of the game TicTacToe. For what reason, it is beyond me, but as I soon discovered many people went about it all wrong.

Before I show, what I think to be an interesting method of calculating the state-space size, let’s first look at some common, yet naive, estimations.

Over Estimate One:

One approach is to just consider the permutations. The equation for calculating a permutation is $f(x) = x!$. This gives us all the different possible orderings of the set of objects. In the case of TicTacToe there are 9 squares, so how many different ways can you select the 9 squares? Well $9!$ number of ways. $9!=362880$

This solution overstates the upper-bound by the most I have seen, as it includes the following states as unique.

x1 | o2 |               x2 | o1 |
——————          ——————
|      |                    |      |
——————          ——————
|      |                    |      |

and all the other sequences of combinations possible. So just how poorly does this estimate, overestimate? Well by about 357,000. So I’m pretty sure if you just randomly guessed a number, you would be closer to the actual result than you would by saying nine factorial.

Over Estimate Two:

Another common answer that is better, common, but still over-estimating is: $3^9=19683$

Which is better. We only count the following board once…

X | X | X
—————
X | X | X
—————
X | X | X

but I’ve still never heard of any type of one-player Tic-Tac-Toe and it seems boring. This solution comes about based on the idea that there are 9 squares, and each square can have one of three possible states, an X, an O or an empty space.

It is worth noting, these guys claim they’ve got the answer but they are discussing games not state-spaces. That is the progression of the N-moves in a game is also taken into account. They also calculate a number of other statistics regarding Tic-Tac-Toe but we are interested in state-space here.

The Power of Choose:

After sitting down and thinking for awhile I came up with a formula that does a more precise job at estimating the state space of Tic-Tac-Toe and it is quite simple. ${9 \choose 1}{8 \choose 0}+{9 \choose 1}{8 \choose 1}+{9 \choose 2}{7 \choose 1}+{9 \choose 2}{7 \choose 2} +{9 \choose 3}{6 \choose 2}$ $+{9 \choose 3}{6 \choose 3}+{9 \choose 4}{5 \choose 3}+{9 \choose 4}{ 5 \choose 4}+{9 \choose 5}{ 4 \choose 4} = 6046$ 

Essentially each term of ${9 \choose X}$is placing the X’s on the board, then the ${K \choose L}$ is the O’s choosing the appropriate number of places from the remaining open spaces on the board. Each term being added is the number of states being generated at each turn. These terms are equal to: $9+72+252+756+1260+1680+1260+630+127 = 6046$

So for turn 1 we have 9 states, for turn 2, 72 states and so on.

The main point here is 6046 is far fewer than the other estimations, the use of Choose is elegant considering its simplicity and the accuracy we are able to achieve. Lastly I like how each term being added correlates to each turn.

As was noted, we still have an over-estimate though. Luckily we can address this point as well, naturally, using our new found love for the choose operation. The first five moves all result in legitimate board states. So we can just accept those terms in our above equation.

For turns 6, 7, and 8 we are generating too many states, namely X’s or O’s have won but more pieces are being placed on the board. There are 8 ways to generate 3 X’s or O’s in a row. So we will use this knowledge and generate our adjusting calculation. $-8( {6 \choose 3} + 2 {6 \choose 4})-8({6 \choose 4}+{6 \choose 5})$

The first half is counting the O’s when X’s have already won. The second half is counting X’s when O’s have already won. Since there is one more X than O’s on the board, we use ${6 \choose 4}+{6 \choose 5}$ one higher than when we are placing O’s. $-8( {6 \choose 3} + 2 {6 \choose 4})=400$

and $-8({6 \choose 4}+{6 \choose 5})=168$

When we subtract these from our original 6046 we get 5478, which is the actual number of states which can be generated in Tic-Tac-Toe.

We can go one step further and condense the calculation using a summation. $\sum_{i=1}^5({9 \choose i}{9-i \choose i-1}) + \sum_{i=1}^4({9 \choose i}{9-i \choose i}) - 8({6 \choose 3}+3{6 \choose 4} + {6 \choose 5}) = 5478$

The interesting point here is that the first summation is adding turns 1, 3, 5, 7, and 9 while the second summation is adding turns 2, 4,6, and 8. The -8 at the end is adjusting for the over-estimate.