based on Lewis Stiller, Multilinear Algebra and Chess Endgames^{[2]}

The mathematical justification for the retrograde analysis algorithm was already implicit in the 1912 paper of Ernst Zermelo^{[3]}. Additional theoretical work was done by John von Neumann and Oskar Morgenstern^{[4]}.

The contemporary dynamic programming methodology, which defines the field of retrograde endgame analysis, was discovered by Richard E. Bellman in 1965 ^{[5]}. Bellman had considered game theory from a classical perspective as well ^{[6]}^{[7]}, but his work came to fruition in his 1965 paper, where he observed that the entire state-space could be stored and that dynamic programming techniques could then be used to compute whether either side could win any position.

Bellman also sketched how a combination of forward search, dynamic programming, and heuristic evaluation could be used to solve much larger state spaces than could be tackled by either technique alone. He predicted that Checkers could be solved by his techniques, and the utility of his algorithms for solving very large state spaces has been validated by Jonathan Schaeffer et al. in the domain of Checkers ^{[8]}, Ralph Gasser in the domain of Nine Men’s Morris^{[9]}, and John Romein with Henri Bal in the domain of Awari^{[10]}. The first retrograde analysis implementation was due to Thomas Ströhlein, whose important 1970 dissertation described the solution of several pawnless 4-piece endgames ^{[11]}.

Algorithm

Retrograde analysis is the basic algorithm to construct Endgame Tablebases. A bijective function is used to map chess positions to Gödel numbers which index a database of bitmaps during construction and retrieval, in its simplest form based on a multi-dimensional array index. Following description is based on Ken Thompson's paper Retrograde Analysis of Certain Endgames with depth to mate (DTM) metric ^{[12]}, and assumes White the winning side. Files of sets of chess positions, where a one-bit is associated with the Gödel number of a position, are successively manipulated during the iterative generation process:

Bi set of the latest newly found Black-to-move and lose in i moves positions

Wi set of the latest newly found White-to-move and win in i moves positions

B set of all currently known Black-to-move and lose positions, union of all Bi so far

W set of all currently known White-to-move and win positions, union of all Wi so far

Ji is temporary superset of Bi not necessarily lose positions

The algorithm starts in enumerating all Black-to-move checkmate positions B0 with the material configuration under consideration, an un-move generator is used to to build predecessor or parent positions. The un-move generation is similar to move generation, with the difference that it is illegal to start in check, but legal to un-move into check, and illegal to capture, but legal to un-capture by leaving an opponent piece behind.

for (i=0; Bi; i++)

Every parent of a Bi position is a White-to-move won position - newly-won positions Wi+1 are parents of a Bi not (yet) in W

Wi+1 becomes subset of W

Every parent of a Wi+1 position is a Black-to-move and lose position if Black wanted to mate himself, stored in Ji+1

Only if all successors (by generating and making legal moves ^{[13]}) of a Ji+1 position are member of W, the Ji+1 position becomes member of Bi+1 and B

The algorithm terminates, if no more newly predecessor positions were found, that is either Wi+1 or Bi+1 stay empty. Each one-bit in W or B correspondents to a White-to-move and won or Black-to-move and lose position. Remaining zero bits indicate either a draw, White-to-move and lose, Black-to-move and won, or illegal positions.

