On this page
A chess computer searches: it tries moves, tries the replies, and scores where each line ends. Newer engines add a learned sense of which positions are good. Below you will trace the search on a tic-tac-toe board with a pencil.
How do chess computers decide the best move?
The recipe goes back to Claude Shannon's 1950 paper Programming a Computer for Playing Chess. An evaluation function is a rule that turns a position into a number; Shannon's example started from piece values of about 9, 5, 3, 3 and 1 for queen, rook, bishop, knight and pawn. The computer looks a few moves ahead, scores the positions it reaches, and works backwards to a move.
Why not look all the way to checkmate? Shannon estimated about 30 legal moves in a typical position, so about 1,000 possibilities for a move by White and Black's reply, over a game of about 40 moves. That gives about 10 to the power 120 variations, and he worked out that a fast machine would need over 10 to the power 90 years to calculate the first move (Shannon, 1950). So every engine searches only part of the tree. Our profile of Claude Shannon and how to measure information in bits tells more of his story.
What is minimax?
Minimax means choosing the move whose worst outcome, if your opponent always replies as well as possible, is the best. Levels alternate: on your turn a position is worth the maximum of its children, on your opponent's turn the minimum. Shannon cites the 1944 game theory of John von Neumann and Oskar Morgenstern; see John von Neumann: games, computers and quantum mechanics.
Trace it by hand: a tic-tac-toe position
Number the squares 1 to 9, left to right, top to bottom. It is X's turn:
Top row (1, 2, 3): X, O, O
Middle row (4, 5, 6): empty, empty, X
Bottom row (7, 8, 9): O, X, empty
Score a finished game +1 if X wins, −1 if O wins, 0 for a draw. X can play 4, 5 or 9.
X plays 4. O replies at 5, completing 3-5-7: −1. (O's other reply, 9, lets X win at 5: +1.) O minimises, so square 4 is worth −1.
X plays 5. X now threatens 4-5-6 and 1-5-9. Whichever square O blocks, X wins at the other: +1 either way. Square 5 is worth +1.
X plays 9. O's first reply, 5, wins for O: −1. Stop. X already has +1 from square 5, so X will never choose 9, and O's other reply does not matter.
X maximises: square 5, worth +1, a fork the search finds without knowing what a fork is. The diagram at the top is this tree.
How does alpha-beta pruning save work?
Skipping branches as in step 3 is called alpha-beta pruning. Donald Knuth and Ronald Moore published a mathematical analysis of it in 1975 in Artificial Intelligence. Order matters: searching square 5 first lets you stop after one reply to both 4 and 9, skipping two lines, not one. So engines try promising moves first.
Speed helps too. IBM says Deep Blue could evaluate 200 million chess positions per second, and in May 1997 it became the first computer to beat a reigning world champion, Garry Kasparov, in a match under standard tournament controls.
How do engines like AlphaZero learn from self-play?
Shannon's scoring rules were written by people. DeepMind's AlphaZero learned its own. In a 2017 preprint by David Silver and colleagues, it started from random play, knowing only the rules, and reached superhuman play in chess, shogi and Go within 24 hours. Its neural network takes a position and outputs a probability for each move and a value estimating the result. After games against itself, the network is adjusted so its probabilities match what its search preferred and its value matches who won.
Instead of alpha-beta, it uses Monte Carlo tree search: many simulated games, favouring moves the network rates highly. It searched about 80 thousand positions per second in chess, against 70 million for Stockfish, the 2016 Top Chess Engine Championship winner. It outperformed Stockfish after 4 hours of training, and in a 100-game match at one minute per move won 28, drew 72 and lost none (Silver et al., 2017); a peer-reviewed version followed in Science.
The two approaches have since met: in August 2020 Stockfish added NNUE, a neural network trained on the evaluations of millions of positions, whose scores feed its alpha-beta search.
How can you use this in your own problem-solving?
The habit suits a tricky proof too: list options, find the strongest counter, drop what fails. For any game tree:
Number the positions so you can name every move.
Fix the scoring first (+1, 0, −1).
Label each level max or min.
Score the bottom, then work upwards.
Try the most promising move first.
Minimax is recursive, so our guide to recursive methods in ISC Class 12 Java is a good next step if you code. If you want someone to check your tree as you build it, Fermi's AI tutor notices where you are stuck and decides whether to explain, ask or show.
