## Mathematical Recreations

 MathRec Home Last Month's Problem Introductory Problem Older Problemsand Links Educational Resources Steve's Personal Page

#### Tic-Tac-Toe (Naughts and Crosses, Cheese and Crackers, etc.) (January 2002)

How many games of Tic-Tac-Toe are there?

This is another question which was prompted by a comment in a Mathematical Recreations article in Scientific American. As I recall, the author made an offhand remark about 9! (that is, 362,880) being the number of possible tic-tac-toe games. For various reasons, this is a very naive answer to the question. In fact, there was a brief follow-up discussion prompted by various readers who complained that the game ends when either player gets three in a row, and a revised figure was provided which was somewhat less than 9!.

The off-hand comment didn't really bother me too much, since tic-tac-toe wasn't the topic of discussion. But the follow-up discussion seemed hopelessly naive. Just to start with, the board itself has 8-fold symmetry. Still, dividing their answer by eight still misses the mark substantially.

I hope that I've done a little better.

#### What is a unique move?

How many possible moves are there to open the game? Personally, I would say three, but there are at least two other reasonable answers. The first player must play in a corner, a side, or the center. Those are the three basic choices, but there are four corners and four sides. If you consider the choice of corner to be relevant, then your answer might be nine. In addition, either X or O may play first, so you might recognize eighteen possibilites. (I suppose someone might reconize the symmetry of the board without recognizing the symmetry of the players. Then there are six possible opening moves.)

This level of discussion is adequate for the first three moves. Since the order of the players only contributes an overall factor of two to our answer, we'll recognize that symmetry and say that there are either three or nine opening moves. If we recognize the symmetry of the board, then there are five possible responses to an opening move in a corner or a side, and two possible responses to an opening move in the center. If you don't recognize the symmetry of the board, then there are eight possible responses to any opening move. So after two moves, there are either twelve or 72 possible games. After two moves, there are six positions with two-fold symmetry (each of which has four possible responses) and six positions with no remaining symmetry (each of which has seven possible responses). Therefore, through three moves you will either say that there are 66 possible games or that there are 504 possible games.

Now it gets more complicated. Consider the following two game paths. Are these the same?

 X
 X O
 X O X
 X O X O
 X
 O X
 X O X
 X O X O

In the first game path, the fourth move is adjacent to the first move. In the second game path, the fourth move is adjacent to the third move. This is the final symmetry to consider. If you consider these two game paths to be the same, then you would say that there are 360 possible games through four moves. If you don't recognize the symmetry of the board at all, then you would say that there are 3024 possible games. If, however, you recognize the symmetry of the board, but still consider these game paths to be different, then you would say that there are 3024/8 = 378 possible games through four moves. (Every single game is asymmetric after four moves, so you can simply divide by the eight-fold symmetry of the board.)

If you consider the game to be a sequence of choices made by the players, then these two games are the same. You would say that there are 360 possible games through four moves. Or would you?

#### What moves are allowed?

Let's consider the following game path.

 X
 X O
 X O X
 X O X O
 X O X X O

Is the fifth move valid? Is the fourth? Certainly those are poor choices. It doesn't look like either player wants to win this game. When analyzing a game, it is often useful to restrict the choices available, so that the properties of the game are easier to discover. I don't know of any tic-tac-toe rule which requires a player to take a win, or to block, even though it is a good idea.

#### When is a game over?

Normally we consider a game of tic-tac-toe to end when one player makes three in a row, or when the board is full. But consider the following game:

 X
 X O
 X O X
 X O X O
 X O X X O

Is this game over? Note that O cannot prevent X from winning. In fact, X and O conspiring together cannot prevent X from winning. If you look at the game as a series of player choices, and the game doesn't end until a player makes three in a row, then there are seven games which start with this sequence of moves. If, however, you look at the game as a series of meaningful player choices, then this game is over and X has won.

#### Well-formulated questions

