#935 1977 · Bell Labs (Ken Thompson) · Computer science & game research
Thompson solved chess endgames by starting at checkmate, computing every position backward
the problem
Computers couldn't reliably win chess endgames that even grandmasters found notoriously hard to convert
background
Chess-playing programs in the 1970s evaluated a position by searching forward from the current board a limited number of moves, scoring the resulting positions and picking the best line — a method that works well in the busy middlegame but breaks down in sparse endgames, where the correct winning plan can require dozens of precise moves with no obvious short-term gain a shallow forward search would ever value. Even strong human players routinely failed to convert theoretically won endgames like king and queen versus king and rook, because the winning technique wasn't intuitive and no textbook had ever mapped out every position exhaustively.
Improving forward search meant searching deeper, which was computationally out of reach for the hardware of the era and still wouldn't guarantee finding the objectively correct move in a position many moves from resolution. Ken Thompson, at Bell Labs, took a completely different approach: rather than searching forward from an unknown position toward an unknown outcome, he started from the only positions in the game whose value was already perfectly known — checkmate — and worked outward from there.
what everyone would do
The standard path to a better chess engine was to search deeper and evaluate positions more cleverly going forward — throwing more computing power and better heuristics at the same forward-search architecture everyone else was using, which still couldn't guarantee a provably correct move in a sparse, many-move-deep endgame.
what they saw
In a finite game, the hardest positions to solve forward are trivial backward from checkmate. Instead of searching toward an unknown answer, Thompson started at the only fixed points and let it propagate outward.
the move
Thompson used retrograde analysis: beginning with every possible checkmated position for a given set of pieces, he computed every legal position one move before it, then one move before that, and so on, backward through the entire game tree until every legal position with those pieces was assigned an exact number of moves to force a win or a draw. His 1977 king-and-queen-versus-king-and-rook (KQKR) database was the first practical result of this backward-computed approach, later extended to cover all four- and five-piece endgames.
why it works
Forward search in a sparse endgame has to guess which of an enormous branching tree of possible move sequences actually leads to the win, with no reliable heuristic to prune the search early. Backward computation avoids guessing entirely: checkmate positions are known with certainty, and the rules of chess are reversible enough that 'what legal positions could lead here in one move' is just as computable as 'what legal moves follow from here.' Because the total number of positions for a small number of pieces is finite and enumerable, exhaustive backward computation, however large, is guaranteed to terminate with a perfect answer, which no amount of forward search could promise.
the payoff
Thompson's 1977 KQKR tablebase coached the US champion, revealing wins needing far more moves than theory assumed, changed the 50-move rule.
where it breaks
It only works when the state space is small enough to enumerate exhaustively — full-board chess, with roughly 10^44 legal positions, is far too large for this method, which is why tablebases only cover endgames with a handful of pieces. It also requires the game to be reversible enough that predecessor positions can be computed from a target position, which holds for chess but not for every domain with defined terminal states.
what came after
Retrograde-computed endgame tablebases became a standard tool in computer chess, later extended by other researchers to all six- and seven-piece endgames, and the same backward-from-the-known-answer technique generalized into a foundational method used across other perfect-information games and in some search and planning problems in computer science.
references
- [1]Endgame tablebases: A short historyChessBase, 2019en.chessbase.com