25,161
edits
Changes
no edit summary
* 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 [[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++)
=See also=
* [[Chess Position]]
* [[Chess Problems, Compositions and Studies]]
* [[:Category:Problem|Chess Problem Solving Engines]]
* [[Corresponding Squares]]
* [[Dynamic Programming]]
* [[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]
* [[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'''). ''[httphttps://jespertkissuu.dkcom/Jesperjespertk/publicdocs/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]]
* [[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]]
==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-chin 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]
* [[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'''). ''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]], and [[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]]
* [[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]
* [[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 ...==
* [[Jesper Torp Kristensen]] ('''2005'''). ''[httphttps://jespertkissuu.dkcom/Jesperjespertk/publicdocs/master_thesis/ Generation and compression of endgame tables in chess with fast random access using OBDDs]''. Master thesis, Supervisor supervisor [[Mathematician#Miltersen|Peter Bro Miltersen]], [https://en.wikipedia.org/wiki/Aarhus_University Aarhus University], [http://jespertk.dk/Jesper/public/master_thesis/report/report.pdf pdf] * [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2006'''). ''[httphttps://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-users.cs.umnloyola.edu/~hrfangjglenn/papersPapers/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]]* [[James Glenn]], [http[Haw-ren Fang]], [[Clyde Kruskal]] ('''2008'''). ''[https://www-userslink.csspringer.umn.educom/%7Ehrfangchapter/papers10.1007/cantstopj978-3-540-87608-3_23 A Retrograde Approximation Algorithm for Multi-player Can’t Stop]''.pdf pdf[[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]
* [[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]
* [[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]]
==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=
==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, [[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]], [[CCC]], December 30, 2014
==2015 ...==
* [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=
==Retrograde Analysis==
* [https://en.wikipedia.org/wiki/Retrograde_analysis Retrograde analysis from Wikipedia]
* [httphttps://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]]* [httphttps://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://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]
* [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==
* [http://lestourtereaux.free.fr/euclide/ Euclide 1.11 - Home] by [[Étienne Dupuis]] » [[Euclide]]
* [httphttps://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://xenon.stanford.edu/~hwatheod/Retractor/ Retractor] a program for Retrograde Analysis chess problems by [[Chad Whipkey]] and [[Theodore Hwa]] » [[Retractor]]
: [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]
* [httphttps://darrylreeveswww.allaboutjazz.com/ Darryl Reeves] - [http://www.mytotoro.netmusicians/darryl-reevesDarryl Reeves] -the-mercury-sessions-churchill-grounds.html The Mercury Sessions] - Retrograde, July 22, 2011 - [http://www.churchillgrounds.com/ Churchill Grounds] - [https://en.wikipedia.org/wiki/Atlanta Atlanta, GA], [https://en.wikipedia.org/wiki/YouTube YouTube] Video: [http://darrylreeves.com/ Darryl Reeves], [http://www.kennybanks.com/ Kenny Banks], [https://www.linkedin.com/in/joelpowell1 Joel Powell], [https://theurbanflux.wordpress.com/tag/kenton-boom-bostick/ Kenton "Boom" Bostick]
: {{#evu:https://www.youtube.com/watch?v=6cRHUd5iCtM|alignment=left|valignment=top}}
=References=
<references />
'''[[Knowledge|Up one Level]]'''
[[Category:Music]]