Let's just reject the idea that the game is played after a player has made three in a row. That eliminates 9! as an answer. We have our three questions and some possible answers:

• What is a unique move?
• Choice of first player is distinct and every board position is distinct
• Choice of first player is arbitrary and every board position is distinct
• Choice of first player is arbitrary and board orientation is arbitrary, but once the board is oriented every position is distinct
• Choice of first player is arbitrary and only distinct player choices are distinct moves
• What moves are allowed?
• Any open square
• Players must make three in a row if possible
• Players must make three in a row if possible, otherwise must make a blocking move if possible
• When is a game over?
• When either player makes three in a row or the board is full
• When the outcome of the game is fully determined

Once we've answered these three questions, there should be only one answer to the number of tic-tac-toe games. When deciding what constitutes a unique move, the first three choices are trivially related. If the first player is a distinct choice, then there are twice as many games. If the orientation of the board is arbitrary, but once the board is oriented every position is distinct, then there are one eighth as many moves as if every position is individually distinct. I think the only proper answer to the second question is the first, although it is interesting to see the effect on the number of possible games as we make the players a bit less stupid.

This leaves us with four problems to solve if we want to determine the number of tic-tac-toe games. (And some other interesting variations where players are not allowed to make "stupid" moves...) Let's refer to the cases where the board positions are distinct as "board symmetry" and the case where we are concerned only with distinct player choices as "game symmetry".

#### Board Symmetry, Game Ends After Three in a Row

We'll do this calculation, and all others with board symmetry, as though the orientation of the board matters, but the choice of first player is arbitrary. If the game only terminated when the board was full, then there would be 9! = 362,880 different games.

Let's consider the games after five moves. How many of those have three in a row? There are eight different ways to choose the three X locations such that they form three in a row (three horizontal, three vertical and two diagonal). For each of those, there are six different ways to order the moves. O has two moves, and there are six different ways to choose the first move and five different ways to choose the second (after reserving the three locations for X).

This gives us 1,440 different games that end with three in a row after five moves. Each of these games eliminates 4! = 24 combinations from the 9! ways to fill the board.

Now consider the games after six moves. The situation is slightly complicated by the fact that X may make three in a row before O has a chance to make the sixth move. If O makes three in a row diagonally, this does not apply, so lets do that first. There are two ways to choose three locations for O's moves and six ways to order the moves for each choice. X makes three moves out of the other six locations, so there are 6!/3! = 120 different ways to choose and order X's moves. So there are 1,440 games which end with three in a row diagonally on the sixth move.

If O makes three in a row horizontally or vertically, then there are six ways to choose the three locations and six ways to order the moves. There would be 120 ways to choose and order X's moves, except that some of those 120 combinations have three in a row for X. Let's count those. For each horizontal or vertical three in a row for O, there are two ways that X could have three in row using the remaining six locations. For each of these choices, there are six ways to order X's moves, so twelve of the 120 combinations must be eliminated. We find that there are 36 ways to choose and order O's moves which result in a horizontal or vertical three in a row, and 108 ways to choose and order X's moves for each of those, resulting in 3,888 combinations.

In total, there are 5,328 games that end with three in a row after six moves. Each of these removes 3! = 6 combinations from the 9! ways to fill the board.

Now, consider the games after seven moves. There are two ways for X to have three in a row diagonally. This accounts for three of X's moves and there are six ways to choose the other move. We find a total of twelve ways to choose X's four moves resulting in three in a row diagonally. The fourth move by X must be on the diagonal for the game to end after seven moves instead of five. There are three ways to choose the fourth move. For each of these choices, there are six ways to order the other three X moves. So we find that there are eighteen different ways to order X's moves. For each of the combinations for X's moves, there are 5!/2! = 60 ways to choose and order O's three moves. So there are 12,960 different games that end with three in a row diagonally on the seventh move.

