games
Prune the game tree, provably
It is 1975 at Stanford, and every chess program alive leans on the same folk trick: stop searching a branch the moment it is refuted. Alpha-beta pruning is ubiquitous and unanalyzed. Analyze it exactly — prove how much of the tree the algorithm must visit in the best case and the expected case, show that with perfect move ordering it searches roughly the square root of the full tree, and thereby doubles the reachable depth for free. The result must be a theorem about all game trees, not a benchmark on one program. Get it wrong and the field tunes its searchers by superstition, unable to say whether the next speedup should come from hardware, ordering heuristics, or a smarter cutoff — a decade of engineering aimed by folklore.
Who this problem belongs to
The two figures whose methods fit it best, out of 55 in contention.
This problem is Knuth's own paper. With Ronald Moore, he published 'An Analysis of Alpha-Beta Pruning' in Artificial Intelligence in 1975, precisely at Stanford, precisely turning the folk algorithm this problem describes into a proven theorem: he established worst-case and best-case bounds on the number of leaf nodes alpha-beta must visit, and showed that with perfect move ordering the algorithm examines close to the square root of the nodes a full minimax search would touch, roughly doubling the reachable search depth for free at fixed cost. This is exactly the 'theorem about all game trees, not a benchmark on one program' the problem demands. His broader career analyzing algorithms rigorously (The Art of Computer Programming) is the general skill this specific paper applied to exactly this specific question. No one else on this roster owns this problem more completely.
Pearl's rigorous analysis of game-tree search algorithms, including his study of the SSS* algorithm and best-first strategies in Heuristics (1984), extended and complemented Knuth and Moore's alpha-beta analysis by proving properties about alternative algorithms and characterizing when alpha-beta is asymptotically optimal among a broad class of directional search procedures — precisely the kind of theorem-level rigor about game trees in general, not any one program, that this problem demands. His work arrives roughly a decade after Knuth and Moore's original 1975 result and builds on rather than originates the specific alpha-beta proof this problem describes. His relevance is a strong, direct extension of exactly this research program, one step behind Knuth's founding analysis but squarely within the same rigorous tradition.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
55 figures are scored on this problem. Draw it in a battle to see where you land.