Ernst Zermelo (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels Proc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501–504. Translation: On an Application of Set Theory to the Theory of the Game of Chess.

Thomas Ströhlein, Ludwig Zagler (1978). Ergebnisse einer vollstandigen Analyse von Schachendspielen: König und Turm gegen König, König und Turm gegen König und Läufer. Report, Institut für Informatik, Technical University of Munich (German)

Robert Lake, Jonathan Schaeffer, Paul Lu (1993). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Technical Report, TR93-13, ps

Ren Wu, Don Beal (2001). Parallel Retrograde Analysis on Different Architectures. IEEE 10th Conference in High Performance Distributed Computing pp. 356-362, August 2001

Victor Zakharov, Vladimir Makhnychev (2010). A Retroanalysis Algorithm for Supercomputer Systems on the Example of Playing Chess. Software Systems and Tools, Vol. 11 (Russian)

Paolo Ciancarini, Gian Piero Favini (2010). Retrograde analysis of Kriegspiel endgames. IEEE Conf. on Computational Intelligence and Games, Copenhagen.

Marko Maliković, Mirko Čubrilo (2010). Solving Shortest Proof Games by Generating Trajectories using Coq Proof Management System. Proceedings of 21st Central European Conference on Information and Intelligent Systems, Varaždin, Croatia^{[20]}

^Ernst Zermelo (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels Proc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501–504. Translation: On an Application of Set Theory to the Theory of the Game of Chess

Home * Knowledge * Retrograde AnalysisRetrograde Analysis,a method in game theory to solve game positions for optimal play by backward induction from known outcomes. A sub-genre of solving certain chess problems uses retrograde analysis to determine which moves were played to reach a position, and for the proof game whether a position is legal in the sense that it could be reached by a series of legal moves from the initial position.

^{[1]}## Table of Contents

## History

based on Lewis Stiller, Multilinear Algebra and Chess Endgames^{[2]}The mathematical justification for the retrograde analysis algorithm was already implicit in the 1912 paper of Ernst Zermelo

^{[3]}. Additional theoretical work was done by John von Neumann and Oskar Morgenstern^{[4]}.The contemporary dynamic programming methodology, which defines the field of retrograde endgame analysis, was discovered by Richard E. Bellman in 1965

^{[5]}. Bellman had considered game theory from a classical perspective as well^{[6]}^{[7]}, but his work came to fruition in his 1965 paper, where he observed that the entire state-space could be stored and that dynamic programming techniques could then be used to compute whether either side could win any position.Bellman also sketched how a combination of forward search, dynamic programming, and heuristic evaluation could be used to solve much larger state spaces than could be tackled by either technique alone. He predicted that Checkers could be solved by his techniques, and the utility of his algorithms for solving very large state spaces has been validated by Jonathan Schaeffer et al. in the domain of Checkers

^{[8]}, Ralph Gasser in the domain of Nine Men’s Morris^{[9]}, and John Romein with Henri Bal in the domain of Awari^{[10]}. The first retrograde analysis implementation was due to Thomas Ströhlein, whose important 1970 dissertation described the solution of several pawnless 4-piece endgames^{[11]}.## Algorithm

Retrograde analysis is the basic algorithm to construct Endgame Tablebases. A bijective function is used to map chess positions to Gödel numbers which index a database of bitmaps during construction and retrieval, in its simplest form based on a multi-dimensional array index. Following description is based on Ken Thompson's paperRetrograde Analysis of Certain Endgameswith depth to mate (DTM) metric^{[12]}, and assumes White the winning side. Files of sets of chess positions, where a one-bit is associated with the Gödel number of a position, are successively manipulated during the iterative generation process:The algorithm starts in enumerating all Black-to-move checkmate positions B0 with the material configuration under consideration, an un-move generator is used to to build predecessor or parent positions. The un-move generation is similar to move generation, with the difference that it is illegal to start in check, but legal to un-move into check, and illegal to capture, but legal to un-capture by leaving an opponent piece behind.

for(i=0; Bi; i++)^{[13]}) of a Ji+1 position are member of W, the Ji+1 position becomes member of Bi+1 and BThe algorithm terminates, if no more newly predecessor positions were found, that is either Wi+1 or Bi+1 stay empty. Each one-bit in W or B correspondents to a White-to-move and won or Black-to-move and lose position. Remaining zero bits indicate either a draw, White-to-move and lose, Black-to-move and won, or illegal positions.

## See also

## Selected Publications

## 1910 ...

1913).Über eine Anwendung der Mengenlehre auf die Theorie des SchachspielsProc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501–504. Translation:On an Application of Set Theory to the Theory of the Game of Chess.## 1920 ...

1927).Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Scientiarum Mathematicarum (University of Szeged)## 1940 ...