There are six different ways to make three in a row horizontally or vertically and six different ways to choose X's fourth move for each of those. For each of these 36 choices, there are eighteen ways to order X's moves, such that the fourth move completes three in a row. Once X's four moves have been chosen, there is only one way for O to make three in a row, and six ways to order those moves. Removing these six combinations from the 5!/2! = 60 different ways to choose and order O's three moves leaves 54 combinations for O's moves. This results in 34,992 games which end with three in a row horizontally or vertically on the seventh move.

In total, there are 47,952 games that end with three in a row after seven moves. Each of these removes 2! = 2 combinations from the 9! ways to fill the board.

We find that there are a total of 54,720 games which end with three in a row before the eighth move, and that these games remove a total of 162,432 combinations from the 9! ways to fill the board. There are also games which end with three in a row after eight or nine moves, but each of these removes exactly one combination from the 9! ways to fill the board. So we find that there are 9! – 162,432 + 54,720 = 255,168 different games of tic-tac-toe if every space on the board is considered distinguishable and the game ends when one player completes three in a row or the board is full.

We can quickly check our work by calculating the number of games which end after eight and nine moves.

For the game to end after eight moves when O completes three in a row diagonally, there are 216 ways to choose and order O's moves. For each of these, there are 120 ways to choose and order X's moves. There are 648 ways to choose and order O's moves such that O completes three in a row horizontally or vertically. There are two ways to choose and 24 ways to order X's four moves such that X would also have three in a row. Removing these from the 120 combinations leaves 72 ways to choose and order X's moves. So 72,576 games end with three in a row on the eighth move.

For the game to end with three in a row after nine moves, we have another nuance to consider. Namely that X could have two instances of three in a row after choosing five locations. If this is the case, then the fifth move must complete both. Let's break this up into three cases: diagonally, horizontal or vertical, and multiple.

For X to make exactly one three in row diagonally on the ninth move, there are two ways to choose the diagonal. There are fifteen ways to choose two other locations for X, but seven of these make a second instance of three in a row for X. So there are only eight remaining. One of the three locations on the diagonal must be the final move, and there are 4! ways to order the other locations for each of those choices. This gives us sixteen ways to choose and 72 ways to order X's moves. For each of these, we have one way to choose and 24 ways to order O's moves for a total of 27,648 combinations.

For X to make exactly one three in a row horizontally or vertically on the ninth move, there are six ways to choose the three in a row. For each of those, there are fifteen ways to choose the remaining two locations for X, but five of those result in a second three in a row for X and an additional six result in three in a row for O, leaving only four choices. So there are 24 ways to choose and 72 ways to order X's moves. For each of these, we have one way to choose and 24 ways to order O's moves for a total of 41,472 combinations.

For X to make three in row twice on the ninth move, there are 22 ways to choose the two instances of three in a row. (Nine with one horizontal and one vertical, twelve with one diagonal, and one with both diagonals.) For each of these, the final move must be the position which completes both. There are 24 ways to order X's other four moves and 24 ways to order O's moves for a total of 12,672 combinations.

So that's a total of 81,792 combinations which result in three in a row on the ninth move.

Finally, there are three basic configurations which fill the board without giving either player three in a row. They are:

 X X O O X X X O O
 X X O O O X X X O
 X X O O O X X O X

There are eight orientations for the first configuration, and four for each of the others. This gives us sixteen ways to choose the locations for X and O. There are 120 ways to order X's moves and 24 ways to order O's moves for each. This gives us 46,080 combinations which result in a full board without three in a row for either player.

Adding these up, we find 1,440 games end on the fifth move, 5,328 on the sixth, 47,952 on the seventh, 72,576 on the eighth, 81,792 on the ninth with three in a row, and 46,080 on the ninth without three in a row. This adds up to 255,168 (as expected). If we recognize that rotations and reflections of the board are arbitrary, then the number of distinct games is 31,896.

