The Thinking Machine Chronicles #0016: Programming a Computer to Play Chess: Shannon's Blueprint for Game-Playing AI

Era 1 · The Foundations (1936–1955) The man who had just told the world how to measure information turns his attention to a board game. His paper on chess is brief, technical, and almost playful, and it contains the design of every game-playing AI ever built.

The World in 1950

The same year that Turing asked whether machines could think, the world was discovering new ways to kill more people more efficiently. The Korean War, which began in June 1950 when North Korean forces crossed the 38th parallel, drew American, British, Australian, and eventually Chinese forces into a conflict that would cost three million lives before its armistice in 1953. President Truman's decision in January to develop the hydrogen bomb had shifted the nuclear competition onto a new order of magnitude; the first H-bomb test was two years away. In Europe, the Schuman Declaration of May 1950 proposed pooling French and German coal and steel production under a common authority, the seed of what would become the European Union, conceived explicitly as a mechanism to make another European war economically impossible.

The technological landscape was still dominated by vacuum tubes. ENIAC had been running for four years; the Manchester Baby and EDSAC were operational. IBM was still primarily a punch-card machinery company; its first stored-program computer, the IBM 701, would not ship until 1952. Claude Shannon, at Bell Labs, had published his mathematical theory of communication in 1948 and spent 1949 extending it to cryptography. By 1950 he was thinking about something that seemed utterly impractical: programming one of these rare, expensive, room-sized machines to play chess.

Shannon's Chess Paper

Claude Shannon's "Programming a Computer for Playing Chess" was published in Philosophical Magazine in March 1950. It runs to about 25 pages, is entirely readable without advanced mathematics, and contains a complete design specification for a chess-playing program. Shannon never implemented it, he had no suitable computer available,but the design was so well conceived that every serious chess program built in the following decades implemented some version of it.

The paper opens with a frank acknowledgement that chess-playing computers would, for the foreseeable future, play badly. Shannon was not trying to build Deep Blue. He was asking a more fundamental question: what is the algorithm by which a computer could choose legal chess moves, and what is the minimum structure that algorithm needs to have?

His answer has three components: a game tree, an evaluation function, and a search strategy.

The Game Tree and Minimax

A chess position can be described as a node in a game tree. From any position, white has $B_w$ legal moves and black has $B_b$; the branching factor for chess is roughly 30–35 at typical positions. Looking ahead $d$ half-moves (plies) produces a tree with approximately $35^d$ nodes:

$N(d) \approx B^d$

At $d = 2$ (one full move for each player), $N \approx 1{,}225$. At $d = 4$, $N \approx 1.5 \times 10^6$. At $d = 40$ (a typical game), $N \approx 10^{62}$, larger than the number of atoms in the observable universe. Exhaustive search is impossible in principle; the game tree of chess has been estimated at $10^{43}$ legal positions.

Shannon's key insight was that you do not need to search the entire tree. You need to search to a fixed depth $d$, evaluate the leaf nodes (the positions reached at depth $d$) with a static evaluation function $f(\mathbf{p})$, and then apply the minimax rule: white maximises, black minimises.

$V(\mathbf{p}, d) = \begin{cases} f(\mathbf{p}) & \text{if } d = 0 \\ \max_{m \in M_W(\mathbf{p})} V(\text{apply}(m, \mathbf{p}), d-1) & \text{if white to move} \\ \min_{m \in M_B(\mathbf{p})} V(\text{apply}(m, \mathbf{p}), d-1) & \text{if black to move} \end{cases}$

where $M_W(\mathbf{p})$ and $M_B(\mathbf{p})$ are the sets of legal moves for white and black from position $\mathbf{p}$. The minimax value $V(\mathbf{p}, d)$ is the best outcome white can achieve, assuming black plays optimally to depth $d$.

The Evaluation Function

The hardest part of Shannon's scheme is the evaluation function $f(\mathbf{p})$, which must assign a numerical score to a chess position. Shannon proposed a simple material-plus-mobility function:

$f(\mathbf{p}) = 200 \cdot (K_W - K_B) + 9(Q_W - Q_B) + 5(R_W - R_B) + 3(B_W + N_W - B_B - N_B) + (P_W - P_B) + 0.1 \cdot (M_W - M_B) - 0.5 \cdot (D_W + D_B + I_W + I_B) + 0.1 \cdot (S_W - S_B)$

where the uppercase letters count kings ($K$), queens ($Q$), rooks ($R$), bishops ($B$), knights ($N$), and pawns ($P$), $M$ is the number of legal moves (mobility), $D$ is the number of doubled pawns, $I$ is the number of isolated pawns, and $S$ is the number of squares controlled. The coefficients are Shannon's estimates; they closely match the values modern engines still use for simple position analysis.

This evaluation function captures two things: material (how many pieces does each side have, weighted by their standard values) and positional factors (mobility, pawn structure). Shannon acknowledged that a grandmaster would use dozens of additional factors, but the point was that even a crude function, combined with deep enough minimax search, could produce playable chess.

