25,161
edits
Changes
Created page with "'''Home * Knowledge * Retrograde Analysis''' FILE:RetrogradeAnalysissmurpiknik.jpg|border|right|thumb|link=http://www.flickr.com/photos/smurpiknik/5149247..."
'''[[Main Page|Home]] * [[Knowledge]] * Retrograde Analysis'''
[[FILE:RetrogradeAnalysissmurpiknik.jpg|border|right|thumb|link=http://www.flickr.com/photos/smurpiknik/5149247538/in/photostream| Retrograde analysis <ref>[http://www.flickr.com/photos/smurpiknik/5149247538/in/photostream Ретроградный анализ. / Retrograde analysis], [http://www.flickr.com/photos/smurpiknik/with/5149247538/#photo_5149247538 Flickr: Fotostream by Segaboy]</ref> ]]
'''Retrograde Analysis''',<br/>
a method in [https://en.wikipedia.org/wiki/Game_theory game theory] to solve [[Chess Position|game positions]] for [https://en.wikipedia.org/wiki/Best_response optimal play] by [https://en.wikipedia.org/wiki/Backward_induction backward induction] from known outcomes. A sub-genre of solving certain [https://en.wikipedia.org/wiki/Chess_problem chess problems] uses retrograde analysis to determine which [[Moves|moves]] were played to reach a position, and for the [https://en.wikipedia.org/wiki/Proof_game proof game] whether a position is legal in the sense that it could be reached by a series of [[Legal Move|legal moves]] from the [[Initial Position|initial position]].
<span id="History"></span>
=History=
History based on [[Lewis Stiller]], ''Multilinear Algebra and Chess Endgames'' <ref>[[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]</ref>
The mathematical justification for the retrograde analysis algorithm was already implicit in the 1912 paper of [[Ernst Zermelo]] <ref>[[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''</ref>. Additional theoretical work was done by [[John von Neumann]] and [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] <ref>[[John von Neumann]] and [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] ('''1944'''). ''Theory of Games and Economic Behavior''. Princeton University Press, Princeton, NJ</ref>.
The contemporary [[Dynamic Programming|dynamic programming]] methodology, which defines the field of retrograde endgame analysis, was discovered by [[Richard E. Bellman]] in 1965 <ref>[[Richard E. Bellman]] ('''1965'''). ''[http://www.rand.org/pubs/papers/P3013/ On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers].'' [https://en.wikipedia.org/wiki/Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America PNAS]</ref>. Bellman had considered game theory from a classical perspective as well <ref>[[Richard E. Bellman]] ('''1954'''). ''On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems''. Technical Report P-473, [https://en.wikipedia.org/wiki/RAND_Corporation RAND Corporation], [https://en.wikipedia.org/wiki/Santa_Monica,_California Santa Monica, CA]</ref> <ref>[[Richard E. Bellman]] ('''1957'''). ''The Theory of Games''. Technical Report P-1062, [https://en.wikipedia.org/wiki/RAND_Corporation RAND Corporation], [https://en.wikipedia.org/wiki/Santa_Monica,_California Santa Monica, CA]</ref>, but his work came to fruition in his 1965 paper, where he observed that the entire [https://en.wikipedia.org/wiki/State_space_%28dynamical_system%29 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 [[Search|forward search]], dynamic programming, and [[Evaluation|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 <ref>[[Rob Lake|Robert Lake]], [[Jonathan Schaeffer]], [[Paul Lu]] ('''1994'''). ''Solving Large Retrograde Analysis Problems Using a Network of Workstations''. [[Advances in Computer Chess 7]]</ref>, [[Ralph Gasser]] in the domain of [[Nine Men’s Morris]] <ref>[[Ralph Gasser]] ('''1991'''). ''Applying Retrograde Analysis to Nine Men’s Morris.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]</ref>, and [[John Romein]] with [[Henri Bal]] in the domain of [[Awari]] <ref>[[John Romein]], [[Henri Bal]] ('''2003'''). ''Solving the Game of Awari using Parallel Retrograde Analysis''. IEEE Computer, Vol. 36, No. 10</ref>. The first retrograde analysis implementation was due to [[Thomas Ströhlein]], whose important 1970 dissertation described the solution of several pawnless 4-piece endgames <ref>[[Thomas Ströhlein]] ('''1970'''). ''Untersuchungen über kombinatorische Spiele.'' Ph.D. Thesis, [[Technical University of Munich]] (German)</ref>.
<span id="Algorithm"></span>
=Algorithm=
Retrograde analysis is the basic [[Algorithms|algorithm]] to construct [[Endgame Tablebases]]. A [https://en.wikipedia.org/wiki/Bijection bijective function] is used to map [[Chess Position|chess positions]] to [https://en.wikipedia.org/wiki/G%C3%B6del_numbering Gödel numbers] which index a database of bitmaps during construction and retrieval, in its simplest form based on a multi-dimensional [[Array|array]] index. Following description is based on [[Ken Thompson|Ken Thompson's]] paper ''Retrograde Analysis of Certain Endgames'' with [[Endgame Tablebases#DTM|depth to mate (DTM)]] metric <ref>[[Ken Thompson]] ('''1986'''). ''Retrograde Analysis of Certain Endgames''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]</ref>, 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 [[Iteration|iterative]] generation process:
* B<span style="vertical-align: sub;font-size: 80%;">i</span> set of the latest newly found Black-to-move and lose in i moves positions
* W<span style="vertical-align: sub;font-size: 80%;">i</span> 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 B<span style="vertical-align: sub;font-size: 80%;">i</span> so far
* W set of all currently known White-to-move and win positions, union of all W<span style="vertical-align: sub;font-size: 80%;">i</span> so far
* 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.
'''for''' (i=0; B<span style="vertical-align: sub; font-size: 80%;">i</span>; i++)
# Every parent of a B<span style="vertical-align: sub; font-size: 80%;">i</span> position is a White-to-move won position - newly-won positions W<span style="vertical-align: sub; font-size: 80%;">i+1</span> are parents of a B<span style="vertical-align: sub; font-size: 80%;">i</span> not (yet) in W
# W<span style="vertical-align: sub;font-size: 80%;">i+1</span> becomes subset of W
# Every parent of a W<span style="vertical-align: sub;font-size: 80%;">i+1</span> position is a Black-to-move and lose position if Black wanted to mate himself, stored in J<span style="vertical-align: sub;font-size: 80%;">i+1</span>
# Only if all successors (by generating and making legal moves <ref>dubbed "grandfather" method, [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</ref>) of a J<span style="vertical-align: sub; font-size: 80%;">i+1</span> position are member of W, the J<span style="vertical-align: sub; font-size: 80%;">i+1</span> position becomes member of B<span style="vertical-align: sub;font-size: 80%;">i+1</span> and B
The algorithm terminates, if no more newly predecessor positions were found, that is either W<span style="vertical-align: sub;font-size: 80%;">i+1</span> or B<span style="vertical-align: sub;font-size: 80%;">i+1</span> 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|draw]], White-to-move and lose, Black-to-move and won, or illegal positions.
=See also=
* [[Chess Problems, Compositions and Studies]]
* [[Chess Problem Solving Engines]]
* [[Corresponding Squares]]
* [[Dynamic Programming]]
* [[Endgame Bitbases]]
* [[Endgame Tablebases]]
* [[Oracle]]
* [[Transposition#RetrogradeAnalysis|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 ...==
* [[Mathematician#DenesKoenig|Dénes Kőnig]] ('''1927'''). ''[http://acta.fyx.hu/acta/showCustomerArticle.action?id=5131&dataObjectType=article&returnAction=showCustomerVolume&sessionDataSetId=2b29ea26fa2c9ba Über eine Schlussweise aus dem Endlichen ins Unendliche]''. [http://acta.fyx.hu/acta/home.action?noDataSet=true Acta Scientiarum Mathematicarum] ([https://en.wikipedia.org/wiki/University_of_Szeged University of Szeged])
==1940 ...==
* [[John von Neumann]], [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] ('''1944'''). ''Theory of Games and Economic Behavior''. Princeton University Press, Princeton, NJ
==1960 ...==
* [[Richard E. Bellman]] ('''1965'''). ''[http://www.rand.org/pubs/papers/P3013/ On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers].'' [https://en.wikipedia.org/wiki/Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America PNAS]
* [[Vladimir E. Alekseev]] ('''1969'''). ''[http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=AD0689470 Compilation of Chess Problems on a Computer]''. Technical translation FSTC-HT-23-124-69, US Army, NTIS AD 689470 ([http://www.worldcat.org/title/problemy-kibernetiki/oclc/1762911 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 [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]] ('''1986''')
* [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=55935 A. G. Alexandrov], [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=96113 A. M. Baraev], [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=96114 Ya. Yu. Gol'fand], [[Edward Komissarchik]], [[Aaron L. Futer]] ('''1977'''). ''[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=7425&option_lang=eng Computer analysis of rook end game]''. [https://en.wikipedia.org/wiki/Automation_and_Remote_Control Avtomatika i Telemekhanika], No. 8, 113–117
* [[Thomas Ströhlein]], [[Ludwig Zagler]] ('''1977'''). ''[http://www.sciencedirect.com/science/article/pii/0012365X77900334 Analyzing games by Boolean matrix iteration]''. [https://en.wikipedia.org/wiki/Discrete_Mathematics_%28journal%29 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'''). ''[https://zbmath.org/?q=an:03637634 Programming endgames with few pieces]''. [https://en.wikipedia.org/wiki/Doklady_Physics Soviet Physics. Doklady], No. 23
* [[Vladimir Arlazarov]], [[Aaron L. Futer]] ('''1979'''). ''Computer Analysis of a Rook End-Game''. [http://www.doc.ic.ac.uk/~shm/MI/mi9.html 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'''). ''[http://www.amazon.com/Chess-Mysteries-Sherlock-Holmes/dp/0394737571 The Chess Mysteries of Sherlock Holmes]''. [https://en.wikipedia.org/wiki/Alfred_A._Knopf Alfred A. Knopf], New York <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/MyFmpXxqccg/Z6WgNuoF-hcJ Smullyan Problem in Sherlock Holmes book] by Christopher Heckman, [[Computer Chess Forums|rgcc]], January 18, 2013</ref>
==1980 ...==
* [[Raymond Smullyan]] ('''1981'''). ''[http://www.chesslund.com/detail.asp?id=2206&n=Smullyan-The-Chess-Mysteries-of-the-Arabian-Knights The Chess Mysteries of the Arabian Knights ]''. [https://en.wikipedia.org/wiki/Alfred_A._Knopf Alfred A. Knopf], New York <ref>[http://de.wikipedia.org/wiki/Schachkomposition#Retrospektive_.28Retroanalyse.29 Retrospektive (Retroanalyse)] from German Wikipedia, [[Mathematician#Smullyan|Raymond Smullyan]], [https://en.wikipedia.org/wiki/The_Guardian Manchester Guardian], 1957</ref>
* [[Max Bramer]], [http://www.informatik.uni-trier.de/~ley/pers/hy/a/Alden:B=_E=_P=.html B. E. P. Alden] ('''1982'''). ''A Program for Solving Retrograde Analysis Chess Problems.'' [[Advances in Computer Chess 3]] <ref>[[Jaap van den Herik]] ('''1981'''). ''Progress in Computer Chess.'' [http://www.aisb.org.uk/aisbq/qarchive.shtml AISB Quarterly], reprinted in [[ICGA Journal#4_3|ICCA Newsletter, Vol. 4. No. 3]], [http://arno.uvt.nl/show.cgi?fid=106747 pdf]</ref>
* [[Ken Thompson]] ('''1986'''). ''Retrograde Analysis of Certain Endgames''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]], [http://pdos.csail.mit.edu/~rsc/thompson86endgame.pdf pdf]
* [[Edward Komissarchik]], [[Aaron L. Futer]] ('''1986'''). ''Computer Analysis of a Queen Endgame''. [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]]
* [[Lewis Stiller]] ('''1988'''). ''Massively Parallel Retrograde Endgame Analysis''. BUCS Tech. Report #88-014, Boston University, Computer Science Department.
* [http://www.informatik.uni-trier.de/~ley/pers/hy/a/Alden:B=_E=_P=.html B. E. P. Alden], [[Max Bramer]] ('''1988'''). ''An Expert System for Solving Retrograde-Analysis Chess Problems.'' [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_29.html International Journal of Man-Machine Studies, Vol. 29, No. 2]
* [[Michael Schlosser]] ('''1988'''). ''Computers and Chess-Problem Composition.'' [[ICGA Journal#11_4|ICCA Journal, Vol. 11, No. 4]]
* [[David Forthoffer]], [[Lars Rasmussen]], [[Sito Dekker]] ('''1989'''). ''A Correction to some KRKB-Database Results''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
* [[Ingo Althöfer]] ('''1989'''). ''Retrograde Analysis and two Computerizable Definitions of the Quality of Chess Games.'' [[ICGA Journal#12_2|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.'' [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
* [[Ralph Gasser]] ('''1991'''). ''Applying Retrograde Analysis to Nine Men’s Morris.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]
* [[Rob Lake|Robert Lake]], [[Jonathan Schaeffer]], [[Paul Lu]] ('''1993'''). ''Solving Large Retrograde Analysis Problems Using a Network of Workstations''. Technical Report, TR93-13, [ftp://ftp.cs.ualberta.ca/pub/TechReports/1993/TR93-13/ ps]
* [[Rob Lake|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''. [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'''). ''[http://jespertk.dk/Jesper/public/master_thesis/ Generation and compression of endgame tables in chess with fast random access using OBDDs]''. Master thesis</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]]
* [[Christoph Wirth]], [[Jürg Nievergelt]] ('''1999'''). ''Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame.'' [[ICGA Journal#22_2|ICCA Journal, Vol. 22, No. 2]]
==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 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]
* [[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]
* [[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'''). ''[http://link.springer.com/chapter/10.1007/11674399_10 An External-Memory Retrograde Analysis Algorithm]''. [[CG 2004]]
==2005 ...==
* [[Jesper Torp Kristensen]] ('''2005'''). ''[http://jespertk.dk/Jesper/public/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], [http://jespertk.dk/Jesper/public/master_thesis/report/report.pdf pdf]
* [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2006'''). ''[http://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.umn.edu/~hrfang/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]], [http://www-users.cs.umn.edu/%7Ehrfang/papers/cantstopj.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]
* [[Dan Heisman]] ('''2009'''). ''Steinitz, Zermelo, and Elkies''. [http://www.chesscafe.com/text/skittles358.pdf pdf] from [https://en.wikipedia.org/wiki/ChessCafe.com ChessCafe.com], on [https://en.wikipedia.org/wiki/Wilhelm_Steinitz 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 [http://www.iis.sinica.edu.tw/~tshsu/tcg2010/slides/slide12.pdf 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'''). ''[http://bib.irb.hr/prikazi-rad?&rad=445958 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, [https://en.wikipedia.org/wiki/Vara%C5%BEdin Varaždin], [https://en.wikipedia.org/wiki/Croatia Croatia] <ref>[https://en.wikipedia.org/wiki/Coq Coq from Wikipedia]</ref>
* [[Marko Maliković]] ('''2011'''). ''Automated Reasoning about Retrograde Chess Problems using Coq''. [http://argo.matf.bg.ac.rs/events/2011/fatpa2011/fatpa2011.html Fourth Workshop on Formal and Automated Theorem Proving and Applications], [https://en.wikipedia.org/wiki/Belgrade Belgrade], [https://en.wikipedia.org/wiki/Serbia Serbia], [http://argo.matf.bg.ac.rs/events/2011/fatpa2011/slides/MarkoMalikovic.pdf slides as pdf]
* [[Jan van Rijn]], [[Jonathan K. Vis]] ('''2013'''). ''Complexity and Retrograde Analysis of the Game Dou Shou Qi''. [http://bnaic2013.tudelft.nl/ BNAIC 2013] <ref>[https://en.wikipedia.org/wiki/Jungle_%28board_game%29 Jungle (board game) from Wikipedia]</ref>
* [[Jan van Rijn]], [[Jonathan K. Vis]] ('''2014'''). ''Endgame Analysis of Dou Shou Qi''. [[ICGA Journal#37_2|ICGA Journal, Vol. 37, No. 2]], [http://www.liacs.nl/~jvrijn/pdf/pub/icga2014a.pdf 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#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]]
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b42e13fffe70a74e retrograde analysis] by Stefan Schroedl, [[Computer Chess Forums|rgcc]], August 15, 1995
==2000 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/c2509d7520be9ba7 reverse engineering] by NoKetch, [[Computer Chess Forums|rgcc]], June 16, 2000
* [https://www.stmintz.com/ccc/index.php?id=162252 EGTB: Better algorithm] by [[Urban Koistinen]], [[CCC]], April 07, 2001 <ref>[http://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]]</ref>
* [http://groups.google.com/group/rec.games.chess.computer/msg/392bcd5797808c0e Re: How endgame tablebases work] by [[Bruce Moreland]], [[Computer Chess Forums|rgcc]], July 19, 2001
* [https://www.stmintz.com/ccc/index.php?id=200335 Generating egtbs ICGAJ] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], December 04, 2001 <ref>[[Ren Wu]], [[Don Beal]] ('''2001'''). ''Fast, Memory-efficient Retrograde Algorithms''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]]</ref> <ref>[http://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]]</ref>
: [https://www.stmintz.com/ccc/index.php?id=200376 Wu/Beal predates Koistinen] by [[Guy Haworth]], [[CCC]], December 04, 2001
* [http://groups.google.com/group/rec.games.abstract/browse_frm/thread/48cca090ce094620 Question about retrograde analysis algorithm for endgame databases] by mathpolymath, [[Computer Chess Forums|rec.games.abstract]], April 24, 2002 <ref>[[Ren Wu]], [[Don Beal]] ('''2001'''). ''Fast, Memory-efficient Retrograde Algorithms''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]]</ref>
==2005 ...==
* [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
* [http://www.talkchess.com/forum/viewtopic.php?t=23214 Could this program be written?] by [[Steven Edwards]], [[CCC]], August 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24713 Retrograde analysis] by Geolm, [[CCC]], November 04, 2008
==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&start=6 Re: Reverse move generation] by [[Harm Geert Muller]], December 30, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=63515 Position Legally Reachable?] by [[Mark Lefler]], [[CCC]], March 21, 2017
=External Links=
==Retrograde Analysis==
* [https://en.wikipedia.org/wiki/Retrograde_analysis Retrograde analysis from Wikipedia]
* [http://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]]
* [http://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]
* [http://www.univie.ac.at/bvi/jimmy/Artikel/Sterbetag.htm Attempt of a Retrograde Computation of Age] by [[Werner DePauli-Schimanovich-Göttig|Werner DePauli-Schimanovich]]
==Programs==
* [http://lestourtereaux.free.fr/euclide/ Euclide 1.11 - Home] by [[Étienne Dupuis]] » [[Euclide]]
* [http://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]]
==Induction==
* [https://en.wikipedia.org/wiki/Inductive_reasoning Inductive reasoning from Wikipedia]
* [https://en.wikipedia.org/wiki/Backward_induction Backward induction from Wikipedia]
* [https://en.wikipedia.org/wiki/Backward_chaining Backward chaining from Wikipedia]
==Retrograde==
* [https://en.wikipedia.org/wiki/Retrograde Retrograde (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Retrograde_motion 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]
* [http://darrylreeves.com/ Darryl Reeves] - [http://www.mytotoro.net/darryl-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}}
==Analysis==
* [https://en.wikipedia.org/wiki/Analysis Analysis from Wikipedia]
* [https://en.wikipedia.org/wiki/Analysis_%28disambiguation%29 Analysis (disambiguation) from Wikipedia]
=References=
<references />
'''[[Knowledge|Up one Level]]'''
[[FILE:RetrogradeAnalysissmurpiknik.jpg|border|right|thumb|link=http://www.flickr.com/photos/smurpiknik/5149247538/in/photostream| Retrograde analysis <ref>[http://www.flickr.com/photos/smurpiknik/5149247538/in/photostream Ретроградный анализ. / Retrograde analysis], [http://www.flickr.com/photos/smurpiknik/with/5149247538/#photo_5149247538 Flickr: Fotostream by Segaboy]</ref> ]]
'''Retrograde Analysis''',<br/>
a method in [https://en.wikipedia.org/wiki/Game_theory game theory] to solve [[Chess Position|game positions]] for [https://en.wikipedia.org/wiki/Best_response optimal play] by [https://en.wikipedia.org/wiki/Backward_induction backward induction] from known outcomes. A sub-genre of solving certain [https://en.wikipedia.org/wiki/Chess_problem chess problems] uses retrograde analysis to determine which [[Moves|moves]] were played to reach a position, and for the [https://en.wikipedia.org/wiki/Proof_game proof game] whether a position is legal in the sense that it could be reached by a series of [[Legal Move|legal moves]] from the [[Initial Position|initial position]].
<span id="History"></span>
=History=
History based on [[Lewis Stiller]], ''Multilinear Algebra and Chess Endgames'' <ref>[[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]</ref>
The mathematical justification for the retrograde analysis algorithm was already implicit in the 1912 paper of [[Ernst Zermelo]] <ref>[[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''</ref>. Additional theoretical work was done by [[John von Neumann]] and [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] <ref>[[John von Neumann]] and [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] ('''1944'''). ''Theory of Games and Economic Behavior''. Princeton University Press, Princeton, NJ</ref>.
The contemporary [[Dynamic Programming|dynamic programming]] methodology, which defines the field of retrograde endgame analysis, was discovered by [[Richard E. Bellman]] in 1965 <ref>[[Richard E. Bellman]] ('''1965'''). ''[http://www.rand.org/pubs/papers/P3013/ On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers].'' [https://en.wikipedia.org/wiki/Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America PNAS]</ref>. Bellman had considered game theory from a classical perspective as well <ref>[[Richard E. Bellman]] ('''1954'''). ''On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems''. Technical Report P-473, [https://en.wikipedia.org/wiki/RAND_Corporation RAND Corporation], [https://en.wikipedia.org/wiki/Santa_Monica,_California Santa Monica, CA]</ref> <ref>[[Richard E. Bellman]] ('''1957'''). ''The Theory of Games''. Technical Report P-1062, [https://en.wikipedia.org/wiki/RAND_Corporation RAND Corporation], [https://en.wikipedia.org/wiki/Santa_Monica,_California Santa Monica, CA]</ref>, but his work came to fruition in his 1965 paper, where he observed that the entire [https://en.wikipedia.org/wiki/State_space_%28dynamical_system%29 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 [[Search|forward search]], dynamic programming, and [[Evaluation|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 <ref>[[Rob Lake|Robert Lake]], [[Jonathan Schaeffer]], [[Paul Lu]] ('''1994'''). ''Solving Large Retrograde Analysis Problems Using a Network of Workstations''. [[Advances in Computer Chess 7]]</ref>, [[Ralph Gasser]] in the domain of [[Nine Men’s Morris]] <ref>[[Ralph Gasser]] ('''1991'''). ''Applying Retrograde Analysis to Nine Men’s Morris.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]</ref>, and [[John Romein]] with [[Henri Bal]] in the domain of [[Awari]] <ref>[[John Romein]], [[Henri Bal]] ('''2003'''). ''Solving the Game of Awari using Parallel Retrograde Analysis''. IEEE Computer, Vol. 36, No. 10</ref>. The first retrograde analysis implementation was due to [[Thomas Ströhlein]], whose important 1970 dissertation described the solution of several pawnless 4-piece endgames <ref>[[Thomas Ströhlein]] ('''1970'''). ''Untersuchungen über kombinatorische Spiele.'' Ph.D. Thesis, [[Technical University of Munich]] (German)</ref>.
<span id="Algorithm"></span>
=Algorithm=
Retrograde analysis is the basic [[Algorithms|algorithm]] to construct [[Endgame Tablebases]]. A [https://en.wikipedia.org/wiki/Bijection bijective function] is used to map [[Chess Position|chess positions]] to [https://en.wikipedia.org/wiki/G%C3%B6del_numbering Gödel numbers] which index a database of bitmaps during construction and retrieval, in its simplest form based on a multi-dimensional [[Array|array]] index. Following description is based on [[Ken Thompson|Ken Thompson's]] paper ''Retrograde Analysis of Certain Endgames'' with [[Endgame Tablebases#DTM|depth to mate (DTM)]] metric <ref>[[Ken Thompson]] ('''1986'''). ''Retrograde Analysis of Certain Endgames''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]</ref>, 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 [[Iteration|iterative]] generation process:
* B<span style="vertical-align: sub;font-size: 80%;">i</span> set of the latest newly found Black-to-move and lose in i moves positions
* W<span style="vertical-align: sub;font-size: 80%;">i</span> 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 B<span style="vertical-align: sub;font-size: 80%;">i</span> so far
* W set of all currently known White-to-move and win positions, union of all W<span style="vertical-align: sub;font-size: 80%;">i</span> so far
* 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.
'''for''' (i=0; B<span style="vertical-align: sub; font-size: 80%;">i</span>; i++)
# Every parent of a B<span style="vertical-align: sub; font-size: 80%;">i</span> position is a White-to-move won position - newly-won positions W<span style="vertical-align: sub; font-size: 80%;">i+1</span> are parents of a B<span style="vertical-align: sub; font-size: 80%;">i</span> not (yet) in W
# W<span style="vertical-align: sub;font-size: 80%;">i+1</span> becomes subset of W
# Every parent of a W<span style="vertical-align: sub;font-size: 80%;">i+1</span> position is a Black-to-move and lose position if Black wanted to mate himself, stored in J<span style="vertical-align: sub;font-size: 80%;">i+1</span>
# Only if all successors (by generating and making legal moves <ref>dubbed "grandfather" method, [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</ref>) of a J<span style="vertical-align: sub; font-size: 80%;">i+1</span> position are member of W, the J<span style="vertical-align: sub; font-size: 80%;">i+1</span> position becomes member of B<span style="vertical-align: sub;font-size: 80%;">i+1</span> and B
The algorithm terminates, if no more newly predecessor positions were found, that is either W<span style="vertical-align: sub;font-size: 80%;">i+1</span> or B<span style="vertical-align: sub;font-size: 80%;">i+1</span> 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|draw]], White-to-move and lose, Black-to-move and won, or illegal positions.
=See also=
* [[Chess Problems, Compositions and Studies]]
* [[Chess Problem Solving Engines]]
* [[Corresponding Squares]]
* [[Dynamic Programming]]
* [[Endgame Bitbases]]
* [[Endgame Tablebases]]
* [[Oracle]]
* [[Transposition#RetrogradeAnalysis|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 ...==
* [[Mathematician#DenesKoenig|Dénes Kőnig]] ('''1927'''). ''[http://acta.fyx.hu/acta/showCustomerArticle.action?id=5131&dataObjectType=article&returnAction=showCustomerVolume&sessionDataSetId=2b29ea26fa2c9ba Über eine Schlussweise aus dem Endlichen ins Unendliche]''. [http://acta.fyx.hu/acta/home.action?noDataSet=true Acta Scientiarum Mathematicarum] ([https://en.wikipedia.org/wiki/University_of_Szeged University of Szeged])
==1940 ...==
* [[John von Neumann]], [https://en.wikipedia.org/wiki/Oskar_Morgenstern Oskar Morgenstern] ('''1944'''). ''Theory of Games and Economic Behavior''. Princeton University Press, Princeton, NJ
==1960 ...==
* [[Richard E. Bellman]] ('''1965'''). ''[http://www.rand.org/pubs/papers/P3013/ On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers].'' [https://en.wikipedia.org/wiki/Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America PNAS]
* [[Vladimir E. Alekseev]] ('''1969'''). ''[http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=AD0689470 Compilation of Chess Problems on a Computer]''. Technical translation FSTC-HT-23-124-69, US Army, NTIS AD 689470 ([http://www.worldcat.org/title/problemy-kibernetiki/oclc/1762911 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 [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]] ('''1986''')
* [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=55935 A. G. Alexandrov], [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=96113 A. M. Baraev], [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=96114 Ya. Yu. Gol'fand], [[Edward Komissarchik]], [[Aaron L. Futer]] ('''1977'''). ''[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=7425&option_lang=eng Computer analysis of rook end game]''. [https://en.wikipedia.org/wiki/Automation_and_Remote_Control Avtomatika i Telemekhanika], No. 8, 113–117
* [[Thomas Ströhlein]], [[Ludwig Zagler]] ('''1977'''). ''[http://www.sciencedirect.com/science/article/pii/0012365X77900334 Analyzing games by Boolean matrix iteration]''. [https://en.wikipedia.org/wiki/Discrete_Mathematics_%28journal%29 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'''). ''[https://zbmath.org/?q=an:03637634 Programming endgames with few pieces]''. [https://en.wikipedia.org/wiki/Doklady_Physics Soviet Physics. Doklady], No. 23
* [[Vladimir Arlazarov]], [[Aaron L. Futer]] ('''1979'''). ''Computer Analysis of a Rook End-Game''. [http://www.doc.ic.ac.uk/~shm/MI/mi9.html 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'''). ''[http://www.amazon.com/Chess-Mysteries-Sherlock-Holmes/dp/0394737571 The Chess Mysteries of Sherlock Holmes]''. [https://en.wikipedia.org/wiki/Alfred_A._Knopf Alfred A. Knopf], New York <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/MyFmpXxqccg/Z6WgNuoF-hcJ Smullyan Problem in Sherlock Holmes book] by Christopher Heckman, [[Computer Chess Forums|rgcc]], January 18, 2013</ref>
==1980 ...==
* [[Raymond Smullyan]] ('''1981'''). ''[http://www.chesslund.com/detail.asp?id=2206&n=Smullyan-The-Chess-Mysteries-of-the-Arabian-Knights The Chess Mysteries of the Arabian Knights ]''. [https://en.wikipedia.org/wiki/Alfred_A._Knopf Alfred A. Knopf], New York <ref>[http://de.wikipedia.org/wiki/Schachkomposition#Retrospektive_.28Retroanalyse.29 Retrospektive (Retroanalyse)] from German Wikipedia, [[Mathematician#Smullyan|Raymond Smullyan]], [https://en.wikipedia.org/wiki/The_Guardian Manchester Guardian], 1957</ref>
* [[Max Bramer]], [http://www.informatik.uni-trier.de/~ley/pers/hy/a/Alden:B=_E=_P=.html B. E. P. Alden] ('''1982'''). ''A Program for Solving Retrograde Analysis Chess Problems.'' [[Advances in Computer Chess 3]] <ref>[[Jaap van den Herik]] ('''1981'''). ''Progress in Computer Chess.'' [http://www.aisb.org.uk/aisbq/qarchive.shtml AISB Quarterly], reprinted in [[ICGA Journal#4_3|ICCA Newsletter, Vol. 4. No. 3]], [http://arno.uvt.nl/show.cgi?fid=106747 pdf]</ref>
* [[Ken Thompson]] ('''1986'''). ''Retrograde Analysis of Certain Endgames''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]], [http://pdos.csail.mit.edu/~rsc/thompson86endgame.pdf pdf]
* [[Edward Komissarchik]], [[Aaron L. Futer]] ('''1986'''). ''Computer Analysis of a Queen Endgame''. [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]]
* [[Lewis Stiller]] ('''1988'''). ''Massively Parallel Retrograde Endgame Analysis''. BUCS Tech. Report #88-014, Boston University, Computer Science Department.
* [http://www.informatik.uni-trier.de/~ley/pers/hy/a/Alden:B=_E=_P=.html B. E. P. Alden], [[Max Bramer]] ('''1988'''). ''An Expert System for Solving Retrograde-Analysis Chess Problems.'' [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_29.html International Journal of Man-Machine Studies, Vol. 29, No. 2]
* [[Michael Schlosser]] ('''1988'''). ''Computers and Chess-Problem Composition.'' [[ICGA Journal#11_4|ICCA Journal, Vol. 11, No. 4]]
* [[David Forthoffer]], [[Lars Rasmussen]], [[Sito Dekker]] ('''1989'''). ''A Correction to some KRKB-Database Results''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
* [[Ingo Althöfer]] ('''1989'''). ''Retrograde Analysis and two Computerizable Definitions of the Quality of Chess Games.'' [[ICGA Journal#12_2|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.'' [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
* [[Ralph Gasser]] ('''1991'''). ''Applying Retrograde Analysis to Nine Men’s Morris.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]
* [[Rob Lake|Robert Lake]], [[Jonathan Schaeffer]], [[Paul Lu]] ('''1993'''). ''Solving Large Retrograde Analysis Problems Using a Network of Workstations''. Technical Report, TR93-13, [ftp://ftp.cs.ualberta.ca/pub/TechReports/1993/TR93-13/ ps]
* [[Rob Lake|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''. [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'''). ''[http://jespertk.dk/Jesper/public/master_thesis/ Generation and compression of endgame tables in chess with fast random access using OBDDs]''. Master thesis</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]]
* [[Christoph Wirth]], [[Jürg Nievergelt]] ('''1999'''). ''Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame.'' [[ICGA Journal#22_2|ICCA Journal, Vol. 22, No. 2]]
==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 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]
* [[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]
* [[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'''). ''[http://link.springer.com/chapter/10.1007/11674399_10 An External-Memory Retrograde Analysis Algorithm]''. [[CG 2004]]
==2005 ...==
* [[Jesper Torp Kristensen]] ('''2005'''). ''[http://jespertk.dk/Jesper/public/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], [http://jespertk.dk/Jesper/public/master_thesis/report/report.pdf pdf]
* [[James Glenn]], [[Haw-ren Fang]], [[Clyde Kruskal]] ('''2006'''). ''[http://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.umn.edu/~hrfang/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]], [http://www-users.cs.umn.edu/%7Ehrfang/papers/cantstopj.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]
* [[Dan Heisman]] ('''2009'''). ''Steinitz, Zermelo, and Elkies''. [http://www.chesscafe.com/text/skittles358.pdf pdf] from [https://en.wikipedia.org/wiki/ChessCafe.com ChessCafe.com], on [https://en.wikipedia.org/wiki/Wilhelm_Steinitz 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 [http://www.iis.sinica.edu.tw/~tshsu/tcg2010/slides/slide12.pdf 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'''). ''[http://bib.irb.hr/prikazi-rad?&rad=445958 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, [https://en.wikipedia.org/wiki/Vara%C5%BEdin Varaždin], [https://en.wikipedia.org/wiki/Croatia Croatia] <ref>[https://en.wikipedia.org/wiki/Coq Coq from Wikipedia]</ref>
* [[Marko Maliković]] ('''2011'''). ''Automated Reasoning about Retrograde Chess Problems using Coq''. [http://argo.matf.bg.ac.rs/events/2011/fatpa2011/fatpa2011.html Fourth Workshop on Formal and Automated Theorem Proving and Applications], [https://en.wikipedia.org/wiki/Belgrade Belgrade], [https://en.wikipedia.org/wiki/Serbia Serbia], [http://argo.matf.bg.ac.rs/events/2011/fatpa2011/slides/MarkoMalikovic.pdf slides as pdf]
* [[Jan van Rijn]], [[Jonathan K. Vis]] ('''2013'''). ''Complexity and Retrograde Analysis of the Game Dou Shou Qi''. [http://bnaic2013.tudelft.nl/ BNAIC 2013] <ref>[https://en.wikipedia.org/wiki/Jungle_%28board_game%29 Jungle (board game) from Wikipedia]</ref>
* [[Jan van Rijn]], [[Jonathan K. Vis]] ('''2014'''). ''Endgame Analysis of Dou Shou Qi''. [[ICGA Journal#37_2|ICGA Journal, Vol. 37, No. 2]], [http://www.liacs.nl/~jvrijn/pdf/pub/icga2014a.pdf 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#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]]
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b42e13fffe70a74e retrograde analysis] by Stefan Schroedl, [[Computer Chess Forums|rgcc]], August 15, 1995
==2000 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/c2509d7520be9ba7 reverse engineering] by NoKetch, [[Computer Chess Forums|rgcc]], June 16, 2000
* [https://www.stmintz.com/ccc/index.php?id=162252 EGTB: Better algorithm] by [[Urban Koistinen]], [[CCC]], April 07, 2001 <ref>[http://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]]</ref>
* [http://groups.google.com/group/rec.games.chess.computer/msg/392bcd5797808c0e Re: How endgame tablebases work] by [[Bruce Moreland]], [[Computer Chess Forums|rgcc]], July 19, 2001
* [https://www.stmintz.com/ccc/index.php?id=200335 Generating egtbs ICGAJ] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], December 04, 2001 <ref>[[Ren Wu]], [[Don Beal]] ('''2001'''). ''Fast, Memory-efficient Retrograde Algorithms''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]]</ref> <ref>[http://www.abc.se/~m10051/eg.txt Computing endgames with few men] by [[Urban Koistinen]]</ref>
: [https://www.stmintz.com/ccc/index.php?id=200376 Wu/Beal predates Koistinen] by [[Guy Haworth]], [[CCC]], December 04, 2001
* [http://groups.google.com/group/rec.games.abstract/browse_frm/thread/48cca090ce094620 Question about retrograde analysis algorithm for endgame databases] by mathpolymath, [[Computer Chess Forums|rec.games.abstract]], April 24, 2002 <ref>[[Ren Wu]], [[Don Beal]] ('''2001'''). ''Fast, Memory-efficient Retrograde Algorithms''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]]</ref>
==2005 ...==
* [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
* [http://www.talkchess.com/forum/viewtopic.php?t=23214 Could this program be written?] by [[Steven Edwards]], [[CCC]], August 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24713 Retrograde analysis] by Geolm, [[CCC]], November 04, 2008
==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&start=6 Re: Reverse move generation] by [[Harm Geert Muller]], December 30, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=63515 Position Legally Reachable?] by [[Mark Lefler]], [[CCC]], March 21, 2017
=External Links=
==Retrograde Analysis==
* [https://en.wikipedia.org/wiki/Retrograde_analysis Retrograde analysis from Wikipedia]
* [http://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]]
* [http://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]
* [http://www.univie.ac.at/bvi/jimmy/Artikel/Sterbetag.htm Attempt of a Retrograde Computation of Age] by [[Werner DePauli-Schimanovich-Göttig|Werner DePauli-Schimanovich]]
==Programs==
* [http://lestourtereaux.free.fr/euclide/ Euclide 1.11 - Home] by [[Étienne Dupuis]] » [[Euclide]]
* [http://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]]
==Induction==
* [https://en.wikipedia.org/wiki/Inductive_reasoning Inductive reasoning from Wikipedia]
* [https://en.wikipedia.org/wiki/Backward_induction Backward induction from Wikipedia]
* [https://en.wikipedia.org/wiki/Backward_chaining Backward chaining from Wikipedia]
==Retrograde==
* [https://en.wikipedia.org/wiki/Retrograde Retrograde (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Retrograde_motion 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]
* [http://darrylreeves.com/ Darryl Reeves] - [http://www.mytotoro.net/darryl-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}}
==Analysis==
* [https://en.wikipedia.org/wiki/Analysis Analysis from Wikipedia]
* [https://en.wikipedia.org/wiki/Analysis_%28disambiguation%29 Analysis (disambiguation) from Wikipedia]
=References=
<references />
'''[[Knowledge|Up one Level]]'''
