games
Beat the world champion
It is 1996 at IBM, and a match is signed that the company cannot afford to lose twice: Deep Blue against Garry Kasparov, the strongest chess player who has ever lived. Build the machine — custom search hardware evaluating two hundred million positions a second, an evaluation function tuned with grandmaster help, an opening book, and endgame databases — and decide how to spend the budget between raw search depth and chess knowledge. Kasparov adapts between games; the machine's flaws will be probed by the best pattern-matcher on earth, on television. Lose and machine intelligence stays a punchline; win ugly, through a glitch Kasparov calls a human hand, and the victory is disputed for years. Both happened. Design for scrutiny as much as strength.
Who this problem belongs to
The two figures whose methods fit it best, out of 57 in contention.
Deep Blue is, in the most literal engineering sense, Shannon's 1950 'Type A' strategy realized at a scale he could only estimate on paper: raw, brute-force minimax search to fixed depth, evaluating on the order of two hundred million positions per second on custom silicon, exactly the strategy he named and costed against the alternative selective 'Type B' approach 46 years earlier. His paper also specified the material-and-mobility evaluation function as the natural starting point, refined for Deep Blue with grandmaster input rather than hand-tuned by Shannon himself, and his framing of the combinatorial explosion is precisely why Deep Blue needed custom hardware rather than general-purpose computing. He did not build the machine or negotiate the 1997 rematch, but the design philosophy IBM's team actually executed is his blueprint, engineered up by four decades of Moore's Law.
Knuth's rigorous analysis of alpha-beta pruning (with Ronald Moore, 1975) established the theoretical foundation that made Deep Blue's brute-force search tractable at all: proving that with good move ordering, the algorithm examines roughly the square root of the nodes a full minimax search would touch, directly determining how much effective search depth a fixed compute budget of two hundred million positions per second could buy. Deep Blue's engineers depended on exactly this kind of provable efficiency to decide how to spend their hardware budget between raw depth and chess knowledge, the tradeoff this problem explicitly names. Knuth did not himself build chess hardware or work on the 1996–1997 IBM project; his contribution is the foundational algorithmic theory the engineering team built on top of, one layer removed from the applied system-design decisions this problem specifically describes.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
57 figures are scored on this problem. Draw it in a battle to see where you land.