
TicTacToe (Naughts and Crosses, Cheese and Crackers, etc.) (January 2002)How many games of TicTacToe 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 tictactoe games. For various reasons, this is a very naive answer to the question. In fact, there was a brief followup 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 offhand comment didn't really bother me too much, since tictactoe wasn't the topic of discussion. But the followup discussion seemed hopelessly naive. Just to start with, the board itself has 8fold symmetry. Still, dividing their answer by eight still misses the mark substantially. I hope that I've done a little better. 
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 twofold 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?








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 eightfold 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?
Let's consider the following game path.





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 tictactoe rule which requires a player to take a win, or to block, even though it is a good idea.
Normally we consider a game of tictactoe to end when one player makes three in a row, or when the board is full. But consider the following game:





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.
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:
Once we've answered these three questions, there should be only one answer to the number of tictactoe 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 tictactoe 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".
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 tictactoe 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:



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 Paths  Terminal Paths /8 

0  1  1  
1  9  9  
2  72  72  
3  252  504  
4  756  3,024  
5  1,260  120  15,120  1,440  180 
6  1.520  148  54,720  5,328  666 
7  1,140  444  148,176  47,952  5,994 
8  390  168  200,448  72,576  9,072 
9  78  78  127,872  127,872  15,984 
Total  5,478  958  255,168  31,896 
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 spotchecked 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:



or 



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:



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 

0  1  1  
1  3  3  
2  12  12  
3  38  66  
4  108  360  
5  174  21  1,710  172 
6  204  21  5,992  579 
7  153  58  15,878  5,115 
8  57  23  20,964  7,426 
9  15  15  13,538  13,538 
Total  765  138  26,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.
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 fullydetermined 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 Paths  Terminal Paths /8 

0  1  1  
1  9  9  
2  72  72  
3  252  504  
4  756  3,024  
5  1,260  124  15,120  1,488  186 
6  1,520  312  54,528  11,040  1,380 
7  1,136  640  130,464  59,040  7,380 
8  390  390  142,848  142,848  17,856 
Total  5,396  1,466  214,416  26,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.
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 

0  1  1  
1  3  3  
2  12  12  
3  38  66  
4  108  360  
5  174  22  1,710  178 
6  204  46  5,974  1,212 
7  152  87  14,066  6,393 
8  57  57  15,346  15,346 
Total  749  212  23,129 
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 

0  1  1  
1  3  3  
2  12  12  
3  38  66  
4  108  360  
5  167  21  1,080  172 
6  196  21  2,458  366 
7  138  58  3,940  1,460 
8  48  23  3,940  1,043 
9  9  9  2,897  2,897 
Total  720  132  5,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 

0  1  1  
1  3  3  
2  12  12  
3  38  66  
4  108  54  360  172 
5  146  94  908  493 
6  121  87  1,604  878 
7  60  41  2,119  1,191 
8  23  23  1,856  1,856 
Total  512  299  4,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 

0  1  1  
1  3  3  
2  12  12  
3  38  11  66  19 
4  54  24  169  58 
5  77  62  465  317 
6  35  31  546  435 
7  10  10  316  316 
Total  230  138  1,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"?
To my thinking, there are 1145 possible games of tictactoe, 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,