Combinatorics
Despite its apparent simplicity, Tic-tac-toe requires detailed analysis to determine even some elementary combinatory facts, the most interesting of which are the number of possible games and the number of possible positions. A position is merely a state of the board, while a game usually refers to the way a terminal position is obtained.
Naive counting leads to 19,683 possible board layouts (39 since each of the nine spaces can be X, O or blank), and 362,880 (i.e. 9!) possible games (different sequences for placing the Xs and Os on the board). However, two matters much reduce these numbers:
- The game ends when three-in-a-row is obtained.
- The number of Xs is always either equal to or exactly 1 more than the number of Os (if X starts).
The complete analysis is further complicated by the definitions used when setting the conditions, like board symmetries.
Number of terminal positions
When considering only the state of the board, and after taking into account board symmetries (i.e. rotations and reflections), there are only 138 terminal board positions. Assuming that X makes the first move every time:
- 91 unique positions are won by (X)
- 44 unique positions are won by (O)
- 3 unique positions are drawn
Number of possible games
Without taking symmetries into account, the number of possible games can be determined by hand with an exact formula that leads to 255,168 possible games (see Henry Bottomley, 2001, or Steve Schaeffer, 2002). Assuming that X makes the first move every time:
- 131,184 finished games are won by (X)
- 77,904 finished games are won by (O)
- 46,080 finished games are drawn
If board symmetries are taken into account, two games are considered the same if rotating and/or reflecting the board makes one of the games into a copy of the other game. With the use of a computer, Steve Schaeffer found in 2002 that the number of games in these conditions is 26,830.
