Endgame tablebase
In chess, the endgame tablebase, or simply the tablebase, is a computerised database containing precalculated evaluations of endgame positions. Tablebases are used to analyse finished games, as well as by chess engines to evaluate positions during play. Tablebases are typically exhaustive, covering every legal arrangement of a specific selection of pieces on the board, with both White and Black to move. For each position, the tablebase records the ultimate result of the game and the number of moves required to achieve that result, both assuming perfect play. Because every legal move in a covered position results in another covered position, the tablebase acts as an oracle that always provides the optimal move.
Tablebases are generated by retrograde analysis, working backwards from checkmated positions. By 2005, tablebases for all positions having up to six pieces, including the two kings, had been created. By August 2012, tablebases had solved chess for almost every position with up to seven pieces, with certain subclasses omitted due to their assumed triviality; these omitted positions were included by August 2018., work is still underway to solve all eight-piece positions.
Tablebases have profoundly advanced the chess community's understanding of endgame theory. Some positions which humans had analysed as draws were proven to be winnable; in some cases, tablebase analysis found a mate in more than five hundred moves, far beyond the ability of humans, and beyond the capability of a computer during play. This caused the fifty-move rule to be called into question, since many positions were discovered that were winning for one side but drawn during play because of this rule. Initially, some exceptions to the fifty-move rule were introduced, but when more extreme cases were later discovered, these exceptions were removed. Tablebases also facilitate the composition of endgame studies.
While endgame tablebases exist for other board games, such as checkers, nine men's morris, and some chess variants, the term endgame tablebase is usually assumed to refer to chess tablebases.
Background
Physical limitations of computer hardware aside, 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, i.e. algorithms that can produce perfect play from any position, are known for some simple games such as Tic Tac Toe/Noughts and crosses and Connect Four. Weak solutions exist for somewhat more complex games, such as checkers. Other games, such as chess and Go, have not been solved because their game complexity is far 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 early 1930s. 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 heuristics 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. Instead of analyzing forward from the position currently on the board, the database would analyze backward from positions where one player was checkmated or stalemated. Thus, a chess computer would no longer need to analyze endgame positions during the game because they would have been solved beforehand. It would no longer make mistakes because the tablebase always yielded the best possible move.
In 1970, Thomas Ströhlein published a doctoral thesis with analysis of the following classes of endgame:,,,,, and. In 1977, Ken Thompson's KQKR tablebase was used in a match against Grandmaster Walter Browne.
Thompson and others helped extend tablebases to cover all four- and five-piece endgames, including,, and. Lewis Stiller published a thesis with research on some six-piece tablebase endgames in 1991.
More recent contributors include:
- John Nunn, foremost data miner of chess endgames and prolific endgame author.
- Eugene Nalimov, after whom the popular Nalimov tablebases are named. Their total size is about 1.2 TB.
- Eiko Bleicher, who has adapted the tablebase concept to a program called "Freezer"
- Guy Haworth, an academic at the University of Reading, who has published extensively in the ICGA Journal and elsewhere;
- Marc Bourzutschky and Yakov Konoval, who have collaborated to analyze endgames with seven pieces on the board;
- Peter Karrer, who constructed a specialized seven-piece tablebase for the endgame of the Kasparov versus The World online match;
- Vladimir Makhnychev and Victor Zakharov from Moscow State University, who completed the 4+3 DTM tablebases in July 2012 and the 5+2 DTM-tablebases in August 2012. They were generated on a supercomputer named Lomonosov. Their total size is about 140 TB. They were attacked by a ransomware in 2021, and have been offline since then.
- Ronald de Man and Bojun Guo, who generated the seven man DTZ tablebase called the Syzygy tablebase in 2018. They were able to reduce the size of seven-man tablebases from 140 TB to 18.4 TB.
| Number of pieces | Number of positions | Database name | Metric | Completed in | Size |
| 5 or fewer | 26,038,209,193 | Syzygy | DTZ | 2013 | 939 MB |
| 5 or fewer | 26,038,209,193 | Nalimov | DTM | 2005 | 7.05 GB |
| 6 | 3,787,154,440,416 | Syzygy | DTZ | 2013 | 150.2 GB |
| 6 | 3,787,154,440,416 | Nalimov | DTM | 2005 | 1.2 TB |
| 7 | 423,836,835,667,331 | Syzygy | DTZ | 2018 | 18.4 TB |
| 7 | 423,836,835,667,331 | Lomonosov | DTM | 2012 | 140 TB |
| 8 | 38,176,306,877,748,245 | ~2 PB |
Generating tablebases
Metrics
Before creating a tablebase, a programmer must choose a metric of optimality which means they must define at what point a player has "won" the game. Every position solved by the tablebase will either have a distance from this specific point or will get classified as a draw. To date, three different metrics have been used:- Depth to mate – The game can only be won by checkmate.
- Depth to conversion – The game can be won by checkmate, capturing material or promoting a pawn. For example, in KQKR, conversion occurs when White captures the Black rook.
- Depth to zeroing – The game can be won by checkmate, capturing material or moving a pawn. For example, in KRPKR, zeroing occurs when White moves their pawn closer to the eighth rank.
The difference between DTC and DTM can be understood by analyzing the diagram at the right. The optimal play depends on which metric is used.
| Metric | Play | DTC | DTM |
| DTC | 1. Qxd1 Kc8 2. Qd2 Kb8 3. Qd8# | 1 | 3 |
| DTM | 1. Qc7+ Ka8 2. Qa7# | 2 | 2 |
According to the DTC metric, White should capture the rook because that leads immediately to a position which will certainly win, but it will take two more moves actually to checkmate. In contrast according to the DTM metric, White mates in two moves, so DTM = DTC = 2.
This difference is typical of many endgames. DTC is always smaller than or equal to DTM, but the DTM metric always leads to the quickest checkmate. Incidentally, DTC = DTM in the unusual endgame of two knights versus one pawn because capturing the pawn results in a draw, unless the capture is also checkmate.
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, the computer must describe approximately 40,000 unique legal positions.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. 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 60 remaining squares where the White king can legally be placed, and then by at most 62 squares for the White queen. The product 10×60×62 = 37,200. Several hundred of these positions are illegal, impossible, or symmetrical reflections of each other, so the actual number is somewhat smaller.
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 no 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, which is 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.