Tic Tac Toe Games

The number of tic tac toe games can be calculated.  While I will not attempt an exact count, I can calculate the upper boundary for the number of games.

I will start with the rough calculation:

There are 9 squares in tic tac toe.  

This makes 9 possible options for the first move

The second move has 8 options

The 3rd move has 7 options

This continues until the last move with only one option

The maximum number of games cannot exceed 9! individual games.  

So the rough calculation is 9!.  OR

`9x8x7x6x5x4x3x2x1=362,880` possible games

However, I can logically narrow that number down considerably.

First Move Reduction

There really isn't 9 first moves.  There is really only 3 first moves.  This being that if you make a move in a corner, I can rotate the board and create the exact same board, regardless of which corner you place your mark in.

Likewise with the middle square and the center edge square.  

So, the first move is REALLY only "the center," "an edge," or "a corner."  

X

X

X

This reduces the number of possible games to:

`3x8x7x6x5x4x3x2x1=120,960`

Second Move Reduction

Again, we can reduce the second move options from 8, to a lower number, using the same idea.  However, this gets more complex.

Suppose the first move was in the center.  The only real options for the second move it a corner or an edge.  No matter which corner you choose, the board can be rotated to create a single board with an X in the middle and a O in a corner.  Likewise with the edges.  So, this is 2 possible second moves.

X O

X O

Notice that we do not consider the upper edge.  That is because we can rotate the board such that the upper edge is in the lower position.  This proves the upper edge is the same game as the lower edge.  The same concept applies to the corners.

Now, suppose the first move was in a corner.  The second move can only be in the center, an adjacent corner, the opposite corner, an adjacent edge, or and opposite edge.  No matter which you chose, I can rotate or flip the board to create one of these 5 boards.

O X

O X

O X

O X

O X

Now, suppose the first move was on an edge.  The same thing applies as above.  The board can be rotated or flipped etc. to create one of 5 boards.

O X

O X

O X

O X

O X

So, now the first 2 moves was calculated as:

`9x8=72` moves

We now know that the total number of moves 1 and 2 is simply 12.

We can count the number of possible second-move games easily enough, but we can also average the number of second moves.  Based on the first move, there will be an average of 4 second moves:

`(5+5+2)/3=4`

so we can be sure the total number of unique games of tic tac toe cannot exceed

`3x4x7x6x5x4x3x2x1=60,480`

Third Move Reduction

We can apply similar reductions to the third move, however, notice that the impact of such reductions is losing steam.  the first reduction reduced the number of moves by 66.7% (from 9 possible moves to just 3.)  The second move reduction reduced the number of moves by 50% (from 8 possible moves to an average of 4 possible moves.)  It is reasonable to assume the third move reduction will be somewhat less than 50%.

Due to the number of grids that needs to be produced, I will only demonstrate the reduction in text, using the second move grids as a reference.  Essentially, if there is symmetry about an axis, it is likely we can reduce the number of possible moves.  This is to say a move on one side of the axis of symmetry would be equivalent to a move on the other side.  This means the two moves are the same move and we can reproduce the first option by flipping the board about the axis.

X O

Since there is symmetry about the diagonal axis, moves above the axis are the same as moves below the axis

4 Moves

 

X O

Since there is symmetry about the vertical axis, moves right of the axis are the same as moves to the left of the axis

4 Moves

 

	O
		X

O		X

O
		X

	O	X

	O
		X

	O
	X

O	X

O
	X

		O
	X

	O
	X

As this turns out, there are only 66 possible games at this point.  We have effectively reduced the 7 options for the third move down to an average of 5.5.  That is a reduction of just 21.4%.

This makes the total number of games no more than:

`3x4x5.5x6x5x4x3x2x1=47,520` games