For comparison with the other solutions, here is a summary table. With a little thought, this table can be produced from the preceding discussion. I generated the table by computer and checked it by hand. The final column shows the number of games which end after each number of moves if you consider reflections and rotations of the board as a whole to be equivalent.

Moves Positions Terminal Positions   Paths  Terminal PathsTerminal Paths /8
011
199
27272
3252504
47563,024
51,26012015,1201,440180
61.52014854,7205,328666
71,140444148,17647,9525,994
8390168200,44872,5769,072
97878127,872127,87215,984
Total5,478958255,16831,896

#### Game Symmetry, Terminate on Three in a Row

In this case (or the other two for that matter), I don't know of any practical way to solve the problem without the use of a computer. I've written two different programs to do this calculation on different occasions, and they agree with each other. The more recent program prints out configuration tables and I have spot-checked these by hand. I'll describe the methodology for the program, go through some of the calculation by hand, and provide the results tables. The source code is in structured Basic. I plan to eventually translate it to Perl and post it, although anyone can have a copy of the Basic code upon request.

The general strategy is to start from the known valid configuration (an empty board) and generate all valid opening moves, classifying them in such a way as to remove symmetries from the configuration. This gives a set of three possible configurations after the opening move, and the process can be repeated for the second move and so on.

Once we reach the third move, we need to recognize that there may be more than one way to generate the same configuration. For example:

 X
 X O
 X O X
or
 X
 O X
 X O X

So, each configuration must be compared against all previous configurations to ensure that there are no duplicates. At each step, therefore, I also track the number of ways that each configuration can be generated. For each opening move, there is one way to generate the configuration. (Remember that we are not treating each space as a distinguishable location. We are only tracking the choices of the players.) The same is true for the second move. Some configurations after three moves can be reached by two different paths, but others have only one possible path, such as:

 X
 X O
 X O X

In this case, if X had played in the upper right first, then both players would have made the same choices at each step in the game. There is, therefore, only one way to generate this configuration.

Finally, I track the configurations which can precede and which can follow each configuration. Once we reach five moves, we also have to recognize finished games, so that we don't generate configurations or track the number of game paths past that point.

For all terminal configurations (in this case three in a row or a full board), we can add up the number of game paths which can produce those boards. If players can make a move in any open space, and the game ends when either player makes three in a row, then there are 26,830 possible games. These results are summarized in the following table. For each move of the game, I've provided the number of reachable positions, the number of those positions which are terminal, the number of paths, and the number of terminal paths (completed games).

Moves Positions Terminal Positions  Paths  Terminal Paths
011
133
21212
33866
4108360
5174211,710172
6204215,992579
71535815,8785,115
8572320,9647,426
9151513,53813,538
Total76513826,830

That is, there are 26,830 different games, if each player is free to play in any unoccupied space, and the game ends when either player has three in a row or the board is full, and two games are the same if the players faced the same choices at each move of the game.

The link associated with each number of moves shows the possible configurations for that stage of the game. Each configuration is associated with the configurations which precede it and the ones that can follow from it. Each of the possible configurations that can follow is labeled with the expected result if each player makes the best possible move. "X Wins" indicates that X will win in all cases. "X control" indicates that X can ensure a victory no matter how O plays. "Draw" indicates that the game is a draw in all cases. "force tie" indicates that either player can prevent the other from winning.

#### Board Symmetry, Game Ends When Outcome Is Determined

Even when players are free to make stupid moves, the game may still be determined before three in a row has been achieved. The following configuration, for example, will result in a victory for X, no matter how poorly X plays:

 X O X X O

O cannot win, and X must eventually make two additional marks. Since three of the four remaining locations result in a win for X, the outcome of this game is fully determined.

