In this visualization, we examine what Herbert Simon might call the “solution space” for tic-tac-toe, a compound visualization of all its solutions—every legal game move and the connections between them—in a single artifact.
Most of us have played tic-tac-toe. It's a deceptively simple game. Two players claim unique symbols (
O) before alternating turns in placing their symbol in an empty cell within a 3-by-3 grid. The first player to place 3 of their symbols in a row, either cardinally or diagonally, wins.
End conditions are clear; either a player wins, or the game is a draw. The myriad ways of getting there are what makes the game fun. But what does the solution to tic-tac-toe look like? Drawing a single winning combination does not do justice to the complexity of the game.
Instead, imagine a map of all possible paths from blank board to finished game. We might call this the “solution space” for tic-tac-toe, where each path is but one way to navigate through the space.
How large is the solution space? Well, for the first move, there are 9 cells available. For the second, there are 8, and so on. Follow to completion, and we get
9! boards for the final level. For each level
n of gameplay, there are
9!/(9-n)! boards in total. By adding the level totals together, we get an “upper bound” of 986,410 boards—far too many to represent meaningfully.
For the visualization to be meaningful, the number of boards must be reduced. We do this by introducing 3 rules; (1) removing duplicate boards reduces the count to 6,046, (2) removing illegal moves (play after a win) reduces the count to 5,478, and (3) by removing symmetric duplicates (rotational and reflectional) we are left with 765 unique boards. This poster displays them all in a matrix.