Type A vs Type B Strategy

Shannon identified a fundamental choice in search architecture that has never gone away:

Type A (brute force): Search all legal moves to a fixed depth $d$. Simple to implement; consistent; blind to tactical patterns; expensive because most moves are bad.

Type B (selective): Search only the "plausible" moves, those that look promising by some quick heuristic,but search them more deeply. Faster; potentially much stronger; but requires a reliable move filter that doesn't prune away the best move.

Shannon recommended Type B for the long run, noting that human chess players are Type B strategists: a grandmaster does not mentally follow every legal continuation to depth 6; they identify two or three candidate moves and analyse those deeply. The problem is that building a reliable plausibility filter requires solving a large part of the problem you're trying to solve.

Most programs built in the 1950s and 1960s used Type A because the plausibility filter was too hard to get right. Only with the arrival of alpha-beta pruning (which dramatically reduces the cost of Type A search) and later neural network evaluation functions (which solve the plausibility problem) did Type B approaches become dominant.

The Code: Shannon Chess Engine

The companion project implements Shannon's original design: a minimax search to configurable depth with the Shannon evaluation function and alpha-beta pruning. The core search is:

def minimax(pos: Position, depth: int, alpha: float, beta: float,
            maximising: bool) -> float:
    if depth == 0 or pos.is_terminal():
        return evaluate(pos)
    if maximising:
        best = -math.inf
        for move in pos.legal_moves():
            val  = minimax(pos.apply(move), depth - 1, alpha, beta, False)
            best = max(best, val)
            alpha = max(alpha, val)
            if beta <= alpha:
                break           # beta cut-off
        return best
    else:
        best = math.inf
        for move in pos.legal_moves():
            val  = minimax(pos.apply(move), depth - 1, alpha, beta, True)
            best = min(best, val)
            beta = min(beta, val)
            if beta <= alpha:
                break           # alpha cut-off
        return best

The full project implements a simplified 8×8 board, legal move generation for all piece types, the Shannon evaluation function, alpha-beta minimax to depth 3, and a demo game showing the engine's decisions.

Why It Mattered

Shannon's chess paper mattered because it turned game-playing into a solved problem at the level of algorithm design, leaving only engineering. The minimax tree with a static evaluation function is a complete specification: given enough search depth and a sufficiently accurate evaluation function, the program will play arbitrarily well. This clarity, that game AI is fundamentally a search problem,gave researchers a concrete, measurable goal that could be attacked incrementally.

The paper also introduced the concept of the evaluation function as a general tool for AI. Any problem that can be framed as a search over a state space can use the Shannon structure: generate successors, evaluate leaf nodes, propagate values toward the root. This structure appears in every domain where AI search is used: theorem proving, logistics planning, protein structure prediction, Go, and eventually reinforcement learning in games with perfect information.

The historical impact was direct: Newell, Shaw, and Simon at RAND and Carnegie Tech read Shannon's paper and used it as a starting point for the Logic Theorist (1956) and the General Problem Solver (1957). The Dartmouth Summer Research Project in 1956, the event that coined the term "artificial intelligence",listed Shannon as a participant and his chess paper as background reading. Every research programme in game-playing AI from 1950 to Deep Blue (1997) and AlphaGo (2016) is a descendent of Shannon's 25 pages.

What Came Next

Shannon's chess algorithm provided the search machinery; but before game-playing AI could develop, someone had to prove that the weighted-connection ideas of McCulloch, Pitts, and Hebb could be built in hardware, not as a program running on a general-purpose computer, but as a dedicated physical machine. In 1951, a twenty-four-year-old Harvard student named Marvin Minsky did exactly that. His SNARC machine,forty vacuum-tube neurons with motor-driven potentiometers, navigated a maze through reinforcement alone, without any explicit programming. That is the next story: The Thinking Machine Chronicles #0017: SNARC: Minsky Builds the First Neural Network Machine at 24.

---

References

1. Shannon, C.E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Series 7, 41(314), 256–275. The source text; the complete design of the minimax chess engine.
2. Newell, A., Shaw, J.C., & Simon, H.A. (1958). Chess-Playing Programs and the Problem of Complexity. IBM Journal of Research and Development, 2(4), 320–335. The first serious implementation effort, extending Shannon's ideas.
3. Knuth, D.E. & Moore, R.W. (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence, 6(4), 293–326. The definitive mathematical analysis of the alpha-beta algorithm that Shannon anticipated.
4. Levy, D. & Newborn, M. (1991). How Computers Play Chess. Freeman. The full history from Shannon's paper to Deep Thought, written by participants.
5. Campbell, M., Hoane, A.J., & Hsu, F-h. (2002). Deep Blue. Artificial Intelligence, 134(1–2), 57–83. The system that defeated Kasparov, tracing the lineage from Shannon through Berliner, Newborn, and Hsu.
6. Silver, D. et al. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815. AlphaZero, which replaces Shannon's hand-coded evaluation function with a learned neural network, while keeping the minimax search structure.