Only if all successors (by generating and making legal moves ) of a J i+1 position are member of W, the J i+1 position becomes member of B i+1 and B.Every parent of a W i+1 position is a Black-to-move and lose position if Black wanted to mate himself, stored in J i+1.Every parent of a B i position is a White-to-move won position - newly-won positions W i+1 are parents of a B i not (yet) in W.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. The algorithm starts in enumerating all Black-to-move checkmate positions B 0 with the material configuration under consideration, an un-move generator is used to to build predecessor or parent positions.
J i is temporary superset of B i not necessarily lose positions.W set of all currently known White-to-move and win positions, union of all W i so far.B set of all currently known Black-to-move and lose positions, union of all B i so far.W i set of the latest newly found White-to-move and win in i moves positions.B i set of the latest newly found Black-to-move and lose in i moves positions.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:
Following description is based on Ken Thompson's paper Retrograde Analysis of Certain Endgames with depth to mate (DTM) metric, and assumes White the winning side. 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. Retrograde analysis is the basic algorithm to construct Endgame Tablebases. The first retrograde analysis implementation was due to Thomas Ströhlein, whose important 1970 dissertation described the solution of several pawnless 4-piece endgames. in the domain of Checkers, Ralph Gasser in the domain of Nine Men’s Morris, and John Romein with Henri Bal in the domain of Awari.
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. Bellman had considered game theory from a classical perspective as well, 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.īellman 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. The contemporary dynamic programming methodology, which defines the field of retrograde endgame analysis, was discovered by Richard E. Additional theoretical work was done by John von Neumann and Oskar Morgenstern. History based on Lewis Stiller, Multilinear Algebra and Chess Endgames The mathematical justification for the retrograde analysis algorithm was already implicit in the 1912 paper of Ernst Zermelo.
0 kommentar(er)
