Endgame tablebase

In chess, an endgame tablebase, or simply tablebase, is a computerised database containing precalculated evaluations of endgame positions. Tablebases are used by players and chess engines to analyze games and positions. 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 assuming perfect play from both sides (i.e. a win for White, a win for Black, or a draw), and the number of moves required to achieve that result. Because every move from 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; the first complete seven-piece tablebase was released in August 2018¹. , work is still underway to solve all eight-piece positions. Tablebases have profoundly advanced the chess community's understanding of endgame theory.…

In chess, an endgame tablebase, or simply tablebase, is a computerised database containing precalculated evaluations of endgame positions. Tablebases are used by players and chess engines to analyze games and positions. 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 assuming perfect play from both sides (i.e. a win for White, a win for Black, or a draw), and the number of moves required to achieve that result. Because every move from 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; the first complete seven-piece tablebase was released in 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 previously believed to be drawn 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. 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 (the only material Black has) results in a draw, unless the capture is also checkmate. Each of these metrics has a counterpart moderated by the fifty-move rule – DTC 50 , DTZ 50 and DTM 50 – in which a win that cannot be forced within the rule's allowance is scored as a draw. A moderated depth is not a property of the position alone: it also depends on the ply-count pc, the number of ply already played since the last capture or pawn move. As pc rises the depth can grow until the win becomes "frustrated" and turns into a fifty-move draw; even a mate in two ply is frustrated once 99 ply have been spent. DTM 50 tables giving a depth for every value of pc were first computed for sub-6-man chess by Galen Huntington, and published with Guy Haworth in 2015¹. Endgames of fewer than five men are unaffected, as their maximum DTM is below 100 ply. Among five-man endgames the rule bites hardest in KBBKN and KNNKP, and therefore also in the six-man endgames upstream of them, KBBKNN, KNNKNP and KNNKPP. Moderation does not simply shorten wins: compared with the unrestricted maximum DTM for the same material, the longest DTM 50 win is shorter in some endgames – KBBKN, KNNKP, KRBKR and KQRKP among them – but longer in others, such as KPPKP, KPPKQ and KQPKQ. Since maximum DTZ exceeds 80, 240 and 510 moves in sub-6-man, sub-7-man and sub-8-man chess respectively, the fifty-move rule, now backed by the mandatory seventy-five-move rule, can be expected to frustrate more wins as men are added. 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 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. The result of this simplification is that, instead of searching for 48 * 47 = 2,256 permutations for the pawns' locations, there is only one permutation. Reducing the search space by a factor of 2,256 facilitates a much quicker calculation. Bleicher has designed a commercial program called "Freezer", which allows users to build new tablebases from existing Nalimov tablebases with a priori information. The program could produce a tablebase for positions with seven or more pieces with blocked pawns, even before tablebases for seven pieces became available. KBBKN — Bernhard Horwitz and Josef Kling (1851) proposed that Black can draw by entering a defensive fortress, but tablebases demonstrated a general win, with maximum DTC = 66 and maximum DTM = 78. (Also see pawnless chess endgame.) KNNKP – Maximum DTC = DTM = 115 moves. KNNNNKQ – The knights win in 62.5 percent of positions, with maximum DTM = 85 moves. KQRKQR – Despite the equality of material, the player to move wins in 67.74% of positions. The maximum DTC is 92, and the maximum DTM is 117. In both this endgame and KQQKQQ, the first player to check usually wins. KRNKNN and KRBKNN — Friedrich Amelung had analyzed these two endgames in the 1900s. KRNKNN and KRBKNN are won for the stronger side in 78% and 95% of the cases, respectively. Stiller's DTC tablebase revealed several lengthy wins in these endgames. The longest win in KRBKNN has a DTC of 223 and a DTM of 238 moves (not shown). Even more interesting is the position at right, where White wins starting with 1. Ke6! Stiller reported the DTC as 243 moves, and the DTM was later found to be 262 moves. For some years, a "mate-in-200" position (first diagram below) held the record for the longest computer-generated forced mate. (Otto Blathy had composed a "mate in 292 moves" problem in 1889, albeit from an illegal starting position. ) In May 2006, Bourzutschky and Konoval discovered a KQNKRBN position with a DTC of 517 moves, whose DTM was later found to be 545 moves. In 2012, when the Lomonosov 7-piece tablebase was being completed, a position was found with a record DTM of 549 moves (third diagram below). It was initially assumed that a 1000-move mate in one of the 8-man endgames would be found. However, cursory targeted research has currently only found a position with DTC 584, which was discovered in 2021 by Bourzutschky. Assuming this projection holds true, Haworth's Law (which states that the number of moves roughly doubles for each piece added) breaks down at this point. Many positions are winnable despite seeming to be non-winnable by force at first glance. For example, the position in the middle diagram is a win for Black in 154 moves (the white pawn is captured after around 80 moves).

Tables

3-man

4-man

5-man

6-man

7-man (some)

Web query server for Nalimov tablebases by Eiko Bleicher (up to six pieces) Web query server for Nalimov tablebases at ChessOK (up to six pieces) Web query server for Nalimov tablebases by Lokasoft (up to six pieces) Web query server for Nalimov tablebases at Shredder (up to six pieces) Web query server for Syzygy tablebases by Niklas Fiekas (up to seven pieces) Maximal positions, i.e. longest DTM positions for endgames with up to five pieces and some with six pieces, compiled by Kirill Kryukov

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372171863 under CC BY-SA 4.0; modifications have been made.