| Endgame Tablebase |
Article Index for Endgame |
Website Links For Endgame |
Information AboutEndgame Tablebase |
| CATEGORIES ABOUT ENDGAME TABLEBASE | |
| chess endgames | |
| chess terms | |
| computer chess | |
| databases | |
|
An endgame tablebase is a computerized Database of all Chess positions within certain Endgame s. The tablebase reveals the Game-theoretical value of each position (win, loss, or Draw ), and how many moves it will take to achieve that result with Perfect Play . Thus, the tablebase acts as an Oracle , always providing the optimal moves for both White and Black. Tablebases are generated by Retrograde Analysis , working backwards from a Checkmate d position. Tablebases have solved chess for every position with six pieces or fewer. The results of the solution have profoundly advanced the chess community's understanding of endgame theory. Some positions which humans had analyzed as draws were proved to be decisive; the tablebase could see a mate in 100 moves or more, far beyond the Horizon of both humans and computers. Tablebases have enhanced competitive play and facilitated the composition of Endgame Studies . They provide a powerful analytical tool, enabling students of chess to discover its deepest secrets. BACKGROUND In principle, it is possible to Solve Any Game under the condition that the complete state is known and there is no random chance. Strong solutions are known for some simple games, such as Tic Tac Toe (draw with perfect play) and Connect Four (first player wins). Other games, such as chess (from the starting position) and Go , have not been solved because their Game Complexity is too vast for computers to evaluate all possible positions. To reduce the game complexity, researchers have modified these complex games by reducing the size of the board, or the number of pieces, or both. Computer Chess is one of the oldest domains of Artificial Intelligence , having begun in the 1940s. Claude Shannon proposed formal criteria for evaluating chess moves in 1949. In 1951, Alan Turing designed a primitive chess playing program, which assigned values for material and mobility; the program "played" chess based on Turing's manual calculations . However, even as competent chess programs began to develop, they exhibited a glaring weakness in playing the endgame. Programmers added specific Heuristic s for the endgame – for example, the King should move to the center of the board . However, a more comprehensive solution was needed. In 1965, Richard Bellman proposed the creation of a database to solve chess and Checkers endgames using Retrograde Analysis .1 Instead of analyzing ''forward'' from the position currently on the board, the database would analyze ''backward'' from positions where one player was Checkmate d. Thus, a chess computer would no longer need to analyze endgame positions during the game because they were solved beforehand. It would no longer make mistakes because the tablebase always played the best possible move. In 1970, Thomas Ströhlein published a doctoral thesis2See also 3 with analysis of the following classes of endgame: KQK, KRK, KPK, KQKR, KRKB, and KRKN (see Endgame Classification ).4 Ken Thompson and others helped extend tablebases to cover all four- and five-piece endgames, including in particular KBBKN, KQPKQ, and KRPKR .See also:
More recent contributors have included the following people:
The analysis of all endgames with up to six pieces (including the two kings) was completed in 2006. (However, tablebases with five pieces against a lone king have not been produced because the result is almost always obvious.) The tablebases for all positions with up to six pieces are available for free download, or can be queried on the web (see the external links below). Research on seven-piece tablebases is ongoing and may be completed by the end of 2015.8 GENERATING TABLEBASES Metrics: Depth to conversion and depth to mate
Before creating a tablebase, a programmer must choose a Metric of optimality – in other words, he must define at what point a player has "won" the game. Every position can be defined by its distance (i.e. the number of moves) from the desired endpoint. Two metrics are generally used:
Haworth has discussed two other metrics, namely "depth to zeroing-move" (DTZ) and "depth by the rule" (DTR). These metrics correct for the Fifty Move Rule , but few tablebases with these metrics have been released to the public.9 The difference between DTC and DTM can be understood by analyzing the diagram at right. How White should proceed depends on which metric is used. According to the DTC metric, White should capture the rook because that "wins" immediately (DTC = 1), but it will take two more moves to checkmate (DTM = 3). In contrast according to the DTM metric, White mates in two moves, so DTM = DTC = 2. This difference is typical of many endgames. Usually DTC is smaller than DTM, but the DTM metric leads to the quickest checkmate. Exceptions occur where the weaker side has only a king, and in the unusual endgame of Two Knights Versus One Pawn ; there DTC = DTM because either there is no defending material to capture or capturing the material does no good. (Indeed, capturing the defending pawn in the latter endgame results in a draw.) Step 1: Generating all possible positions
Once a metric is chosen, the first step is to generate all the positions with a given material. For example, to generate a DTM tablebase for the endgame of king and queen versus king (KQK), the computer must describe the 40,000 unique legal positions in an Array . Levy and Newborn explain that the number 40,000 derives from a Symmetry argument. The Black king can be placed on any of ten squares: a1, b1, c1, d1, b2, c2, d2, c3, d3, and d4 (see diagram). On any other square, its position can be considered equivalent by symmetry of rotation or reflection. Thus, there is no difference whether a Black king in a corner resides on a1, a8, h8, or h1. Multiply this number of 10 by at most 64 squares for placing the White king and then by at most 64 squares for the White queen. The product 10×64×64 = 40,960. Several hundred of these positions are illegal, impossible, or symmetrical reflections of each other, so the actual number is somewhat smaller .See also Stiller 1995:93-98. For each position, the tablebase evaluates the situation separately for White-to-move and Black-to-move. Assuming that White has the queen, almost all the positions are White wins, with checkmate forced in not more than ten moves. Some positions are draws because of Stalemate or the unavoidable loss of the queen. Each additional piece added to a Pawnless endgame multiplies the number of unique positions by about a factor of sixty – the approximate number of squares not already occupied by other pieces. Endgames with one or more pawns increase the complexity because the symmetry argument is reduced. Since pawns can move forward but not sideways, rotation and vertical reflection of the board produces a fundamental change in the nature of the position. The best calculation of symmetry is achieved by limiting one pawn to 24 squares in the rectangle a2-a7-d7-d2. All other pieces and pawns may be located in any of the 64 squares with respect to the pawn. Thus, an endgame with pawns has a complexity of 24/10 = 2.4 times a pawnless endgame with the same number of pieces. Step 2: Evaluating positions using retrograde analysis Tim Krabbé explains the process of generating a tablebase as follows: "The idea is that a database is made with all possible positions with a given material as in the preceding section . Then a subdatabase is made of all positions where Black is mate. Then one where White can give mate. Then one where Black cannot stop White giving mate next move. Then one where White can always reach a position where Black cannot stop him from giving mate next move. And so on, always a ply further away from mate until all positions that are thus connected to mate have been found. Then all of these positions are linked back to mate by the shortest path through the database. That means that, apart from 'equi-optimal' moves, all the moves in such a path are perfect: White's move always leads to the quickest mate, Black's move always leads to the slowest mate."10 Figure 1 illustrates the idea of retrograde analysis. White mates in two moves with 1. Kc6, leading to the position in Figure 2. Then if 1...Kb8 2. Qb7 mate, and if 1...Kd8 2. Qd7 mate (Figure 3). Figure 3, before White's second move, is defined as "mate in one Ply ." Figure 2, after White's first move, is "mate in two ply," regardless of how Black plays. Finally, the initial position in Figure 1 is "mate in three ply" (i.e., two moves) because it leads directly to Figure 2, which is already defined as "mate in two ply." This process, which links a current position to another position that could have existed one ply earlier, can continue indefinitely. Each position is evaluated as a win or loss in a certain number of moves. At the end of the retrograde analysis, positions which are not designated as wins or losses are necessarily draws.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Author | Lewis Benjamin Stiller |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Year | 1995 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Title | Exploiting symmetry on parallel architectures |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Publisher | PhD Thesis, Johns Hopkins University |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Url | http://usersrcncom/lstiller/thesispdf |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Format | PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Accessdate | 2007-05-04 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|