Minimax · alpha–beta pruning
Tic-tac-toe
Three in a row wins. The computer searches the game tree with minimax and alpha–beta pruning; on Unbeatable, a draw is the best you can do. Turn on the evaluation to see how it scores every square.
Tic-tac-toe game
Arrow keys move, Enter or Space plays. Number keys 1 to 9 play a square directly.
- You
- 0
- Draws
- 0
- Computer
- 0
Settings
Each empty square shows its minimax score for the player to move, if both sides play perfectly from then on: +9 wins at once, smaller positive scores win later, 0 is a draw, negative scores lose.
How to play
Rules
Players take turns putting X and O on a 3×3 grid. The first to complete a row, a column or a diagonal wins; a full board without a line is a draw.
Play the computer or a friend on the same device, and choose your mark and who moves first.
Keyboard
- Arrow keys move between squares; Enter or Space plays the focused square.
- Number keys 1–9 play a square directly. Choose how they map under “Number keys”: 1 is top left follows reading order, like a phone keypad; 7 is top left matches the numeric keypad on a keyboard.
Screen readers hear every move and the result, and when the evaluation is on, each square’s name includes its score.
How the computer thinks
Minimax. To choose a move, the computer plays out every possible continuation to the end of the game. A finished game scores 10 − n for the side that wins on the nth move from now, minus that for the side that loses, and 0 for a draw; each side is assumed to pick the move that is best for itself. Subtracting n makes the computer prefer a quick win and, when it cannot avoid a loss, the longest defence.
Alpha–beta pruning. Many continuations never need to be looked at: as soon as one reply shows that a move is worse than an alternative already found, the rest of that move’s replies cannot change the decision and are skipped. The answer is exactly the same as full minimax, reached through fewer positions. The tests for this page check both claims: the two searches agree on every reachable position, and Unbeatable never loses to any sequence of moves, whoever starts.
Levels. Easy plays any free square. Medium looks two moves ahead: it takes a win and blocks yours, but it cannot see a fork coming. Unbeatable searches to the end and picks at random among the best moves, so games vary, but it never loses. With perfect play on both sides, tic-tac-toe is a draw.
Evaluation. “Show evaluation” writes these scores on the empty squares for the player to move: +9 wins at once, smaller positive scores win later, 0 draws, and negative scores lose against best play.