The Minimax Chess Horizon
Type A Brute Force Versus Type B Selective Pruning Before Any Computer Played Chess
A standard chess game averages forty full moves per player, with roughly thirty legal moves available at every turn. In March 1949, at a symposium of the Institute of Radio Engineers in New York, Claude Shannon analyzed what happens when a machine tries to play perfect chess by exhausting every legal continuation. He published the full mathematical framework a year later in the March 1950 Philosophical Magazine under the title Programming a Computer for Playing Chess. Because each full move—one white reply plus one black reply—branches by roughly $30 \times 30 \approx 10^3$ possibilities, forty moves produce roughly $(10^3)^{40} = 10^{120}$ distinct game variations. A hypothetical electronic computer evaluating one million full games per second would require more than $10^{90}$ years to calculate its very first move.
At the time Shannon wrote his paper, not a single stored-program computer on Earth had ever played a game of chess. Yet Shannon realized that designing a chess program was the ideal laboratory testbed for machine decision-making. It modeled any real-world problem too complex for an exact mathematical solution. In 1928, mathematician John von Neumann had proved that chess is a finite, deterministic, two-person zero-sum game with a theoretical minimax value. Every position is objectively a forced win for White, a forced win for Black, or a draw. Because the $10^{120}$ tree makes reaching the terminal checkmate impossible, Shannon introduced the core engineering compromise that still governs artificial intelligence search today.
Instead of searching all the way to the end of the game, the machine searches forward only a fixed number of half-moves (plies). It then scores the resulting leaf positions using an approximate heuristic formula $f(P)$, which Shannon called the static evaluation function. He constructed $f(P)$ by combining material balance—assigning standard pawn weights of 9 for a queen, 5 for a rook, 3 for a bishop or knight, and 1 for a pawn—with positional terms. Those positional adjustments penalized doubled, backward, and isolated pawns while rewarding piece mobility.
Once the machine reaches the look-ahead horizon and computes $f(P)$ at the leaves, it propagates those scores backward up the tree. It alternates between maximization on the machine's turn and minimization on the opponent's turn, assuming the human opponent picks the reply that minimizes $f(P)$. Yet Shannon immediately spotted a fatal flaw in naive fixed-depth minimax search, which he named the Type A strategy.
In a Type A strategy, the computer examines every single legal move to a rigid depth of, say, three moves (six plies) and then stops cold. Suppose on the very sixth half-move White captures a defended Black pawn with the White queen. If the search stops right there and applies $f(P)$, the static formula sees White ahead by one pawn and scores the blunder as a triumph. The fixed cutoff leaves the machine completely blind to the fact that Black will recapture the queen on ply seven.
To cure that horizon blindness, Shannon formulated the Type B strategy based on two rules:
- 1. Quiescence search: Never apply the static evaluation function $f(P)$ in the middle of an active exchange, check, or piece capture; continue searching capture sequences deeper until the board reaches a quiet (quiescent) position.
- 2. Selective forward pruning: Discard obviously pointless moves early in the tree so computing cycles are concentrated on forceful tactical lines.
To test these principles in physical hardware, Shannon built a relay-based endgame chess machine around 1949–1950 (often associated with the chess muse Caissa). The cabinet played six-piece endgames using roughly one hundred and fifty relay operations and ten to fifteen seconds per move. Every championship chess engine built over the following seven decades—from Belle and Deep Blue to modern neural-network searchers—operated by combining Shannon's 1950 static evaluation scoring with selective pruning of his Type A and Type B minimax game trees.