Nalimov Tablebases

From Chessprogramming wiki
Jump to: navigation, search

Home * Knowledge * Endgame Tablebases * Nalimov Tablebases

Huffman tree [1]

Nalimov Tablebases,
are 3-to-6-man endgame tablebases developed by Eugene Nalimov, providing depth to mate information. First published for up to 5-man in late 1998, 6-man files were released subsequently over the years and 6-man chess was finally solved in 2005 [2]. Nalimov Tablebases apply a more efficient indexing scheme than previous tablebases, and were further compressed into 8 KiB blocks exploiting common subsequences and Huffman coding as contributed by Andrew Kadatch, doing less file I/O which gets replaced by fast on-the-fly decompression [3]. This allows fast probing not only at the root, but during the search inside the tree [4], further utilized by an own LRU cache despite keeping TB files in the page cache by the operating system. For endgames with pawns of both sides, the TBs consider en passant with disjoint index ranges [5].

File Sizes

5-man Nalimov Tablebases are about two times smaller than Edwards' Tablebases when uncompressed, and about eight times smaller than Edwards' when compressed [6].

Men Sum of File sizes
3 62 KiB
4 30 MiB
5 7.1 GiB
6 1.2 TiB

Savings

In CCC, Eugene Nalimov gave a brief summary, how to realize the space savings [7] :

  1. For pawnless ending, one can restrict one piece to a1-d1-d4 triangle (that was done in SJE's generator). But if that piece happens to be on a1-d4 diagonal, one can restrict other piece to 'large' a1-h1-h8 triangle (exploit one more symmetry).
  2. When one places a second piece on the board, one square is occupied already, so there are only 63 possible squares, for third - only 62, etc.
  3. If there are two identical pieces (e.g. as in knnkp), one can order their locations - e.g. force second piece to occupy square with smaller number. Then one has not N*(N-1) total combinations, but N*(N-1)/2
  4. Pawns occupy ranks 2-7. Even if one wants to handle en passant, there are better ways to do that than to reserve entire rank (or two) for possible en passant target
  5. Kings never can be near each other, so there are only 3612 ways to place 2 kings on the empty board (not using symmetries), versus 4096 when using SJE's format
  6. One cannot capture enemy's king, so, if one knows where it's located, there are some forbidden squares for the pieces of the side-to-move.

License

In the late 90s Nalimov Tablebases became defacto standard and were used in many commercial, private and free chess engines and GUI's. A reference implementation by Eugene Nalimov and Robert Hyatt was realized in Crafty, with Tablebases and probing code previously available from Bob Hyatt's site [8]. Probing could easily incorporated into own chess engines, however the license policy requires explicit permission by Eugene Nalimov [9].

See also

Publications

Forum Posts

1998 ...

Re: Nalimov's TBs: one question by Eugene Nalimov, CCC, November 18, 1998
Re: Q: Nalimov EGTB? by Eugene Nalimov, CCC, August 05, 1999
Re: difference betrween nalimov and thompson EGTB by Frederic Friedel, CCC, December 11, 1999

2000 ...

Re: Usage of egtb.cpp in GPL software (Amy, ExChess, ...) by Eugene Nalimov, CCC, December 05, 2000

2005 ...

2010 ...

2015 ...

Re: Nalimov EGTB problem related to DTM? by Ronald de Man, CCC, February 14, 2016

2020 ...

External Links

General

Online Lookup

Download

References

  1. Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". The frequencies and codes of each character are below. Encoding the sentence with this code requires 135 bits, as opposed to 288 bits if 36 characters of 8 bits were used, Huffman coding from Wikipedia
  2. Guy Haworth (2005). 6-Man Chess Solved. ICGA Journal, Vol. 28, No. 3
  3. Re: Compressed Nalimov EGTBs by Robert Hyatt, rgcc, November 18, 2003
  4. Re: Q: Nalimov EGTB? by Eugene Nalimov, CCC, August 05, 1999
  5. Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2001). Space-efficient Indexing of Endgame Tables for Chess. Advances in Computer Games 9, chapter 3. Nalimov’s Index Scheme
  6. Re: Q: Nalimov EGTB? by Eugene Nalimov, CCC, August 05, 1999
  7. Re: Nalimov's TBs: one question by Eugene Nalimov, CCC, November 18, 1998
  8. Index of /hyatt/crafty/TB hosted by Robert Hyatt (Wayback Machine)
  9. To sumarize this by Thomas Mayer, CCC, August 17, 2005

Up one level