search
Prune the adversary's replies
It is the era when machines first search adversarial game trees, and the combinatorics are merciless: each of your moves invites a reply, and a reply to that, branching past all counting within a few plies. You want the move that is best assuming the opponent answers optimally — the minimax move — without examining the astronomically many leaves a full search touches. The key realization: once a line proves worse than one already found, its remaining branches cannot change the decision and can be pruned unexamined, and good move ordering cuts the effective search enormously. Get it wrong and you search a tree so vast no move returns, or prune unsoundly and pick a move a lurking reply refutes — bounded adversarial search is the engine beneath game machines.
Who this problem belongs to
The two figures whose methods fit it best, out of 69 in contention.
Von Neumann is the reason a 'best move assuming optimal reply' is even a well-posed question. His 1928 paper 'Zur Theorie der Gesellschaftsspiele' proved the minimax theorem for zero-sum two-player games: a value exists that both players can guarantee, and the optimal strategy is defined recursively through the game tree, exactly the structure this problem asks to search. Theory of Games and Economic Behavior (1944, with Morgenstern) built the full apparatus of extensive-form games and backward induction that any adversarial search implements. He did not personally write a pruning algorithm or a chess program, and the astronomical branching of real games was not his concern; he supplied the mathematical object being searched, not the search's engineering. Everything downstream, alpha-beta included, is minimax computed cleverly rather than exhaustively — his theorem is the ground truth the pruning is proven correct against.
Shannon's 1950 paper 'Programming a Computer for Playing Chess' is the founding document of this exact problem. Writing before any machine could run his ideas, he laid out minimax evaluation of a game tree to fixed depth, an evaluation function built from material and mobility, and — crucially — distinguished 'Type A' brute-force search from 'Type B' selective search that only follows plausible moves and abandons refuted lines early, the conceptual seed of pruning. He explicitly worried about the combinatorial explosion of full-tree search and argued selectivity was necessary on any foreseeable hardware. He never implemented or proved a pruning rule; that came later, from McCarthy, Samuel, and Knuth and Moore. But minimax without touching every leaf, ordered toward plausible replies, is Shannon's 1950 framing almost verbatim, a design decades ahead of the hardware.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
69 figures are scored on this problem. Draw it in a battle to see where you land.