Home * Knowledge * Endgame Tablebases

Endgame Tablebases (EGTBs or EGTs) are precalculated tables generated by an exhaustive retrograde analysis. During its game play and/or search, a chess program can look-up, 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.

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 maximising 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.

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 bord 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.

Formats


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 [1] . The old record was 243 moves from a position in a rook and knight versus two knights endgame, discovered by Lewis Stiller in 1991 [2] .

2006

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

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 [5]. 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 [6].

See also


Selected Publications

1965 ...

1970 ...

1985 ...

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...


Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2012 ...

2014 ...


External Links


Test-Positions


Online Lookup


Download


References

  1. ^ Subject: KRRNKRR win in 290: a new record by Marc Bourzutschky from CCC, October 16, 2005
  2. ^ Chess endgame from Wikipedia
  3. ^ 311. 31 March 2006: White plays and wins in 330 moves by Tim Krabbé
  4. ^ OPEN CHESS DIARY 316. 26 May 2006: A 517-move win by Tim Krabbé
  5. ^ Endgame tablebase from Wikipedia - Background
  6. ^ Lomonosov Endgame Tablebases - ChessOK
  7. ^ Subject: brute-force vs. intuition in math & chess by Bill Dubuque, August 1996
  8. ^ Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis
  9. ^ Knowledge discovery from Wikipedia
  10. ^ Kasparov versus the World from Wikipedia
  11. ^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
  12. ^ Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
  13. ^ OBDD - Ordered Binary Decision Diagram from Wikipedia
  14. ^ Computing endgames with few men by Urban Koistinen
  15. ^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
  16. ^ Computing endgames with few men by Urban Koistinen
  17. ^ Easy mate by Frank Phillips, CCC, September 13, 2003 » Checkmate
  18. ^ syzygy1/tb · GitHub by Ronald de Man
  19. ^ Lomonosov Endgame Tablebases - ChessOK
  20. ^ Gaviota tablebases, probing code v4 (UPDATE) by Miguel A. Ballicora, CCC, March 11, 2011
  21. ^ EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001
  22. ^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001
  23. ^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
  24. ^ New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013
  25. ^ Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014

What links here?


Up one level