What is there to count in the simple game of Tic Tac Toe?
Total number of all possible game states
A game state is a legal position on a board. The tic tac toe board has nine spaces and each space can be either empty, have an “X” or have an “O”. That means that there can be at most 39 = 19,683 possible game states. Rules, or constraints, limit the actual number of game states. For example, there can be at most one more “O” than “X” (assuming “O” goes first), and once a player has won, there can be no more moves.
To find the total number of legal game states we can construct the game tree. This is a directed, acyclic graph (a “DAG”) in which a node’s children are the possible legal next moves from the current game state, and for which the root node is the empty board. First, we need to put together a function that can work out the number of next game states that follow a given boardstate. Next, we need a function that can work out if a state is terminal (which looks at a board and sees if a player has won, if it’s a tie, or if there are more moves). We can then build the function that generates the game tree and counts the number of unique nodes.
You can find all the python code for this at my github repository. Here’s a code snippet:
#Accumulate all possible states of game def accum( game: tuple, acc: set ): acc.add( game ) ns = next_states( game ); #Recurse through children for n in ns: accum( n, acc )
The result is that there are 5,478 unique legal game states.
Total number of possible logically unique game states
Any board or gamestate can be rotated by 90o, 180o and 270o, and can be reflected across four axes. The resulting “equivalence class” of up to 8 game states is a set of game states that are logically equivalent.
Try it out by setting up a game state and clicking the “Show Equivalents” button.
The total number of unique game states is 765, 13.964951 percent of all possible game states. This means that if we account for these symmetries, only that small percent of all game states need to worked out by the AI.
Total number of games:
A game is a set of moves that go from the empty board to a terminal state. The method used to find this data is a depth first tree search. In this method, the function uses the next moves function to see if the next moves from a given game board are in a terminal state. If they are not, it recursively repeats the process for those game states. If one of them is an end state, it adds it to a count.
The total number of possible games is 255,168. If you account for logically equivalent game states, there are only 26,830 possible games.
If we weigh each path with its probability, we can figure out the chance of winning, losing or drawing in a random game of tic tac toe. The result is that the player who goes first has a 58% chance of winning, a 29% chance of losing and a 13% chance of drawing.