Endgame Tablebases

From Chessprogramming wiki
Jump to: navigation, search

Home * Knowledge * Endgame Tablebases

Samuel Bak - Persistence [1]

Endgame Tablebases, (EGTBs or EGTs)
precalculated endgame tables generated by an exhaustive retrograde analysis. During its game play and/or search, recognizing a specific material composition, a chess program can probe, or in principle compute these tables to determine the outcome of positions definitively and act as an oracle providing the optimal moves. The tables are usually divided into separate files for each material configuration and side to move. What all different formats of tablebases have in common is that every possible piece placement has its own, unique index number which represents the position where the information about the position is located in the file. Positions with non-null castling rights could be represented in an EGT but typically are not.

The term Tablebase opposed to endgame database was coined by Steven Edwards by means of a data vector and a single file access for both sides to move, when he introduced his Edwards' Tablebases, addressing several shortcomings of Ken Thompson's earlier database of positions with the weaker and hence potentially losing side to move only [2] .

Metrics

DTM

Depth to Mate 'Mate' is the ultimate goal and ends the game. For each position that is represented, 'DTM' indicates the theoretical value, and the number of winner's moves to 'Mate' if won/lost - assuming that the winner is minimizing and the loser is maximizing DTM.

DTC

Depth to Conversion 'Conversion' is the changing of the force on the board, by capture and/or Pawn-conversion. For each position that is represented, 'DTC' indicates the theoretical value, and the number of winner's moves to the goal of 'Won Conversion' if won/lost - assuming that the winner is minimizing and the loser is maximizing DTC. DTC £ DTM.

DTZ

Depth to Zeroing (of the ply count) The ply-count is zeroed if and only if a Pawn is pushed or a capture is made. For each position that is represented, 'DTZ' indicates the theoretical value, and the number of winner's moves to the goal of 'Win and ply-count zeroed' if won/lost - assuming that the winner is minimizing and the loser is maximizing DTZ. DTZ £ DTC £ DTM.

DTZ50

Depth to Zeroing (of the ply count) in the context of the 50-Move Rule The DTC, DTM and DTZ metrics do not consider the current FIDE 50-move rule whereby a game in which no irreversible moves have been played for 100 plies can be claimed as a draw by the player 'on move'. In this metric, in addition to the DTC/DTM/DTZ draws, positions requiring more than 50 winner's moves to zero the ply-count are defined as draws. DTZ £ DTZ50 if DTZ50 ¹ draw. 'DTZ50' is one of a set of 'DTZk' rules: a k-move rule effectively applies if there are only k moves left before a draw-claim might be made. k1 £ k2 implies DTZk2 £ DTZk1 if DTZk1 ¹ draw.

Note that, because depth is measured in winner's moves rather than plies, this metric does not define as draw a position in which 50 winner's moves and 51 loser's moves are required to zero the ply-count, despite the fact that the loser would claim a draw after 100 plies had been played in that endgame.

DTR

Depth by the (k-move) Rule 'The Rule' referred to here is a notional set of k-move rules. For each position that is represented, 'DTR' indicates the theoretical value and, for won/lost positions, the least k for which DTZk is not draw - assuming that the winner is minimising and the loser is maximising DTR. DTZ £ DTR. No DTR EGTs have been created to date [3] .

DTZR

Depth to Zeroing move, give that DTR is being minimaxed If DTR = draw, then DTZR = draw. Otherwise, Otherwise DTRZR indicates the theoretical value, and the number of winner's moves to the zeroing of the ply count, given that the two sides are minimaxing first DTR and then DTZR. DTZR would be used in conjunction with DTR to progress a deep win in the context of a k-move rule because DTR can remain unchanged over a sequence of moves. DTZR £ DTR but it is not always the case that DTZ £ DTZR as may seem intuitively obvious: the loser may zero the move-count to maximise DTR.

Summary

To summarize the different metrics of tablebases, each metric has its strengths and weaknesses. Nalimov's DTM EGTs are widely and commercially available, and used by many chess engines or chess GUIs. DTC EGTs are more easily computed and stored as they involve smaller depth-ranges and are more compressible. For endgames with less or equal than 5 pieces on the board, KNNKP comes closest to requiring more than one Byte per position to store DTM: maxDTM = 115 (1-0) and 73 (0-1) necessitating 190 values in the EGT. For KPPKP, maxDTM = 127 (1-0) but only 42 (0-1). But for certain 6 piece endgames, one Byte is not enough: maxDTM = 262 for a KRNKNN position. The DTC and DTZ metrics increasingly postpone the need for two Bytes per position in an uncompressed EGT, but KRBNKQN has maxDTC = maxDTZ = 517 (0-1), both wtm and btm.

In extremis, he unmoderated use of DTM, DTC or DTZ EGTs will let slip a winnable position in the context of the 50-move rule ... hence the marginal need for the DTR and DTZR metrics, coupled with the ability to recompute DTR/DTZR EGTs in the context of a limited move-budget.

Bitbases

see main article Endgame Bitbases

Inside the search much denser tables with value {won, draw, loss, invalid} or boolean {win, not_win} information are sufficient with respect to bounds. Denser tables are more efficiently used, given that memory and cache are limited resources. Boolean Win/Not_Win Bitbases require only one bit per position (and if necessary, further enquiry if draw is to be distinguished from loss with respect to bounds). Value Bitbases require two bits per position.

Indexing

Every position is assigned to an unique index to specify the location of the information stored about it. There are two main aims when generating the index number. The easier the algorithm to generate the index from any given position, the faster will be the probing of the tablebase as well as the generation of it. But the second aim is to get a relatively small range of index-numbers, to keep the size of the file as small as possible.

The most straight forward way would be to for every piece on the board use 6 bit (1-64 squares)

