Difference between revisions of "Retrograde Analysis"

From Chessprogramming wiki
Jump to: navigation, search
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++)

Revision as of 21:28, 18 December 2021

Home * Knowledge * Retrograde Analysis

Retrograde analysis [1]

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

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++)

  1. 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
  2. Wi+1 becomes subset of W
  3. 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
  4. 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

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 ...

1940 ...

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

Forum Posts

1995 ...

2000 ...

Wu/Beal predates Koistinen by Guy Haworth, CCC, December 04, 2001

2005 ...

2010 ...

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

2015 ...

2020 ...

External Links

Retrograde Analysis

Programs

Induction

Retrograde

Apparent retrograde motion from Wikipedia
Darryl Reeves, Kenny Banks, Joel Powell, Kenton "Boom" Bostick

Analysis

References

  1. Ретроградный анализ. / Retrograde analysis, Flickr: Fotostream by Segaboy
  2. Lewis Stiller (1996). Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf
  3. 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
  4. John von Neumann and Oskar Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ
  5. Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
  6. 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
  7. Richard E. Bellman (1957). The Theory of Games. Technical Report P-1062, RAND Corporation, Santa Monica, CA
  8. Robert Lake, Jonathan Schaeffer, Paul Lu (1994). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 7
  9. Ralph Gasser (1991). Applying Retrograde Analysis to Nine Men’s Morris. Heuristic Programming in AI 2
  10. John Romein, Henri Bal (2003). Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 10
  11. Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
  12. Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3
  13. dubbed "grandfather" method, Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
  14. Smullyan Problem in Sherlock Holmes book by Christopher Heckman, rgcc, January 18, 2013
  15. Retrospektive (Retroanalyse) from German Wikipedia, Raymond Smullyan, Manchester Guardian, 1957
  16. Jaap van den Herik (1981). Progress in Computer Chess. AISB Quarterly, reprinted in ICCA Newsletter, Vol. 4. No. 3, pdf
  17. 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
  18. Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
  19. Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
  20. Coq from Wikipedia
  21. Jungle (board game) from Wikipedia
  22. Karl's Race A Game on Karl Scherer's Alternating Tiling by Ingo Althöfer, 2006
  23. Computing endgames with few men by Urban Koistinen
  24. Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
  25. Computing endgames with few men by Urban Koistinen
  26. Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
  27. EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001
  28. Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001
  29. Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3

Up one Level