Difference between revisions of "Retrograde Analysis"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(9 intermediate revisions by the same user not shown) | |||
Line 22: | Line 22: | ||
* J<span style="vertical-align: sub;font-size: 80%;">i</span> is temporary superset of B<span style="vertical-align: sub;font-size: 80%;">i</span> not necessarily lose positions | * J<span style="vertical-align: sub;font-size: 80%;">i</span> is temporary superset of B<span style="vertical-align: sub;font-size: 80%;">i</span> not necessarily lose positions | ||
− | The algorithm starts in enumerating all Black-to-move [[Checkmate|checkmate]] positions B<span style="vertical-align: sub;font-size: 80%;">0</span> 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|move generation]], with the difference that it is illegal to start in [[Check|check]], but legal to un-move into check, and illegal to capture, but legal to un-capture by leaving an opponent piece behind. | + | The algorithm starts in enumerating all Black-to-move [[Checkmate|checkmate]] positions B<span style="vertical-align: sub;font-size: 80%;">0</span> with the material configuration under consideration, an [[Move Generation#Reverse|un-move generator]] is used to to build predecessor or parent positions. The un-move generation is similar to [[Move Generation|move generation]], with the difference that it is illegal to start in [[Check|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; B<span style="vertical-align: sub; font-size: 80%;">i</span>; i++) | '''for''' (i=0; B<span style="vertical-align: sub; font-size: 80%;">i</span>; i++) | ||
Line 33: | Line 33: | ||
=See also= | =See also= | ||
+ | * [[Chess Position]] | ||
* [[Chess Problems, Compositions and Studies]] | * [[Chess Problems, Compositions and Studies]] | ||
* [[:Category:Problem|Chess Problem Solving Engines]] | * [[:Category:Problem|Chess Problem Solving Engines]] | ||
Line 80: | Line 81: | ||
* [[Henri Bal]], [[Victor Allis]] ('''1995'''). ''Parallel Retrograde Analysis on a Distributed System''. Supercomputing ’95, San Diego, CA. | * [[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''. [http://library.msri.org/books/Book29/index.html Games of No Chance] edited by [[Richard J. Nowakowski]], [http://www.msri.org/publications/books/Book29/files/stiller.pdf pdf] | * [[Lewis Stiller]] ('''1996'''). ''Multilinear Algebra and Chess Endgames''. [http://library.msri.org/books/Book29/index.html Games of No Chance] edited by [[Richard J. Nowakowski]], [http://www.msri.org/publications/books/Book29/files/stiller.pdf pdf] | ||
− | * [[Dietmar Lippold]] ('''1996'''). ''Legality of Positions of Simple Chess Endgames''. [http://digilander.libero.it/gargamellachess/papers/legality%20of%20positions.zip zipped pdf] <ref>referred in [[Jesper Torp Kristensen]] ('''2005'''). ''[ | + | * [[Dietmar Lippold]] ('''1996'''). ''Legality of Positions of Simple Chess Endgames''. [http://digilander.libero.it/gargamellachess/papers/legality%20of%20positions.zip zipped pdf] <ref>referred in [[Jesper Torp Kristensen]] ('''2005'''). ''[https://issuu.com/jespertk/docs/master_thesis Generation and compression of endgame tables in chess with fast random access using OBDDs]''. Master thesis, supervisor [[Mathematician#Miltersen|Peter Bro Miltersen]], [https://en.wikipedia.org/wiki/Aarhus_University Aarhus University]</ref> |
* [[Dietmar Lippold]] ('''1997'''). ''The Legitimacy of Positions in Endgame Databases''. [[ICGA Journal#20_1|ICCA Journal, Vol. 20, No. 1]] | * [[Dietmar Lippold]] ('''1997'''). ''The Legitimacy of Positions in Endgame Databases''. [[ICGA Journal#20_1|ICCA Journal, Vol. 20, No. 1]] | ||
* [[Hiroyuki Iida]], [[Jin Yoshimura]], [[Kazuro Morita]], [[Jos Uiterwijk]] ('''1998'''). ''[http://www.springerlink.com/content/pg7at646416va0re/ Retrograde Analysis of the KGK Endgame in Shogi: Its Implications for Ancient Heian Shogi]''. [[CG 1998]] | * [[Hiroyuki Iida]], [[Jin Yoshimura]], [[Kazuro Morita]], [[Jos Uiterwijk]] ('''1998'''). ''[http://www.springerlink.com/content/pg7at646416va0re/ Retrograde Analysis of the KGK Endgame in Shogi: Its Implications for Ancient Heian Shogi]''. [[CG 1998]] | ||
Line 86: | Line 87: | ||
==2000 ...== | ==2000 ...== | ||
* [[Roel van der Goot]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_6 Awari Retrograde Analysis]''. [[CG 2000]] | * [[Roel van der Goot]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_6 Awari Retrograde Analysis]''. [[CG 2000]] | ||
− | * [[Haw-ren Fang]], [[Tsan-sheng Hsu]], [[Shun- | + | * [[Haw-ren Fang]], [[Tsan-sheng Hsu]], [[Shun-Chin Hsu]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_7 Construction of Chinese Chess Endgame Databases by Retrograde Analysis]''. [[CG 2000]] |
* [[Bruno Bouzy]] ('''2001'''). ''Go Patterns Generated by Retrograde Analysis''. [[6th Computer Olympiad#Workshop|6th Computer Olympiad Workshop]], [http://www.mi.parisdescartes.fr/~bouzy/publications/RAGO.pdf pdf] | * [[Bruno Bouzy]] ('''2001'''). ''Go Patterns Generated by Retrograde Analysis''. [[6th Computer Olympiad#Workshop|6th Computer Olympiad Workshop]], [http://www.mi.parisdescartes.fr/~bouzy/publications/RAGO.pdf pdf] | ||
* [[Lewis Stiller]] ('''2001'''). ''Retrograde Analysis: Software Architecture''. [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]] | * [[Lewis Stiller]] ('''2001'''). ''Retrograde Analysis: Software Architecture''. [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]] | ||
* [[Ren Wu]], [[Don Beal]] ('''2001'''). ''[http://ilk.uvt.nl/icga/journal/contents/content24-3.htm#FAST Fast, Memory-efficient Retrograde Algorithms]''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]] <ref>[https://www.stmintz.com/ccc/index.php?id=200335 Generating egtbs ICGAJ] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], December 04, 2001, with reference to [http://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]]</ref> <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6302&p=29956 Wu / Beal retrograde analisys algorithm] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[Computer Chess Forums|Winboard Forum]], March 10, 2007 </ref> | * [[Ren Wu]], [[Don Beal]] ('''2001'''). ''[http://ilk.uvt.nl/icga/journal/contents/content24-3.htm#FAST Fast, Memory-efficient Retrograde Algorithms]''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]] <ref>[https://www.stmintz.com/ccc/index.php?id=200335 Generating egtbs ICGAJ] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], December 04, 2001, with reference to [http://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]]</ref> <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6302&p=29956 Wu / Beal retrograde analisys algorithm] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[Computer Chess Forums|Winboard Forum]], March 10, 2007 </ref> | ||
* [[Ren Wu]], [[Don Beal]] ('''2001'''). ''Parallel Retrograde Analysis on Different Architectures''. IEEE 10th Conference in High Performance Distributed Computing pp. 356-362, August 2001 | * [[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]], | + | * [[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.'' [http://library.msri.org/books/Book42/ More Games of No Chance] edited by [[Richard J. Nowakowski]] | * [[Ren Wu]], [[Don Beal]] ('''2002'''). ''A memory efficient retrograde algorithm and its application to solve Chinese Chess endgames.'' [http://library.msri.org/books/Book42/ 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]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf] | * [[Thomas Lincke]] ('''2002'''). ''Exploring the Computational Limits of Large Exhaustive Search Problems''. Ph.D thesis, [[ETH Zurich]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf] | ||
Line 97: | Line 98: | ||
* [[Ping-hsun Wu]], [[Ping-Yi Liu]], [[Tsan-sheng Hsu]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_10 An External-Memory Retrograde Analysis Algorithm]''. [[CG 2004]] | * [[Ping-hsun Wu]], [[Ping-Yi Liu]], [[Tsan-sheng Hsu]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_10 An External-Memory Retrograde Analysis Algorithm]''. [[CG 2004]] | ||
==2005 ...== | ==2005 ...== | ||
− | * [[Jesper Torp Kristensen]] ('''2005'''). ''[ | + | * [[Jesper Torp Kristensen]] ('''2005'''). ''[https://issuu.com/jespertk/docs/master_thesis Generation and compression of endgame tables in chess with fast random access using OBDDs]''. Master thesis, supervisor [[Mathematician#Miltersen|Peter Bro Miltersen]], [https://en.wikipedia.org/wiki/Aarhus_University Aarhus University] |
− | * [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2006'''). ''[ | + | * [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2006'''). ''[https://link.springer.com/chapter/10.1007/978-3-540-75538-8_13 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]], [http://www | + | * [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2007'''). ''A Retrograde Approximation Algorithm for Two-Player Can't Stop''. [[CGW 2007]], [http://www.cs.loyola.edu/~jglenn/Papers/cantstop2.pdf pdf] |
− | * [[Haw-ren Fang]], [[James Glenn]], [[Clyde Kruskal]] ('''2008'''). ''Retrograde approximation algorithms for Jeopardy stochastic games''. [[ICGA Journal#31_2|ICGA Journal, Vol. 31, No. 2]], [ | + | * [[Haw-ren Fang]], [[James Glenn]], [[Clyde Kruskal]] ('''2008'''). ''Retrograde approximation algorithms for Jeopardy stochastic games''. [[ICGA Journal#31_2|ICGA Journal, Vol. 31, No. 2]] |
+ | * [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2008'''). ''[https://link.springer.com/chapter/10.1007/978-3-540-87608-3_23 A Retrograde Approximation Algorithm for Multi-player Can’t Stop]''. [[CG 2008]] | ||
* [[Noam Elkies|Noam D. Elkies]], [[Mathematician#RPStanley|Richard P. Stanley]] ('''2008'''). ''Chess and Mathematics''. excerpt, 6 Retrograde Analysis, [http://www-math.mit.edu/%7Erstan/chess/spg.pdf pdf] | * [[Noam Elkies|Noam D. Elkies]], [[Mathematician#RPStanley|Richard P. Stanley]] ('''2008'''). ''Chess and Mathematics''. excerpt, 6 Retrograde Analysis, [http://www-math.mit.edu/%7Erstan/chess/spg.pdf pdf] | ||
* [[Marko Maliković]] ('''2008'''). ''Developing Heuristics for Solving Retrograde Chess Problems''. [http://seminar.foi.hr/ Seminar on Formal Methods and Applications], [https://en.wikipedia.org/wiki/Vara%C5%BEdin Varaždin], [https://en.wikipedia.org/wiki/Croatia Croatia] | * [[Marko Maliković]] ('''2008'''). ''Developing Heuristics for Solving Retrograde Chess Problems''. [http://seminar.foi.hr/ Seminar on Formal Methods and Applications], [https://en.wikipedia.org/wiki/Vara%C5%BEdin Varaždin], [https://en.wikipedia.org/wiki/Croatia Croatia] | ||
Line 116: | Line 118: | ||
* [[Michael Hartisch]] ('''2015'''). ''Impact of Rounding during Retrograde Analysis for a Game with Chance Nodes: Karl’s Race as a Test Case''. [[ICGA Journal#38_2|ICGA Journal, Vol. 38, No. 2]] » [[Games]], [[EinStein würfelt nicht!]] <ref>[http://www.althofer.de/karls-race.html Karl's Race] A Game on [[Karl Scherer|Karl Scherer's]] Alternating Tiling by [[Ingo Althöfer]], 2006</ref> | * [[Michael Hartisch]] ('''2015'''). ''Impact of Rounding during Retrograde Analysis for a Game with Chance Nodes: Karl’s Race as a Test Case''. [[ICGA Journal#38_2|ICGA Journal, Vol. 38, No. 2]] » [[Games]], [[EinStein würfelt nicht!]] <ref>[http://www.althofer.de/karls-race.html Karl's Race] A Game on [[Karl Scherer|Karl Scherer's]] Alternating Tiling by [[Ingo Althöfer]], 2006</ref> | ||
* [[Michael Hartisch]], [[Ingo Althöfer]] ('''2015'''). ''Optimal Robot Play in Certain Chess Endgame Situations''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]] | * [[Michael Hartisch]], [[Ingo Althöfer]] ('''2015'''). ''Optimal Robot Play in Certain Chess Endgame Situations''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]] | ||
+ | ==2020 ...== | ||
+ | * [[Guy Haworth]] ('''2020'''). ''CEN: Thomas Ströhlein’s Endgame Tables, a 50th Anniversary''. [[ICGA Journal#42_23|ICGA Journal, Vol. 42, Nos. 2-3]] | ||
=Forum Posts= | =Forum Posts= | ||
Line 133: | Line 137: | ||
==2010 ...== | ==2010 ...== | ||
* [http://www.open-chess.org/viewtopic.php?f=5&t=779 Retrograde tablebase methods] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], November 26, 2010 | * [http://www.open-chess.org/viewtopic.php?f=5&t=779 Retrograde tablebase methods] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], November 26, 2010 | ||
− | * [http://www.talkchess.com/forum/viewtopic.php?t=54796 Reverse move generation] by Kostas Oreopoulos, December 30, 2014 » [[Move Generation]] | + | * [http://www.talkchess.com/forum/viewtopic.php?t=54796 Reverse move generation] by Kostas Oreopoulos, [[CCC]], December 30, 2014 » [[Move Generation#Reverse|Un-Move Generation]] |
− | : [http://www.talkchess.com/forum/viewtopic.php?t=54796&start=6 Re: Reverse move generation] by [[Harm Geert Muller]], December 30, 2014 | + | : [http://www.talkchess.com/forum/viewtopic.php?t=54796&start=6 Re: Reverse move generation] by [[Harm Geert Muller]], [[CCC]], December 30, 2014 |
==2015 ...== | ==2015 ...== | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=63515 Position Legally Reachable?] by [[Mark Lefler]], [[CCC]], March 21, 2017 | * [http://www.talkchess.com/forum/viewtopic.php?t=63515 Position Legally Reachable?] by [[Mark Lefler]], [[CCC]], March 21, 2017 | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73332 Retrograde analysis - TBs move sequences to checkmate] by Hedinn Steingrimsson, [[CCC]], March 12, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77685 On the number of chess positions] by [[John Tromp]], [[CCC]], July 09, 2021 | ||
+ | : [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=77685&start=34 Re: On the number of chess positions] by [[John Tromp]], [[CCC]], April 02, 2022 | ||
+ | : [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=77685&start=42 Re: On the number of chess positions] by [[Peter Österlund]], [[CCC]], April 03, 2022 » [[Chess Position]] | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78913 Fast reverse move generation] by koedem, [[CCC]], December 18, 2021 » [[Move Generation#Reverse|Un-Move Generation]] | ||
=External Links= | =External Links= | ||
==Retrograde Analysis== | ==Retrograde Analysis== | ||
* [https://en.wikipedia.org/wiki/Retrograde_analysis Retrograde analysis from Wikipedia] | * [https://en.wikipedia.org/wiki/Retrograde_analysis Retrograde analysis from Wikipedia] | ||
− | * [ | + | * [https://home.hccnet.nl/h.g.muller/EGT7/retro.html Leapfrog: Retrograde Analysis] from [http://home.hccnet.nl/h.g.muller/EGT7/7-men.html Leapfrog tablebase generator] by [[Harm Geert Muller]] |
− | * [ | + | * [https://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]] <ref> [https://www.stmintz.com/ccc/index.php?id=162252 EGTB: Better algorithm] by [[Urban Koistinen]], [[CCC]], April 07, 2001</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=200335 Generating egtbs ICGAJ] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], December 04, 2001</ref> <ref>[[Ren Wu]], [[Don Beal]] ('''2001'''). ''Fast, Memory-efficient Retrograde Algorithms''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]]</ref> |
* [http://www.janko.at/Retros/index.htm The Retrograde Analysis Corner] | * [http://www.janko.at/Retros/index.htm The Retrograde Analysis Corner] | ||
* [http://jewishchesshistory.blogspot.de/2008/01/prime-ministers-and-retrograde-analysis.html Jewish Chess History: Prime Ministers and Retrograde Analysis] | * [http://jewishchesshistory.blogspot.de/2008/01/prime-ministers-and-retrograde-analysis.html Jewish Chess History: Prime Ministers and Retrograde Analysis] | ||
* [http://joekisenwether.wordpress.com/non-chess-retrograde-analysis/ Non-Chess Retrograde Analysis] « [http://joekisenwether.wordpress.com/ Joe Kisenwether's Blog] | * [http://joekisenwether.wordpress.com/non-chess-retrograde-analysis/ Non-Chess Retrograde Analysis] « [http://joekisenwether.wordpress.com/ Joe Kisenwether's Blog] | ||
+ | * [https://levelup.gitconnected.com/build-your-own-chess-endgame-monster-a3fb23bb3ec1 Build Your Own Chess Endgame Monster - Level Up Coding] by [[Don Cross]], February 17, 2020 | ||
+ | ==GitHub== | ||
+ | * [https://github.com/tromp/ChessPositionRanking GitHub - tromp/ChessPositionRanking: Software suite for ranking chess positions and accurately estimating the number of legal chess positions] by [[John Tromp]] | ||
==Programs== | ==Programs== | ||
* [http://lestourtereaux.free.fr/euclide/ Euclide 1.11 - Home] by [[Étienne Dupuis]] » [[Euclide]] | * [http://lestourtereaux.free.fr/euclide/ Euclide 1.11 - Home] by [[Étienne Dupuis]] » [[Euclide]] | ||
− | * [ | + | * [https://www.freezerchess.com/ Freezerchess.com - Endgame Analysis beyond Databases] by [[Eiko Bleicher]] » [[Freezer]] |
* [http://natch.free.fr/Natch.html Natch - Checking proof games] by [[Pascal Wassong]] » [[Natch]] | * [http://natch.free.fr/Natch.html Natch - Checking proof games] by [[Pascal Wassong]] » [[Natch]] | ||
* [http://xenon.stanford.edu/~hwatheod/Retractor/ Retractor] a program for Retrograde Analysis chess problems by [[Chad Whipkey]] and [[Theodore Hwa]] » [[Retractor]] | * [http://xenon.stanford.edu/~hwatheod/Retractor/ Retractor] a program for Retrograde Analysis chess problems by [[Chad Whipkey]] and [[Theodore Hwa]] » [[Retractor]] | ||
Line 160: | Line 173: | ||
: [https://en.wikipedia.org/wiki/Apparent_retrograde_motion Apparent retrograde motion from Wikipedia] | : [https://en.wikipedia.org/wiki/Apparent_retrograde_motion Apparent retrograde motion from Wikipedia] | ||
* [https://en.wikipedia.org/wiki/Retrograde_%28music%29 Retrograde (music) from Wikipedia] | * [https://en.wikipedia.org/wiki/Retrograde_%28music%29 Retrograde (music) from Wikipedia] | ||
− | * [ | + | * [https://www.allaboutjazz.com/musicians/darryl-reeves Darryl Reeves] - The Mercury Sessions - Retrograde, July 22, 2011 - Churchill Grounds - [https://en.wikipedia.org/wiki/Atlanta Atlanta, GA], [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
− | : | + | : Darryl Reeves, Kenny Banks, Joel Powell, Kenton "Boom" Bostick |
: {{#evu:https://www.youtube.com/watch?v=6cRHUd5iCtM|alignment=left|valignment=top}} | : {{#evu:https://www.youtube.com/watch?v=6cRHUd5iCtM|alignment=left|valignment=top}} | ||
Line 170: | Line 183: | ||
=References= | =References= | ||
<references /> | <references /> | ||
− | |||
'''[[Knowledge|Up one Level]]''' | '''[[Knowledge|Up one Level]]''' | ||
[[Category:Music]] | [[Category:Music]] |
Latest revision as of 11:56, 4 April 2022
Home * Knowledge * Retrograde Analysis
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.
Contents
History
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 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
- Inductive reasoning from Wikipedia
- Backward induction from Wikipedia
- Backward chaining from Wikipedia
Retrograde
- 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