Maths

Why Tic Tac Toe always ends in a draw

Play enough Tic Tac Toe against someone good and every game ends the same way. That isn't a coincidence. It has been proven, and the numbers behind the proof are surprisingly small.

What "solved" means

A game is solved when we know the result with perfect play from both sides. Tic Tac Toe is solved: if neither player makes a mistake, the game is a draw. The first player can't force a win, and neither can the second player.

That's a stronger statement than "good players usually draw". It means there's a strategy for each player that guarantees at least a draw against anything the other side does. You can see that strategy written as eight simple rules in how to never lose at Tic Tac Toe.

The whole game, counted

Tic Tac Toe is tiny by the standards of games. A computer can list every possible game in well under a second. Here's what you find when you do:

What's countedNumber
Different complete games (move sequences)255,168
  won by the first player131,184
  won by the second player77,904
  drawn46,080
Different board positions that can occur in a game5,478
Positions that are truly different (ignoring rotations and reflections)765
Truly different final positions138 (91 first-player wins, 44 second-player wins, 3 draws)

Notice that draws are only about 18% of all possible games, and only 3 of the 138 distinct final positions. Draws aren't common because the board makes them easy. They're common because good players avoid every one of the many paths to a loss.

For comparison, chess is estimated to have more possible positions than there are atoms in the observable universe, which is why chess is not solved.

Why the first player can't win

The proof is simply exhaustive: check every reply to every move. Working backwards from the end of the game, each position gets a label. A finished position is a win, loss or draw. Any other position takes the best label among the moves available to the player whose turn it is. This method is called minimax. Apply it to the empty board and the label comes out as a draw.

The intuition is that each attack has a defence. The centre, which lies on four lines, can always be taken or contested. Every fork the first player tries to build needs at least one free move, and a defender who follows the rules never gives one away.

A typical drawn final position

Why the second player can't win either

There's a neat argument that the second player can never have an advantage, called strategy stealing. Suppose the second player had a winning strategy. The first player could make a random first move, then pretend to be the second player and follow that winning strategy. The extra mark on the board can never hurt, because having more of your marks on the board never makes a line harder to complete. If the strategy ever asks for the square that's already taken, the first player just makes another random move. That would give the first player a win, which contradicts the assumption that the second player wins. So the second player can't have a winning strategy.

The same argument works for many games where an extra move never hurts, including bigger versions of Tic Tac Toe. It proves the first player can't be at a disadvantage, without saying how to play.

Symmetry does a lot of the work

The board looks the same after rotating it 90° or flipping it, so many positions are really the same. There are only three different first moves (corner, edge and centre), only twelve different positions after two moves, and 765 different positions overall. That's why people can learn to play Tic Tac Toe perfectly, which is impossible for chess or Go.

A draw isn't a boring result

Because perfect play draws, every decisive game between people contains a mistake. That's what makes the game interesting to play: the question isn't "can I win?" but "will my opponent find the one correct move?" Against a corner opening, for example, only one of eight replies holds the draw. The best first move explains how to make the most of that.

If you want a game that isn't a draw, try one of the variants. Several of them, such as Qubic, played on a 4 × 4 × 4 cube, are proven wins for the first player.