The hidden complexity of an apparently simple game like tic-tac-toe makes the game a valid subject for research in artificial intelligence. One measure of complexity in the domain of games is the number of unique games that can be played from the starting position to all possible end positions following the legal rules of the game. Probability theory, discrete mathematics, and combinatorics can measure this complexity of tic-tac-toe, given one assumption. We assume that all games complete with no unoccupied squares, even if 'X' or 'O' achieves an early victory before all nine squares are occupied. Given this assumption, there are
possible and unique games of tic-tac-toe. Over the course of a game, 'X' chooses five squares to play in out of nine, and he can choose to play those five moves in any order. Over the courses of a game, 'O' chooses four squares to play in out of the four remaining squares available to him, and he can choose to play those four moves in any order. There are exactly 362,880 possible and unique games of tic-tac-toe. A number of this order of magnitude is today considered tractable by computer scientists, but artificial intelligence research in tic-tac-toe is appropriate because it is both tractable and sufficiently complex.