◄ WORLD V · SONNY 5DART 581 · a helldive across the board

THE RETROGRADE ANALYSIS solve the endgame backwards

To build a perfect endgame database, do not search forward — work backward from the end. Mark every terminal position won or lost, then repeatedly propagate: a position is a loss if every move leads to a won position for the opponent, a win if some move reaches a lost one. Iterate to a fixed point and every position carries its exact result and distance-to-mate. It is how chess tablebases were built — and how checkers was solved.

THE TECHNIQUE label terminals, propagate to a fixed point

The demo builds the win/loss labels of a subtraction game by backward induction: live demo







  
HISTORY & CREDIT Bellman 1965 · Ströhlein 1970

  
“Endgame tablebases store best moves from analysis.” — they are computed backward from mate to the fixed point; no forward search or heuristics. cited

  
terminals · label positions with no moves (the loser to move).
propagate back · loss if all moves lead to wins; win if any move leads to a loss — iterate to a fixed point.
1965/70 · Bellman & Ströhlein; Thompson’s chess databases; checkers solved in 2007.

  
The future of a game, computed from its end. algorithm






  
RECOMMEND FOR I-13 the labels, on the compiler

  
On i-13, backward induction on subtraction {1,2} puts losses at multiples of 3 and wins elsewhere:

  
$ i13 run gm_retrograde-analysis.i13
RUN OK · 1525 step(s) · call depth 7
win/lose 0..6 = 0 1 1 0 1 1 0
losses_at_multiples_of_3 = 1  wins_otherwise = 1

  
Recommend as a NULL — a fixed point (B43) + pinned labels (B39). The win/loss labeling is the least fixed point of the game graph; every correct backward pass computes the same table. Fixed-points auto-NULL. NULL — solve the endgame backwards.