1944).Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ## 1960 ...

1965).On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers.PNAS1969).Compilation of Chess Problems on a Computer. Technical translation FSTC-HT-23-124-69, US Army, NTIS AD 689470 (Problemy Kibernetiki, 19, 1967)## 1970 ...

1970).Untersuchungen über kombinatorische Spiele.Ph.D. Thesis, Technical University of Munich (German)1974).Ob Analize Ferzevogo Endshpilya pri Pomoshchi EVM.(Analysis of a queen endgame using an IBM computer) Problemy Kybernetiki, Vol. 29, pp. 211-220. English translation by Christian Posthoff, revised in ICCA Journal, Vol. 9, No. 4 (1986)1977).Computer analysis of rook end game. Avtomatika i Telemekhanika, No. 8, 113–1171977).Analyzing games by Boolean matrix iteration. Discrete Mathematics, Vol. 19, No. 21978).Ergebnisse einer vollstandigen Analyse von Schachendspielen: König und Turm gegen König, König und Turm gegen König und Läufer.Report, Institut für Informatik, Technical University of Munich (German)1978).Programming endgames with few pieces. Soviet Physics. Doklady, No. 231979).Computer Analysis of a Rook End-Game. Machine Intelligence 9 (eds. Jean Hayes Michie, Donald Michie and L.I. Mikulich), pp. 361-371. Ellis Horwood, Chichester. Reprinted in Computer Chess Compendium1979).The Chess Mysteries of Sherlock Holmes. Alfred A. Knopf, New York^{[14]}## 1980 ...

1981).The Chess Mysteries of the Arabian Knights. Alfred A. Knopf, New York^{[15]}1982).A Program for Solving Retrograde Analysis Chess Problems.Advances in Computer Chess 3^{[16]}1986).Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pdf1986).Computer Analysis of a Queen Endgame. ICCA Journal, Vol. 9, No. 41988).Massively Parallel Retrograde Endgame Analysis. BUCS Tech. Report #88-014, Boston University, Computer Science Department.1988).An Expert System for Solving Retrograde-Analysis Chess Problems.International Journal of Man-Machine Studies, Vol. 29, No. 21988).Computers and Chess-Problem Composition.ICCA Journal, Vol. 11, No. 41989).A Correction to some KRKB-Database Results. ICCA Journal, Vol. 12, No. 11989).Retrograde Analysis and two Computerizable Definitions of the Quality of Chess Games.ICCA Journal, Vol. 12, No. 2## 1990 ...

1991).New Ideas in Problem Solving and Composing Programs. Advances in Computer Chess 61991).Can a Computer Compose Chess Problems?Advances in Computer Chess 61991).Some Results from a Massively Parallel Retrograde Analysis.ICCA Journal, Vol. 14, No. 31991).Applying Retrograde Analysis to Nine Men’s Morris.Heuristic Programming in AI 21993).Solving Large Retrograde Analysis Problems Using a Network of Workstations. Technical Report, TR93-13, ps1994).Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 71995).Parallel Retrograde Analysis on a Distributed System. Supercomputing ’95, San Diego, CA.1996).Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf1996).Legality of Positions of Simple Chess Endgames. zipped pdf^{[17]}1997).The Legitimacy of Positions in Endgame Databases. ICCA Journal, Vol. 20, No. 11998).Retrograde Analysis of the KGK Endgame in Shogi: Its Implications for Ancient Heian Shogi. CG 19981999).Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame.ICCA Journal, Vol. 22, No. 2## 2000 ...

2000).Awari Retrograde Analysis. CG 20002000).Construction of Chinese Chess Endgame Databases by Retrograde Analysis. CG 20002001).Go Patterns Generated by Retrograde Analysis. 6th Computer Olympiad Workshop, pdf2001).Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3^{[18]}^{[19]}2001).Parallel Retrograde Analysis on Different Architectures. IEEE 10th Conference in High Performance Distributed Computing pp. 356-362, August 20012001).Construction of Chinese Chess Endgame Databases by Retrograde Analysis. Lecture Notes in Computer Science 2063: CG 20002002).A memory efficient retrograde algorithm and its application to solve Chinese Chess endgames.More Games of No Chance edited by Richard J. Nowakowski2002).Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf2003).Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 10, pp. 26–332004).An External-Memory Retrograde Analysis Algorithm. CG 2004## 2005 ...

