Retrograde AnalysisHistory
Home * Knowledge * Retrograde Analysis
Retrograde analysis [1] Retrograde 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.
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.
See also
- Chess Position
- Chess Problems, Compositions and Studies
- Chess Problem Solving Engines
- Corresponding Squares
- Dynamic Programming
- Endgame Bitbases
- Endgame Tablebases
- Oracle
- Transposition | Retrograde Analysis
Selected Publications
1910 …
- 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.
1920 …
- Dénes Kőnig (1927). Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Scientiarum Mathematicarum ( University of Szeged)
1940 …
- John von Neumann, Oskar Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ
1960 …
- Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
- Vladimir E. Alekseev (1969). Compilation of Chess Problems on a Computer. Technical translation FSTC-HT-23-124-69, US Army, NTIS AD 689470 ( Problemy Kibernetiki, 19, 1967)
1970 …
- Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
- Edward Komissarchik, Aaron L. Futer (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)
- A. G. Alexandrov, A. M. Baraev, Ya. Yu. Gol’fand, Edward Komissarchik, Aaron L. Futer (1977). Computer analysis of rook end game. Avtomatika i Telemekhanika, No. 8, 113–117
- Thomas Ströhlein, Ludwig Zagler (1977). Analyzing games by Boolean matrix iteration. Discrete Mathematics, Vol. 19, No. 2
- 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)
- Aaron L. Futer (1978). Programming endgames with few pieces. Soviet Physics. Doklady, No. 23
- Vladimir Arlazarov, Aaron L. Futer (1979). 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 Compendium
- Raymond Smullyan (1979). The Chess Mysteries of Sherlock Holmes. Alfred A. Knopf, New York [14]
1980 …
- Raymond Smullyan (1981). The Chess Mysteries of the Arabian Knights . Alfred A. Knopf, New York [15]
- Max Bramer, B. E. P. Alden (1982). A Program for Solving Retrograde Analysis Chess Problems. Advances in Computer Chess 3 [16]
- Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pdf
- Edward Komissarchik, Aaron L. Futer (1986). Computer Analysis of a Queen Endgame. ICCA Journal, Vol. 9, No. 4
- Lewis Stiller (1988). Massively Parallel Retrograde Endgame Analysis. BUCS Tech. Report #88-014, Boston University, Computer Science Department.
- B. E. P. Alden, Max Bramer (1988). An Expert System for Solving Retrograde-Analysis Chess Problems. International Journal of Man-Machine Studies, Vol. 29, No. 2
- Michael Schlosser (1988). Computers and Chess-Problem Composition. ICCA Journal, Vol. 11, No. 4
- David Forthoffer, Lars Rasmussen, Sito Dekker (1989). A Correction to some KRKB-Database Results. ICCA Journal, Vol. 12, No. 1
- Ingo Althöfer (1989). Retrograde Analysis and two Computerizable Definitions of the Quality of Chess Games. ICCA Journal, Vol. 12, No. 2
1990 …
- László Lindner, Michael Schlosser (1991). New Ideas in Problem Solving and Composing Programs. Advances in Computer Chess 6
- Michael Schlosser (1991). Can a Computer Compose Chess Problems? Advances in Computer Chess 6
- Lewis Stiller (1991). Some Results from a Massively Parallel Retrograde Analysis. ICCA Journal, Vol. 14, No. 3
- Ralph Gasser (1991). Applying Retrograde Analysis to Nine Men’s Morris. Heuristic Programming in AI 2
- Robert Lake, Jonathan Schaeffer, Paul Lu (1993). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Technical Report, TR93-13, ps
- Robert Lake, Jonathan Schaeffer, Paul Lu (1994). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 7
- Henri Bal, Victor Allis (1995). Parallel Retrograde Analysis on a Distributed System. Supercomputing ’95, San Diego, CA.
- Lewis Stiller (1996). Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf
- Dietmar Lippold (1996). Legality of Positions of Simple Chess Endgames. zipped pdf [17]
- Dietmar Lippold (1997). The Legitimacy of Positions in Endgame Databases. ICCA Journal, Vol. 20, No. 1
- Hiroyuki Iida, Jin Yoshimura, Kazuro Morita, Jos Uiterwijk (1998). Retrograde Analysis of the KGK Endgame in Shogi: Its Implications for Ancient Heian Shogi. CG 1998
- Christoph Wirth, Jürg Nievergelt (1999). Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame. ICCA Journal, Vol. 22, No. 2
2000 …
- Roel van der Goot (2000). Awari Retrograde Analysis. CG 2000
- Haw-ren Fang, Tsan-sheng Hsu, Shun-Chin Hsu (2000). Construction of Chinese Chess Endgame Databases by Retrograde Analysis. CG 2000
- Bruno Bouzy (2001). Go Patterns Generated by Retrograde Analysis. 6th Computer Olympiad Workshop, pdf
- Lewis Stiller (2001). Retrograde Analysis: Software Architecture. ICGA Journal, Vol. 24, No. 2
- Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3 [18] [19]
- Ren Wu, Don Beal (2001). Parallel Retrograde Analysis on Different Architectures. IEEE 10th Conference in High Performance Distributed Computing pp. 356-362, August 2001
- Haw-ren Fang, Tsan-sheng Hsu, Shun-Chin Hsu (2001). Construction of Chinese Chess Endgame Databases by Retrograde Analysis. Lecture Notes in Computer Science 2063: CG 2000
- Ren Wu, Don Beal (2002). A memory efficient retrograde algorithm and its application to solve Chinese Chess endgames. More Games of No Chance edited by Richard J. Nowakowski
- Thomas Lincke (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf
- John Romein, Henri Bal (2003). Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 10, pp. 26–33
- Ping-hsun Wu, Ping-Yi Liu, Tsan-sheng Hsu (2004). An External-Memory Retrograde Analysis Algorithm. CG 2004
2005 …
- Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, supervisor Peter Bro Miltersen, Aarhus University
- James Glenn, Haw-ren Fang, Clyde Kruskal (2006). A Retrograde Approximation Algorithm for One-Player Can’t Stop. CG 2006
- James Glenn, Haw-ren Fang, Clyde Kruskal (2007). A Retrograde Approximation Algorithm for Two-Player Can’t Stop. CGW 2007, pdf
- Haw-ren Fang, James Glenn, Clyde Kruskal (2008). Retrograde approximation algorithms for Jeopardy stochastic games. ICGA Journal, Vol. 31, No. 2
- James Glenn, Haw-ren Fang, Clyde Kruskal (2008). A Retrograde Approximation Algorithm for Multi-player Can’t Stop. CG 2008
- Noam D. Elkies, Richard P. Stanley (2008). Chess and Mathematics. excerpt, 6 Retrograde Analysis, pdf
- Marko Maliković (2008). Developing Heuristics for Solving Retrograde Chess Problems. Seminar on Formal Methods and Applications, Varaždin, Croatia
- Dan Heisman (2009). Steinitz, Zermelo, and Elkies. pdf from ChessCafe.com, on Wilhelm Steinitz, Ernst Zermelo and Noam Elkies
2010 …
- Victor Zakharov, Vladimir Makhnychev (2010). A Retroanalysis Algorithm for Supercomputer Systems on the Example of Playing Chess. Software Systems and Tools, Vol. 11 (Russian)
- Ping-hsun Wu, Ping-yi Liu, Tsan-sheng Hsu (2010). An External-memory Retrograde Analysis Algorithm. slides as pdf
- Paolo Ciancarini, Gian Piero Favini (2010). Retrograde analysis of Kriegspiel endgames. IEEE Conf. on Computational Intelligence and Games, Copenhagen.
- Marko Maliković, Mirko Čubrilo (2010). What Were the Last Moves? International Review on Computers and Software
- 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]
- Marko Maliković (2011). Automated Reasoning about Retrograde Chess Problems using Coq. Fourth Workshop on Formal and Automated Theorem Proving and Applications, Belgrade, Serbia, slides as pdf
- Jan van Rijn, Jonathan K. Vis (2013). Complexity and Retrograde Analysis of the Game Dou Shou Qi. BNAIC 2013 [21]
- Jan van Rijn, Jonathan K. Vis (2014). Endgame Analysis of Dou Shou Qi. ICGA Journal, Vol. 37, No. 2, pdf
2015 …
- Michael Hartisch (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]
- Michael Hartisch, Ingo Althöfer (2015). Optimal Robot Play in Certain Chess Endgame Situations. ICGA Journal, Vol. 38, No. 3
2020 …
- Guy Haworth (2020). CEN: Thomas Ströhlein’s Endgame Tables, a 50th Anniversary. ICGA Journal, Vol. 42, Nos. 2-3
Forum Posts
1995 …
- retrograde analysis by Stefan Schroedl, rgcc, August 15, 1995
2000 …
- reverse engineering by NoKetch, rgcc, June 16, 2000
- EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001 [23]
- Re: How endgame tablebases work by Bruce Moreland, rgcc, July 19, 2001
- Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001 [24] [25]
Wu/Beal predates Koistinen by Guy Haworth, CCC, December 04, 2001
- Question about retrograde analysis algorithm for endgame databases by mathpolymath, rec.games.abstract, April 24, 2002 [26]
2005 …
- Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
- Could this program be written? by Steven Edwards, CCC, August 24, 2008
- Retrograde analysis by Geolm, CCC, November 04, 2008
2010 …
- Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
- Reverse move generation by Kostas Oreopoulos, CCC, December 30, 2014 » Un-Move Generation
Re: Reverse move generation by Harm Geert Muller, CCC, December 30, 2014
2015 …
- Position Legally Reachable? by Mark Lefler, CCC, March 21, 2017
2020 …
- Retrograde analysis - TBs move sequences to checkmate by Hedinn Steingrimsson, CCC, March 12, 2020
- On the number of chess positions by John Tromp, CCC, July 09, 2021
Re: On the number of chess positions by John Tromp, CCC, April 02, 2022 Re: On the number of chess positions by Peter Österlund, CCC, April 03, 2022 » Chess Position
- Fast reverse move generation by koedem, CCC, December 18, 2021 » Un-Move Generation
External Links
Retrograde Analysis
- Retrograde analysis from Wikipedia
- Leapfrog: Retrograde Analysis from Leapfrog tablebase generator by Harm Geert Muller
- Computing endgames with few men by Urban Koistinen [27] [28] [29]
- The Retrograde Analysis Corner
- Jewish Chess History: Prime Ministers and Retrograde Analysis
- Non-Chess Retrograde Analysis « Joe Kisenwether’s Blog
- Build Your Own Chess Endgame Monster - Level Up Coding by Don Cross, February 17, 2020
GitHub
- GitHub - tromp/ChessPositionRanking: Software suite for ranking chess positions and accurately estimating the number of legal chess positions by John Tromp
Programs
- Euclide 1.11 - Home by Étienne Dupuis » Euclide
- Freezerchess.com - Endgame Analysis beyond Databases by Eiko Bleicher » Freezer
- Natch - Checking proof games by Pascal Wassong » Natch
- Retractor a program for Retrograde Analysis chess problems by Chad Whipkey and Theodore Hwa » Retractor
Induction
Retrograde
Apparent retrograde motion from Wikipedia
- Retrograde (music) from Wikipedia
- Darryl Reeves - The Mercury Sessions - Retrograde, July 22, 2011 - Churchill Grounds - Atlanta, GA, YouTube Video
Darryl Reeves, Kenny Banks, Joel Powell, Kenton “Boom” Bostick
Analysis
References
- ↑ Ретроградный анализ. / Retrograde analysis, Flickr: Fotostream by Segaboy
- ↑ Lewis Stiller (1996). Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf
- ↑ 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
- ↑ John von Neumann and Oskar Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ
- ↑ Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
- ↑ Richard E. Bellman (1954). On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems. Technical Report P-473, RAND Corporation, Santa Monica, CA
- ↑ Richard E. Bellman (1957). The Theory of Games. Technical Report P-1062, RAND Corporation, Santa Monica, CA
- ↑ Robert Lake, Jonathan Schaeffer, Paul Lu (1994). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 7
- ↑ Ralph Gasser (1991). Applying Retrograde Analysis to Nine Men’s Morris. Heuristic Programming in AI 2
- ↑ John Romein, Henri Bal (2003). Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 10
- ↑ Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
- ↑ Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3
- ↑ dubbed “grandfather” method, Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
- ↑ Smullyan Problem in Sherlock Holmes book by Christopher Heckman, rgcc, January 18, 2013
- ↑ Retrospektive (Retroanalyse) from German Wikipedia, Raymond Smullyan, Manchester Guardian, 1957
- ↑ Jaap van den Herik (1981). Progress in Computer Chess. AISB Quarterly, reprinted in ICCA Newsletter, Vol. 4. No. 3, pdf
- ↑ referred in Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, supervisor Peter Bro Miltersen, Aarhus University
- ↑ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
- ↑ Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
- ↑ Coq from Wikipedia
- ↑ Jungle (board game) from Wikipedia
- ↑ Karl’s Race A Game on Karl Scherer’s Alternating Tiling by Ingo Althöfer, 2006
- ↑ Computing endgames with few men by Urban Koistinen
- ↑ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
- ↑ Computing endgames with few men by Urban Koistinen
- ↑ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
- ↑ EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001
- ↑ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001
- ↑ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3