TicTacToe State Space Choose Calculation

I understand there are numerous questions around the internet about the state space of tic-tac-toe but I have a feeling they've usually got it wrong. Alternatively, perhaps it is I who have it wrong. Which is what leads me to my question.

Common Over Estimates:

Over Estimate One:

First some common answers to the number of possible states in Tic-Tac-Toe:

$9! = 362880$

This is one solution, which is overstates the upper-bound by the most I have seen, as it includes states such as:

x1|o2|
--------
|  |
--------
|  |


as well as:

x2|o1|
--------
|  |
--------
|  |


and all the other sequences of combinations possible. (Thank you to Exodus5 for pointing out the error.)

Over Estimate Two:

Another common answer that is better, common, but still over-estimating is:

$3^9 = 19683$

Which is better. Now 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.

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.

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, but still not 100% as it still overestimates.

$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$ = 9+72+252+756+1260+1680+1260+630+127 = 6046

Edit: The final term above I had $4 \choose 5$ but the correct value is $4 \choose 4$ which yields the missing 1 from Immanuel's solution.

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. 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 seems rather elegant considering its simplicity and the accuracy we are able to achieve, and lastly I like how each term being added correlates to each turn.

I recognize that it is not perfect, as I am ignoring some win conditions, i.e. this board is also counted:

x|x|x
-----
x|o|o
-----
x|o|o


Which isn't a legitimate board but still 6045 is less than $1/3$ of the commonly stated $3^9$ and isn't the equation rather beautiful?

The Question:

The question is, does this application of choose accurately represent how X's and O's can alternatively be placed on a 3x3 grid? Have I missed anything?

Bonus question: Any insights on how to estimate the number of illegitimate boards during moves 6, 7, 8, and 9? Note: With 5 or fewer moves, all boards generated are legitimate.

The goal is not to have a computer brute force the thinking for us, but to gain a deeper understanding of the distribution of win conditions. Also to make sure I didn't make any mistakes.

• Since each square can only be one of 3 states "X", "O" or blank there are at most $3^9 = 19638$ possible board states. It would be relatively easy to write a computer program to try each of these to test which were legitimate. The tests for legitimacy would be there is either the same number of "X" and "O" or 1 more "X" as "X" goes first and no more than one winning line. Similarly there are at most $9! = 362880$ games playable: again we could test all these with a computer. I'm not aware of any nice method to calculate this though without using brute force and a computer. – Warren Hill Sep 6 '13 at 14:58
• I'm not sure if you read what I have posted. I explicitly explain why $3^9$ is an inaccurate overestimation. I also explicitly explain why $9!$ is even more wrong than $3^9$. I understand it can be done with a computer but that isn't the point. You've only re-iterated points I have already made... The question is whether or not the my use of choose is accurate and results in a better estimation, and what the distribution of illegitimate boards may be for moves 6, 7, 8, and 9. – mwjohnson Sep 6 '13 at 15:08
• The $3^9$ estimate of states is a gross over estimate because it does not take into account how many Xs and Ys these are nor does include boards that have include boards that have more than one winning line. I'm just pointing out that this set is small enough as to be easily countable and a brute force computer model to test all of these should be trivial -- I'll take a look at this tomorrow and post the results If somebody else does. The 9! figure is from the number of playable games assuming they all go the full 9 moves; again its a gross over estimate. – Warren Hill Sep 6 '13 at 15:23
• @mwjohnson: 1. The board you give as an example is indeed a possible position (top left may have been last move). 2. I think from your response you may have missed that 9! is not usually calculating positions, it is (attempting) to calculate sequences of moves. It does over count (as it doesn't terminate on wins), but not for the reasons you give and shouldn't be conflated with positions. 3. See mathrec.org/old/2002jan/solutions.html for an explanation of the classical calculations here. – ex0du5 Sep 6 '13 at 16:18

Which states do you have that are illegal?
Note that the positions you have counted are either legal, or one move past legal as if the loser was allowed to make one more move after losing. So we need to count the ways that the loser has too many squares.

To count the way X's have a line, but O's and X's have the same number of squares (two cases: 3 of each or 4 of each), we pick the line (8 ways) and then fill the rest of the squares to get $8\times\left(\binom{6}{3} + 2\binom{6}{4}\right)=400$. The $\binom{6}{3}$ is choosing the locations of the O's in the 3 case. If we have 4 of each, then there are $\binom{6}{4}$ ways to place the O's and 2 places left to put the last X.
To count the ways that O's have a line, but there are more X's than O's, we get $8\times\left(\binom{6}{4} + \binom{6}{5}\right)=168$. $\binom{6}{4}$ is the number of ways to have 4 X's and 3 O's. $\binom{6}{5}$ is the case where we have 5 X's and 4 O's.

Subtracting these from your 6046 gets 5,478, which matches the computer.

• This is precisely the clever and brilliant response I was looking for, very nice and thank you. If you could, can you describe in a bit more detail the terms in your equation so I can better understand more precisely their relation. 8 is the number of ways to win, I understand that. 6 is the number of remaining squares given a win, I get that too. Why choose 3, 4 and 5? and why multiply by 2? If you could break down each term that would be a big help. Thank you. I agree that likely the null board is included. – mwjohnson Sep 7 '13 at 17:45
• Added a little bit more explanation. Hope it helps. – Immanuel Sep 7 '13 at 19:08

There are very few, so an exhaustive computer search is quite easy. There are 5,478 total positions, of which 958 are terminal, either because the board is full or because one of the players has won.

This assumes that X always plays first. If O is allowed to start, the set of positions is larger, but still less than twice as large.

This counts board positions, not play sequences. For example, if X plays in space 1, then O plays in space 2, then X plays in space 3, that is considered the same as if X plays in space 3, then O plays in space 2, then X plays in space 1, and it is not counted separately; nor is any subsequent position counted again.

It does not take rotations or reflections of the board into account; rotated or reflected boards are considered different positions. This would be quite easy to fix, if desired.

Source code is here. The game_over subroutine detects whether one of the players has three in a row; the next_moves subroutine calculates the moves available from a position, first using game_over to detect if one of the players has won; if so it reports that there are no legal moves and therefore no following positions.

• I appreciate the effort and the ground truth. I'm also happy to see my estimation is only off by about 650 states. Writing these kinds of programs can be fun exercises. I made a clarifying edit, as I'm more specifically interested in the nature of the distribution of win conditions and how that can be elegantly described with a clever equation. – mwjohnson Sep 6 '13 at 16:09