After generating all valid moves, it is possible to start backward and determine which configurations will always generate the same outcome. When a fully-determined position is located, it is marked as a terminal position. After all of the terminal positions have been identified, then the number of game paths can be recalculated as before. (It's also possible to trim the game paths as you go, which is what I actually did. But it was unnecessary work.)

Here is the corresponding data when the game terminates as soon as the outcome is uniquely determined, where every position on the board is treated as uniquely distinguishable.

Moves Positions Terminal Positions   Paths  Terminal PathsTerminal Paths /8
011
199
27272
3252504
47563,024
51,26012415,1201,488186
61,52031254,52811,0401,380
71,136640130,46459,0407,380
8390390142,848142,84817,856
Total5,3961,466214,41626,802

Note that the game always ends by the eighth move. Either O gets three in a row at that point, or X makes the only remaining move.

#### Game Symmetry, Game Ends When Outcome Is Determined

Here is the corresponding data when the game terminates as soon as the outcome is uniquely determined, where two games are the same if the decisions faced by the players are the same at every point.

Moves Positions Terminal Positions  Paths  Terminal Paths
011
133
21212
33866
4108360
5174221,710178
6204465,9741,212
71528714,0666,393
8575715,34615,346
Total74921223,129

#### Pruning The Decision Tree

I deliberately separated out the process of determining valid moves. This is because it usually doesn't make sense to examine all possible moves, since you can assume that players aren't idiots. Even if a player makes an idiotic move, you can assume that the opponent will pounce on it. I've looked at two different restrictions to the moves that players are allowed to make. The first restriction is that players must complete three in a row if it is possible. These are the results of this restriction for the case where the game does not end until three in a row is made or the board is full:

Moves Positions Terminal Positions  Paths  Terminal Paths
011
133
21212
33866
4108360
5167211,080172
6196212,458366
7138583,9401,460
848233,9401,043
9992,8972,897
Total7201325,938

If we consider the game to be ended when the outcome is determined, then we get the following results:

Moves Positions Terminal Positions  Paths  Terminal Paths
011
133
21212
33866
410854360172
514694908493
6121871,604878
760412,1191,191
823231,8561,856
Total5122994,590

Finally, I think it makes sense to consider games where players will make three in a row whenever they can, but otherwise will choose to block whenever possible. There are lots of cases where a player can prevent a particular instance of three in a row, but it won't help them win the game. In fact, it might not even delay their demise. In this case, it isn't clear to me that it makes sense to require the player to make a futile blocking move. Personally, I'd concede and not even make a mark. So here are the results when players will complete three in a row if possible, and otherwise will block if possible, where the game is considered to end when the outcome is determined.

Moves Positions Terminal Positions  Paths  Terminal Paths
011
133
21212
338116619
4542416958
57762465317
63531546435
71010316316
Total2301381,145

Note that a game is always over after the seventh move. If O can win, they will do so. If they cannot win, then they will block, and if they cannot win and cannot block, then the game is a draw or X has two winning moves.

There are some other points of view that I think are worth looking at. You could assume that a player will always see and execute a forking move. This would further reduce the number of possible games. I also think it might be interesting to ask what games a perfect player could be involved in (assuming the opponent is not also a perfect player). In this case, there are two trees—one where the perfect player goes first and one where the perfect player goes second. But that opens up a whole new can of worms. Which moves are "better"?

#### Summary

To my thinking, there are 1145 possible games of tic-tac-toe, since I am reluctant to assume that a player will always see and execute a forking move if possible, but I think that it is reasonable to assume that anyone who can play and understand what they are doing will block when possible. I don't think this is the best answer to the question, though. I think it's better to stick to the rules of the game and assume that the players may be stupid.

I do think that the proper way to count the number of games is to consider the decisions faced by the players. Therefore, the best answer to the question is probably 26,830. This is what you get if you don't end the game until three in a row is completed. I think it's also fair to consider the game to be over when the outcome is fully determined. With the players free to act as stupidly as they wish, this still cuts out some meaningless paths, and gives an answer of 23,129.

Send all responses to .

Thanks,
Steve