index = position_white_King + position_black_King * 64

for each piece {
    index = index * 64 + position
}

This can be optimized in several ways. A chess board can be rotated and mirrored (if pawns are on the board only a vertical reflection is possible).

  • Pieces may not stand on the same square.
  • For pieces of the same type, different arrangements can be left away.
  • The side to move may not give check.
  • The distance between the two Kings must be greater than one.

Brief Info

of some popular Endgame tablebases:

Format Metric 1st published 5 men 6 men 7 men
Thompson DTC 1991 2.5 GiB (not completed) - -
Edwards DTM 1994 56 GiB (estimated) - -
Nalimov DTM 1998 7.1 GiB 1.2 TiB -
Scorpio WDL 2005 214 MiB 48.1 GiB -
Gaviota DTM 2008 6.5 GiB - -
Lomonosov DTM 2012 - - 140 TiB
Syzygy WDL + DTZ50 2013 / 2018 939 MiB 150.2 GB 17 TB

Formats

Generators

7-man EGTBs

2005

In 2005, Yakov Konoval started to collaborate with Marc Bourzutschky on constructing 7-man EGTBs. Yakov wrote the generator and Marc a verification program and some utilities for extracting the data. In October 2005, Yakov Konoval and Marc Bourzutschky announced that a position in the ending of a KRRNkrr requires 290 moves to convert to a simpler winning endgame [4] . The old record was 243 moves from a position in a rook and knight versus two knights endgame, discovered by Lewis Stiller in 1991 [5] .

2006

In March 2006, the wizards of 7-men endgames, Marc Bourzutschky and Yakov Konoval found a 330 moves win in KQBNkqb [6] and in May 2006 a 517 moves win in KQNkrbn [7] .

2012

In July 2012, Vladimir Makhnychev and Victor Zakharov from Moscow State University completed 4+3 DTM-tablebases (525 endings including KPPPKPP). The next set of 5+2 DTM-tablebases was completed during August 2012 [8] . The tablebases are named Lomonosov Tablebases, using the Lomonosov Supercomputer.

2013

Convekta Ltd. announced the release of Lomonosov Tablebases. Until December 31, 2013, the tablebases will be available online through ChessOK products [9].

2018

Starting in March 2018, seven piece Syzygy Bases, originally created for up to six pieces by Ronald de Man in 2013, were generated by Bojun Guo, finished in August 2018 [10].

See also

Selected Publications

1965 ...

1970 ...

1975 ...

1985 ...

1986

1987

1988

1989

1990 ...

1991

1992

1993

1994

1995 ...

1996

1997

1999

2000 ...

2001

Guy Haworth (2001). Discarding Like Pieces. 6th Computer Olympiad Workshop
Guy Haworth (2001). Depth by The Rule. 6th Computer Olympiad Workshop
Guy Haworth (2001). 3-5-Man Chess Data. 6th Computer Olympiad Workshop
Guy Haworth (2001). 3-5-Man Mutual Zugzwangs in Chess. 6th Computer Olympiad Workshop

2002

2003

2004

2005 ...

2006

2008

2009

2010 ...

2011

2013

2014

2015 ...

2016

2017

Forum Posts

1995 ...

overlapping tablebase lookup by Jay Scott, CCC, February 09, 1999

2000 ...

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

2005 ...

2010 ...

2011

2012

2013

2014

2015 ...

2016

Re: Nalimov EGTB problem related to DTM? by Ronald de Man, CCC, February 14, 2016
EPD to test EGTB probe code by Sergei S. Markoff, CCC, May 24, 2016

2017

2018

2019

External Links

Compression Schemes for Gaviota Tablebases

ChessBase

ChessOK

Online Lookup

Download

Statistics

References

  1. Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
  2. Ernst A. Heinz (1999). Endgame Databases and Efficient Index Schemes for Chess. ICCA Journal, Vol. 22, No. 1, ps
  3. DTR is no good! by Harm Geert Muller, CCRL Forum, September 24, 2008
  4. Subject: KRRNKRR win in 290: a new record by Marc Bourzutschky from CCC, October 16, 2005
  5. Chess endgame from Wikipedia
  6. 311. 31 March 2006: White plays and wins in 330 moves by Tim Krabbé
  7. OPEN CHESS DIARY 316. 26 May 2006: A 517-move win by Tim Krabbé
  8. Endgame tablebase from Wikipedia - Background
  9. Lomonosov Endgame Tablebases - ChessOK
  10. Re: 7-men Syzygy attempt by Bojun Guo, CCC, August 19, 2018
  11. Subject: brute-force vs. intuition in math & chess by Bill Dubuque, August 1996
  12. Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis
  13. Knowledge discovery from Wikipedia
  14. Kasparov versus the World from Wikipedia
  15. Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
  16. Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
  17. OBDD - Ordered Binary Decision Diagram from Wikipedia
  18. Plakoto from Wikipedia
  19. Endgame tablebases with the fifty-move rule by Galen Huntington
  20. tablebase compression / academic integrity by Ronald de Man, CCC, May 19, 2016
  21. Computing endgames with few men by Urban Koistinen
  22. Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
  23. Computing endgames with few men by Urban Koistinen
  24. Easy mate by Frank Phillips, CCC, September 13, 2003 » Checkmate
  25. A018214 - OEIS | Alkane (or paraffin) numbers
  26. Lomonosov Endgame Tablebases - ChessOK
  27. kervinck/pfkpk · GitHub
  28. Gaviota tablebases, probing code v4 (UPDATE) by Miguel A. Ballicora, CCC, March 11, 2011
  29. EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001
  30. Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001
  31. Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
  32. New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013
  33. Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014
  34. Yet another KPK endgame table generator: pfkpk by Marcel van Kervinck, CCC, September 05, 2015

Up one level