2005).Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, Supervisor Peter Bro Miltersen, Aarhus University, pdf2006).A Retrograde Approximation Algorithm for One-Player Can’t Stop. CG 20062007).A Retrograde Approximation Algorithm for Two-Player Can't Stop. CGW 2007, pdf2008).Retrograde approximation algorithms for Jeopardy stochastic games. ICGA Journal, Vol. 31, No. 2, pdf2008).Chess and Mathematics. excerpt, 6 Retrograde Analysis, pdf2008).Developing Heuristics for Solving Retrograde Chess Problems. Seminar on Formal Methods and Applications, Varaždin, Croatia2009).Steinitz, Zermelo, and Elkies. pdf from ChessCafe.com, on Wilhelm Steinitz, Ernst Zermelo and Noam Elkies## 2010 ...

2010).A Retroanalysis Algorithm for Supercomputer Systems on the Example of Playing Chess. Software Systems and Tools, Vol. 11 (Russian)2010).An External-memory Retrograde Analysis Algorithm. slides as pdf2010).Retrograde analysis of Kriegspiel endgames. IEEE Conf. on Computational Intelligence and Games, Copenhagen.2010).What Were the Last Moves?International Review on Computers and Software2010).Solving Shortest Proof Games by Generating Trajectories using Coq Proof Management System. Proceedings of 21st Central European Conference on Information and Intelligent Systems, Varaždin, Croatia^{[20]}2011).Automated Reasoning about Retrograde Chess Problems using Coq. Fourth Workshop on Formal and Automated Theorem Proving and Applications, Belgrade, Serbia, slides as pdf2013).Complexity and Retrograde Analysis of the Game Dou Shou Qi. BNAIC 2013^{[21]}2014).Endgame Analysis of Dou Shou Qi. ICGA Journal, Vol. 37, No. 2, pdf## 2015 ...

2015).Impact of Rounding during Retrograde Analysis for a Game with Chance Nodes: Karl’s Race as a Test Case. ICGA Journal, Vol. 38, No. 2 » Games, EinStein würfelt nicht!^{[22]}2015).Optimal Robot Play in Certain Chess Endgame Situations. ICGA Journal, Vol. 38, No. 3## Forum Posts

## 1995 ...

## 2000 ...

^{[23]}^{[24]}^{[25]}Wu/Beal predates Koistinen by Guy Haworth, CCC, December 04, 2001

^{[26]}## 2005 ...

## 2010 ...

Re: Reverse move generation by Harm Geert Muller, December 30, 2014

## 2015 ...

## External Links

## Retrograde Analysis

^{[27]}^{[28]}^{[29]}## Programs

## Induction

## Retrograde

Apparent retrograde motion from Wikipedia

Darryl Reeves, Kenny Banks, Joel Powell, Kenton "Boom" Bostick

## Analysis

## References

1996).Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf1913).Über eine Anwendung der Mengenlehre auf die Theorie des SchachspielsProc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501–504. Translation:On an Application of Set Theory to the Theory of the Game of Chess1944).Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ1965).On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers.PNAS1954).On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems. Technical Report P-473, RAND Corporation, Santa Monica, CA1957).The Theory of Games. Technical Report P-1062, RAND Corporation, Santa Monica, CA1994).Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 71991).Applying Retrograde Analysis to Nine Men’s Morris.Heuristic Programming in AI 22003).Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 101970).Untersuchungen über kombinatorische Spiele.Ph.D. Thesis, Technical University of Munich (German)1986).Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 31981).Progress in Computer Chess.AISB Quarterly, reprinted in ICCA Newsletter, Vol. 4. No. 3, pdf2005).Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis2001).Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 32001).Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 32001).Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3## What links here?

Up one Level