Thing I Learned Today: Number of Tic-Tac-Toe Boards

by Brian Shourd on November 6, 2012

Tags: coding, haskell, math

I was looking at a problem about Tic-Tac-Toe on HackerRank a few days ago, and it got me working on a bot-building program using a genetic algorithm. A big part of that was parameterizing the bots, so that I could give them some kind of DNA. Now, this is my first time trying anything with genetic algorithms, so I’m certainly doing this naively, but I thought - hey, I could just enumerate all possible board states, and then each bot would just be a list of moves corresponding to all possible board states.

But how many boards are there?

Let’s start with an estimate: a tic-tac-toe board has nine entries, and each one can be either blank, X, or O. That’s \(3^9 = 19683\) different states. Of course, this is way too many - many of these board states aren’t legal. They could have, for instance, 5 Xs and only 2 Os, which can’t happen unless X cheats.

Side note: When I was much younger, my mother bought us Tic-Tac-Toe Cheerios, which had both Xs and the iconic Os in the same box. Delightful. On the front of the box was, of course, a game of Tic-Tac-Toe, played with the cereal bits themselves, only it was wrong. It had such a state as I just described on it. My mother, bless her heart, encouraged me to write to General Mills and inform them of the predicament (I believe that I worded it “X cheated!”). To my surprise, they sent me back a coupon for a free box of any General Mills cereal and promptly cancelled Tic-Tac-Toe Cheerios forever. The latter is not likely my fault.

Ok, let’s find a better estimate. Let’s suppose that X goes first. There are 9 places for X to go. Then it is O’s turn, and he/she has only 8 spots to choose from. So far, that makes \(9 + 9 \times 8\) boards (\(9\) having just one X, \(9 \times 8\) having an X and an O). Continuing in this pattern, we find \(\sum_{i=1}^9 \frac{9!}{(9-i)!} = 986409\) boards.

That’s significatnly worse! What went wrong? Well, we are double-counting boards here like nobody’s business. Our estimate for the number of boards with 2 Xs and 1 O is \(9 \times 8 \times 7 = 504\). But there are some ordering issues. This board will be counted twice:

 X | O |   
---+---+---
   | X |   
---+---+---
   |   |

It will be counted once for X taking the first turn in the center, and again if X’s first turn is in the corner. And it just get’s worse as turns go on. We have to divide out by the number of ways that we can reorder the X’s. In this case, there are 2 of them, so it is \(2!\) and there are only \(252\) boards with 2 Xs and 1 O on them. The total number of boards is then

\(\sum_{i=0}^9 \frac{9!}{(9-i)! \lfloor \frac{i}{2} \rfloor ! \lceil \frac{i}{2} \rceil !} = 6046\)

Much better. In fact, we’re actually pretty close now.

But there are still too many. Why? Sometimes the game ends. In particular, if somebody wins, the game ends. Many of the boards that we counted with lots of Xs and Os actually have a 3-in-a-row in them, and thus aren’t really valid states. Actually, only the ones where both players have 3-in-a-row are invalid. And counting these gets very tricky.

So let’s ask the computer to do it. I wrote a quick Haskell program to do this and it found out that there are actuall only 5812 possible board states.

We can reduce that more, though. Lot’s of these boards are just rotations or reflections of other boards. They’re basically the same. If we take this into consideration, then there are only 765 board states.

But wait, there’s more! Lot’s of these boards don’t have any actual decisions to make, since the game is either over or there is only one move left. Eliminating those, we find 593 states.

And if we take away the boards with easy decisions - that is, boards where there is a ‘take the win’ or ‘block the win’ option, we reduce it still more. Only 96 boards remain. Here is the complete code: