Bell Labs' Ken Thompson solved chess endgames by computing backward from checkmate

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.

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.

Instead of searching forward, they computed backward from every checkmate, assigning each position an exact number of moves to force a win or draw.

Checkmate positions are known with certainty, providing fixed starting points.

Chess rules are reversible, so computing predecessors is as easy as computing successors.

The finite state space for few pieces allows exhaustive enumeration, guaranteeing a perfect solution.

Backward computation avoids the need for heuristics to prune forward search.

When forward search is intractable, enumerate known terminal states and propagate values backward through reversible rules.

Thompson's 1977 KQKR tablebase coached the US champion, revealing wins needing far more moves than theory assumed, changed the 50-move rule. 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.