Tic-Tac-Toe holds a special place in the history of computing and artificial intelligence. It was one of the first games to be completely solved — meaning the outcome of every possible position is known with certainty. This article explains what “solved” means, how computers achieve it, and why this simple game became a cornerstone of game theory education.

What Is a Solved Game?

A game is solved when an algorithm can determine the outcome from any legal position, assuming both players play optimally. For Tic-Tac-Toe, the solution is straightforward: optimal play from both sides always results in a draw. X cannot force a win, and neither can O.

Solved games fall into three categories:

  • Ultra-weakly solved — the outcome of the initial position is known, but a full strategy may not be computed.
  • Weakly solved — a strategy exists that achieves the optimal result from the starting position.
  • Strongly solved — the outcome is known for every legal position, not just the start. Tic-Tac-Toe is strongly solved.

The Game Tree

A game tree is a diagram of every possible sequence of moves. The root node is the empty board. Each branch represents a move, and each leaf node is a terminal state — win for X, win for O, or a draw.

For Tic-Tac-Toe:

  • There are 255,168 total possible games (sequences of moves from start to finish).
  • There are 5,478 distinct legal board positions (unique arrangements of marks).
  • Of all possible games, 131,184 are won by X, 77,904 are won by O, and 46,080 end in draws.

These numbers assume that play continues until a win or a full board, and that rotations and reflections are counted separately.

The Minimax Algorithm

Minimax is the foundational algorithm for solving two-player, zero-sum, perfect-information games. It works by assigning a value to each terminal position:

  • +1 if X wins
  • -1 if O wins
  • 0 if the game is a draw

The algorithm then works backward through the tree. At positions where it is X’s turn, it picks the move with the maximum value (X wants to win). At positions where it is O’s turn, it picks the move with the minimum value (O wants X to lose). By propagating these values up to the root, minimax determines the optimal move from any position.

For Tic-Tac-Toe, minimax evaluates the complete tree and confirms that the root value is 0 — a draw — when both sides play perfectly.

Alpha-Beta Pruning

Even though Tic-Tac-Toe’s game tree is small enough to search exhaustively, the technique of alpha-beta pruning is worth understanding. It is an optimization of minimax that skips entire branches of the tree when it can prove they will not affect the final result.

Alpha-beta pruning maintains two values:

  • Alpha — the best value X can guarantee so far.
  • Beta — the best value O can guarantee so far.

When alpha exceeds beta in any branch, that branch is “pruned” — there is no reason to explore it further. In Tic-Tac-Toe, alpha-beta pruning can reduce the number of positions evaluated by roughly half. In more complex games like chess, the savings are even more dramatic.

OXO — The First Computer Opponent

In 1952, Alexander “Sandy” Douglas created OXO as part of his doctoral thesis at the University of Cambridge. Running on the EDSAC vacuum-tube computer, OXO allowed a human to play Noughts and Crosses against the machine using a rotary telephone dial for input and a cathode-ray tube for display.

OXO played perfectly — it would never lose. The program is considered one of the earliest video games and one of the first demonstrations of a computer playing a game using artificial intelligence.

Why Tic-Tac-Toe Matters to Computer Science

Despite its simplicity, Tic-Tac-Toe is a remarkably effective teaching tool for several foundational concepts:

  • Recursion — minimax is naturally recursive, making it an ideal introduction to recursive thinking.
  • Tree traversal — exploring the game tree teaches depth-first and breadth-first search patterns.
  • Adversarial search — the game introduces the idea that the “opponent” is actively working against you, a concept central to all game-playing AI.
  • Complexity scaling — comparing Tic-Tac-Toe’s tiny game tree to chess’s incomprehensibly large tree illustrates how combinatorial explosion works.

Nearly every introductory AI or algorithms course includes Tic-Tac-Toe as a project or example for these reasons.

From Tic-Tac-Toe to Chess and Beyond

The same minimax framework that solves Tic-Tac-Toe scales up (with additional techniques) to far more complex games. Checkers was fully solved in 2007. Chess and Go remain unsolved, but engines using minimax descendants, neural networks, and Monte Carlo tree search play at superhuman levels. It all started with three marks in a row on a tiny grid.

For a detailed look at the specific positions and outcomes, see our article on perfect play and every possible outcome.