← the iceberg
Layer 1 · Classical AI

Unbeatable Tic-Tac-Toe

This is the founding technique of artificial intelligence, and it contains no learning whatsoever — no training data, no parameters, nothing fitted. Every turn the computer re-derives the entire future of the game from scratch: it plays out every legal continuation to the end, assumes you will answer as well as possible, and takes the branch whose worst case is best. That is minimax, and on a board this small it is not a strategy but a proof. You cannot win. You can only draw.

You are X and you move first. Pick a square.

The search behind the last move

states evaluated
time taken
verdict for O
states this game

The number is the lesson. The first move of a game costs the machine over half a million board positions; by move seven it costs a handful. Classical AI buys certainty with brute-force enumeration — which works beautifully here and collapses immediately on chess, where this same exhaustive search would need more positions than there are atoms in the observable universe.

How it works

The game is a tree: the current board is the root, each legal move is an edge, and each finished game is a leaf. Leaves are scored from O's point of view — O wins is +1, X wins is −1, a full board is 0 — and every internal node gets its score by recursion rather than by any heuristic. On O's turn the machine takes the maximum of its children's scores; on your turn it takes the minimum, because it assumes you play the best reply available to you. Moves are made and then un-made on a single shared array — that is backtracking, and it is why exploring half a million positions costs nothing in memory. Because both sides are assumed perfect and tic-tac-toe is a solved draw, the value at the root is always 0 once the machine has moved: the joke ending in this page is code that can never run.