The Mathematics of Tic-Tac-Toe

We all remember tic-tac-toe as a simple game. Young children find it easy to learn, and enjoy playing it. As they get older, they come to understand how to play the game strategically and not lose. When two experts play, the game will always result in a tie.

A tic-tac-toe board is a 3×3 grid. If I were to fill in each of the nine spaces with a unique value (like 1, 2, 3, 4, 5, 6, 7, 8, 9), then I’d have nine choices for filling the first slot, eight choices for filling the second slot, and so on and so on. Counting this way, I’d have 9*8*7*6*5*4*3*2*1 = 9! (read “9 factorial”) = 362,880 ways to fill the board.

In actuality, tic-tac-toe players fill in each of the nine entries with one of only three values: an X, an O, or leave it blank. That’s a total of 3*3*3*3*3*3*3*3*3 = 3^9 = 19,683 different ways the 3×3 grid can be filled in.

The goal of the game in tic-tac-toe is to get three in a row – horizontally, vertically, or diagonally. Play continues until someone achieves this goal or all the spaces are filled with X’s and O’s.

While the minimum number of moves to win a game is five, the maximum number of moves in any game is nine, filling the board with only X’s and/or O’s. In that case, there are only 2^9 = 512 different final filled boards.

But wait a minute. That includes things like a board filled all by X’s. That’s not really a valid state because in a real tic-tac-toe game, there are two players taking turns. Let’s assume that player one, who marks his spaces with X, goes first. Player two, who marks his spaces with O, goes next. The players continue to alternate taking moves until the board is filled, now containing 5 X’s and 4 O’s. How many valid filled boards are there?

Unlike in the original case we considered, these nine entries are not unique. An X placed in one grid position is indistinguishable from an X placed in another grid position, and ditto for the O’s. So we have to divide out the previously counted 5! permutations of the X’s, and the 4! permutations of the O’s. This leaves us with a total number of final filled boards containing 5 X’s and 4 O’s of 9!/(5!*4!) = 126.

Now let’s look at some specific boards under rotation and reflection. Consider the board

		OXO 
		XXX 
		OXO

If I rotate this board clockwise by 90, 180, and 270 degrees, I end up with the same board. If reflect it horizontally, vertically, and across both diagonals, I still get the same board back. We say that this board has an orbit of 1. There is one other board of orbit 1, namely

		XOX 
		OXO 
		XOX

Consider now the board

		OOO 
		XOX 
		XXX

Under rotation and reflection, this board can become

		XXO		XXX		OXX 
		XOO		XOX		OOX 
		XXO		OOO		OXX

We say this board has an orbit of 4, that is, there are four different boards we can get to by rotating and reflecting the original board. There are in fact eleven boards that have an orbit of 4. Finally, there are another ten boards that have orbits of 8. So in total, there are 2 + 11 + 10 = 23 unique boards which, when rotated and reflected, end up giving us all 126 boards we found earlier. There are more sophisticated mathematical methods for calculating the number of unique boards – using something called Burnside’s Lemma – which you can learn more about here: https://www.youtube.com/watch?v=wdDF7_vfLcE

The important thing to take away from this discussion is that even simple games like tic-tac-toe have some very sophisticated mathematical principles underlying them. We will investigate more about the mathematics of other games in future blogs.