What Does It Mean for a Game to Be "Solved"?

In mathematics and game theory, a game is called solved when the optimal strategy for every possible situation has been calculated. For a solved game, we know the outcome of perfect play before the game even begins. Tic-Tac-Toe is one of the most well-known solved games: with perfect play from both sides, the game always ends in a draw.

The Game Tree: Mapping Every Possibility

Game theorists analyze games using a structure called a game tree. Each node in the tree represents a board state, and each branch represents a possible move. The full game tree for Tic-Tac-Toe is surprisingly large:

  • There are 9! (362,880) possible ways to fill the board if all moves are made.
  • However, many games end before the board is full, bringing the number of complete game sequences down to around 255,168.
  • After accounting for symmetry (rotations and reflections of the board are equivalent), there are only 138 distinct terminal positions.

This relative smallness is exactly why Tic-Tac-Toe was one of the first games that computers could "solve" exhaustively — the game tree is manageable even for early hardware.

Zero-Sum Games and Nash Equilibrium

Tic-Tac-Toe is a zero-sum game: one player's gain is exactly the other's loss. A win for X is a loss for O; a draw is neutral for both. Under these conditions, game theory tells us that rational players will find what's called a Nash Equilibrium — a state where neither player can improve their outcome by changing their strategy alone.

For Tic-Tac-Toe, the Nash Equilibrium is the draw. Both players, playing optimally, will always converge on this outcome. Neither can force a win against a perfect opponent.

Minimax: The Algorithm of Perfect Play

The strategy used by computers (and sharp human players) to achieve perfect play is called the minimax algorithm. Here's the core idea:

  • The maximizing player (say, X) tries to choose moves that maximize their score (win = +1, draw = 0, loss = -1).
  • The minimizing player (O) tries to minimize that same score.
  • The algorithm works backwards from all possible end states, assigning values and choosing the best move at each step.

When minimax is applied to Tic-Tac-Toe's full game tree, it confirms that the best achievable outcome from both sides is always 0 — a draw. No sequence of moves by X can guarantee a win if O plays correctly, and vice versa.

First-Mover Advantage: Does It Exist?

In many games, going first is a significant advantage. In Tic-Tac-Toe, the first player (X) does have more winning chances — but only against an imperfect opponent. Against perfect play, the first-mover advantage evaporates entirely. The second player (O) can always secure a draw with correct responses.

That said, statistically, X wins more often than O in casual human play, because most players don't execute perfect defensive play consistently.

What Tic-Tac-Toe Teaches Us About Game Theory

Despite being simple, Tic-Tac-Toe is an excellent teaching tool for foundational game theory concepts:

  1. Backward induction — reasoning from the end of the game to determine the best opening moves.
  2. Perfect information — both players can see the entire board at all times, unlike card games with hidden hands.
  3. Finite determinism — the game always ends, and luck plays no role whatsoever.
  4. Symmetry reduction — using rotational and reflective symmetry to simplify analysis.

Beyond Tic-Tac-Toe

Understanding these concepts in Tic-Tac-Toe is a stepping stone to analyzing more complex games. Chess and Go are also zero-sum perfect-information games — but their game trees are astronomically larger, putting "solving" them well beyond current computing power. Tic-Tac-Toe gives us a clear, human-scale window into the same mathematical machinery that governs far more complex strategic competitions.