Tic-Tac-Toe

Tic-tac-toe — noughts and crosses outside North America — is played on a three-by-three grid. X moves first, players alternate, and the first to line up three of their own marks in a row, a column or a diagonal wins. If all nine squares fill with no line, the game is a draw. This board plays either two people on one device or a computer opponent at three strengths, and it keeps a running tally of wins and draws until you change the settings.

Why nobody wins

Tic-tac-toe is a solved game, and the solution is a draw: if neither player makes a mistake, every game ends with the board full and no line made. That is not a claim about how people usually play, it is a complete result. The game tree is small enough to walk in full — 255,168 distinct games, of which 131,184 end in a win for X, 77,904 in a win for O and 46,080 in a draw — and only 5,478 board positions are reachable at all. The opponent on this page at its highest setting searches that tree exhaustively, so it can be drawn but never beaten.

X's large share of those 255,168 games is a fact about careless play, not about the opening: it counts every line a losing O could have taken. Under best play all nine opening squares draw, which is why the computer opens somewhere different each game rather than replaying one memorised line at you.

How to play well

Two rules cover almost every position. First, if you can complete a line this turn, do it. Second, if your opponent can complete a line next turn, block it. A player who applies both consistently will never lose to a careless opponent — that is exactly what the Medium setting here does, and it is enough to punish inattention.

What Medium misses is the fork: a move that creates two threats at once, so the block that stops one lets the other through. Forks are what separate competent play from perfect play, and building or preventing them is the only real skill in the game. The classic trap is the opening corner: the search rates the center as O's only non-losing reply to it, so every other answer hands X a fork. Mirrored, the only safe replies to a center opening are the four corners — take an edge instead and best play forks you.

The three computer levels

Easy takes a win that is sitting in front of it and otherwise plays a random empty square — it will not block you. Medium adds the block: it wins when it can, stops you when you threaten, and is otherwise random, so it loses to a fork but not to carelessness. Perfect runs a full minimax search of every continuation on every turn, scoring a win as better the sooner it arrives, so it takes the quickest win available and, when it is losing, picks the longest road there. Against Perfect, a draw is the best result available to anyone.

Where it comes from

Three-in-a-row games are ancient: the Romans played terni lapilli on scratched grids, and Three Men's Morris, its close relative, is older still. The modern name and ruleset settled in Britain as noughts and crosses in the nineteenth century. It also has a place in computing history — OXO, written by A. S. Douglas on Cambridge's EDSAC in 1952, was among the first graphical computer games, and the game has been a standard first exercise in game-tree search ever since, precisely because the whole tree fits in memory.