Changes

Jump to: navigation, search

Nalimov Tablebases

13,326 bytes added, 17:26, 11 May 2018
Created page with "'''Home * Knowledge * Endgame Tablebases * Nalimov Tablebases''' FILE:Huffman tree 2.svg|border|right|thumb|Huffman tree <ref>Huffman tree generated f..."
'''[[Main Page|Home]] * [[Knowledge]] * [[Endgame Tablebases]] * Nalimov Tablebases'''

[[FILE:Huffman tree 2.svg|border|right|thumb|Huffman tree <ref>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, [https://en.wikipedia.org/wiki/Huffman_coding Huffman coding from Wikipedia]</ref> ]]

'''Nalimov Tablebases''',<br/>
are '''3'''-to-'''6'''-man endgame tablebases developed by [[Eugene Nalimov]], providing [[Endgame Tablebases#DTM|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 <ref>[[Guy Haworth]] ('''2005'''). ''[http://centaur.reading.ac.uk/4522/ 6-Man Chess Solved]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]</ref>. Nalimov Tablebases apply a more efficient indexing scheme than previous tablebases, and were further [https://en.wikipedia.org/wiki/Data_compression compressed] into 8 KiB blocks exploiting [https://en.wikipedia.org/wiki/Subsequence#Common_subsequence common subsequences] and [https://en.wikipedia.org/wiki/Huffman_coding Huffman coding] as contributed by [[Andrew Kadatch]], doing less [https://en.wikipedia.org/wiki/Input/output file I/O] which gets replaced by fast on-the-fly decompression <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/3C-KaeDere0/Bru6UFlOO4QJ Re: Compressed Nalimov EGTBs] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], November 18, 2003</ref>. This allows fast probing not only at the [[Root|root]], but during the [[Search|search]] inside the [[Search Tree|tree]] <ref>[https://www.stmintz.com/ccc/index.php?id=63619 Re: Q: Nalimov EGTB?] by [[Eugene Nalimov]], [[CCC]], August 05, 1999</ref>, further utilized by an own [https://en.wikipedia.org/wiki/Cache_algorithms#LRU LRU cache] despite keeping TB files in the [https://en.wikipedia.org/wiki/Page_cache page cache] by the [https://en.wikipedia.org/wiki/Operating_system operating system]. For endgames with pawns of both sides, the TBs consider [[En passant|en passant]] with disjoint index ranges <ref>[[Eugene Nalimov]], [[Guy Haworth]], [[Ernst A. Heinz]] ('''2001'''). ''[http://centaur.reading.ac.uk/4563/ Space-efficient Indexing of Endgame Tables for Chess]''. [[Advances in Computer Games 9]], chapter 3. Nalimov’s Index Scheme</ref>.

=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 <ref>[https://www.stmintz.com/ccc/index.php?id=63619 Re: Q: Nalimov EGTB?] by [[Eugene Nalimov]], [[CCC]], August 05, 1999</ref>.
{| class="wikitable"
|-
! Men
! colspan="2" | Sum of File sizes
|-
! 3
| style="text-align:center;" | 62
| KiB
|-
! 4
| style="text-align:center;" | 30
| MiB
|-
! 5
| style="text-align:center;" | 7.1
| GiB
|-
! 6
| style="text-align:center;" | 1.2
| TiB
|}

=Savings=
In [[CCC]], [[Eugene Nalimov]] gave a brief summary, how to realize the space savings <ref>[https://www.stmintz.com/ccc/index.php?id=33351 Re: Nalimov's TBs: one question] by [[Eugene Nalimov]], [[CCC]], November 18, 1998</ref> :
{| class="wikitable"
|-
|
# For pawnless ending, one can restrict one piece to a1-d1-d4 triangle (that was done in [[Steven Edwards|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).
# 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.
# 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
# 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
# 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
# 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 Engines|commercial]], [[Private Engines|private]] and free chess engines and [[GUI|GUI's]]. A reference implementation by Eugene Nalimov and [[Robert Hyatt]] was realized in [[Crafty]], with Tablebases and probing code available from Bob Hyatt's site <ref>[http://www.cis.uab.edu/hyatt/crafty/TB/ Index of /hyatt/crafty/TB] hosted by [[Robert Hyatt]]</ref>. Probing could easily incorporated into own chess engines, however the license policy requires explicit permission by Eugene Nalimov.

=See also=
* [[Endgame Bitbases|Bitbases]]
* [[Edwards' Tablebases]]
* [[Gaviota Tablebases]]
* [[Lomonosov Tablebases]]
* [[Scorpio Bitbases]]
* [[Syzygy Bases]]
* [[Thompson's Databases]]

=Publications=
* [[Eugene Nalimov]], [[Guy Haworth]], [[Ernst A. Heinz]] ('''2000'''). ''[http://centaur.reading.ac.uk/4562/ Space-Efficient Indexing of Chess Endgame Tables]''. [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]], [http://supertech.lcs.mit.edu/%7Eheinz/ps/NHH_ICGA.ps.gz postscript]
* [[Eugene Nalimov]], [[Guy Haworth]], [[Ernst A. Heinz]] ('''2001'''). ''[http://centaur.reading.ac.uk/4563/ Space-efficient Indexing of Endgame Tables for Chess]''. [[Advances in Computer Games 9]]
* [[Guy Haworth]], [[Peter Karrer]], [[John Tamplin]], [[Christoph Wirth]] ('''2001'''). ''[http://centaur.reading.ac.uk/4581/ 3-5-man chess: Maximals and mzugs]''. [[ICGA Journal#24_4|ICGA Journal, Vol. 24, No. 4]]
* [[Eugène Nalimov]] ('''2002'''). ''Chess Endgame Tablebases''. [[Eugène Nalimov#Lecture|Invited Lecture]], [[7th Computer Olympiad#Workshop|7th Computer Olympiad Workshop]]
* [[Guy Haworth]] ('''2005'''). ''[http://centaur.reading.ac.uk/4522/ 6-Man Chess Solved]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]

=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=25540 Tablebases] by [[Eugene Nalimov]], [[CCC]], August 28, 1998
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/13dce097a251e2a4# Program for new TB by Dr. Eugene Nalimov ?] by [[Michael Diosi]], [[Computer Chess Forums|rgcc]], November 6, 1998
* [https://www.stmintz.com/ccc/index.php?id=33325 Nalimov's TBs: one question] by [[Jouni Uski]], [[CCC]], November 18, 1998
: [https://www.stmintz.com/ccc/index.php?id=33351 Re: Nalimov's TBs: one question] by [[Eugene Nalimov]], [[CCC]], November 18, 1998
* [https://www.stmintz.com/ccc/index.php?id=63581 Q: Nalimov EGTB?] by [[Dennis Breuker]], [[CCC]], August 05, 1999
: [https://www.stmintz.com/ccc/index.php?id=63619 Re: Q: Nalimov EGTB?] by [[Eugene Nalimov]], [[CCC]], August 05, 1999
* [https://www.stmintz.com/ccc/index.php?id=63720 Nalimov TB caching ?] by [[Ulrich Türke]] from [[CCC]], August 06, 1999
* [https://www.stmintz.com/ccc/index.php?id=67203 EGTBs] by [[Frank Phillips]], [[CCC]], September 03, 1999
* [https://www.stmintz.com/ccc/index.php?id=81835 difference betrween nalimov and thompson EGTB] by [[Rajen Gupta]], [[CCC]], December 10, 1999
: [https://www.stmintz.com/ccc/index.php?id=81932 Re: difference betrween nalimov and thompson EGTB] by [[Frederic Friedel]], [[CCC]], December 11, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=90672 Nalimov-EGTBs in ANSI-C?] by [[Heiner Marxen]], [[CCC]], January 21, 2000
* [https://www.stmintz.com/ccc/index.php?id=155187 Nalimov endgames] by [[Jean-Christophe Weill]], [[CCC]], February 20, 2001
* [https://www.stmintz.com/ccc/index.php?id=192968 Nalimov's EGTBs (long post with code)] by [[Heiner Marxen]], [[CCC]], October 13, 2001
* [https://www.stmintz.com/ccc/index.php?id=196952 Nalimov TB question] by [[Bas Hamstra]], [[CCC]], November 11, 2001
* [https://www.stmintz.com/ccc/index.php?id=270531 Questions about the new Nalimov tablebase files...] by [[Dann Corbit]], [[CCC]], December 12, 2002
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/dc2f8a69e0deaded# Compressed Nalimov EGTBs] by Leonardo Ljubicic, [[Computer Chess Forums|rgcc]], November 18, 2003
* [https://www.stmintz.com/ccc/index.php?id=364329 Bug/glitch in Nalimov Code (and in Wilhelm)?] by [[Dieter Bürssner]], [[CCC]], May 09, 2004
* [https://www.stmintz.com/ccc/index.php?id=369041 To Eugene Nalimov: Copyright of Tablebase files] by [[Karl-Heinz Milaster]], [[CCC]], June 05, 2004
* [https://www.stmintz.com/ccc/index.php?id=369294 Are nalimov EGTB's a copyright from chessbase?] by [[Vincent Diepeveen]], [[CCC]], June 07, 2004
* [https://www.stmintz.com/ccc/index.php?id=393219 Enpassant in Nalimov] by Henry Hongdoyo, [[CCC]], October 25, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=407134 Subject: Problem (small bug?) with Nalimov TBs] by [[Dieter Bürssner]], [[CCC]], January 23, 2005
* [https://www.stmintz.com/ccc/index.php?id=470947 For Eugene Nalimov: EGTB Request] by [[Vasik Rajlich]], [[CCC]], December 16, 2005
* [https://www.stmintz.com/ccc/index.php?id=488972 smp and nalimov egtb, how to make it work?] by [[Volker Böhm]], [[CCC]], February 23, 2006
* [https://www.stmintz.com/ccc/index.php?id=489022 Chessbase releases 9 dvds on Nalimov 6-piece database 43 gb] by Daneil Johnson, [[CCC]], February 23, 2006
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=19 Nalimov access] with [[Vasik Rajlich]], [[Computer Chess Forums|Rybka Forum]], January 9, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=14841 Nalimov Tablebases] by Terry Giles, [[CCC]], July 02, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=24476 Nalimov EGTB] by cyberfish, [[CCC]], October 19, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=29745 6-men (64 bit) Nalimov EGTB generator] by [[Gian-Carlo Pascutto]], [[CCC]], September 13, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=31112 Nalimov EGTB probes skeleton code] by [[Joshua Shriver]], [[CCC]], December 17, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=32987 Nalimov and memory for indexes (are you aware?)] by [[Miguel A. Ballicora]], [[CCC]], March 01, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=33726 Question for Nalimov experts] by [[Mincho Georgiev]], [[CCC]], April 10, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=36886 Gaviota EGTB in Houdini 1.5 + contacting Eugene Nalimov] by [[Robert Houdart]], [[CCC]], December 01, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=46857 Nalimov 6 men ...] by [[Michael Diosi]], [[CCC]], January 12, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48084 Nalimov] by [[Sune Larsson]], [[CCC]], May 22, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=59237 Nalimov EGTB problem related to DTM?] by [[Kai Laskos]], [[CCC]], February 14, 2016 » [[Endgame Tablebases#DTM|DTM]]
: [http://www.talkchess.com/forum/viewtopic.php?t=59237&start=7 Re: Nalimov EGTB problem related to DTM?] by [[Ronald de Man]], [[CCC]], February 14, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60195 Nalimov egtb probing code] by [[Fabio Gobbato]], [[CCC]], May 16, 2016

=External Links=
==General==
* [http://www.ajedrez-de-estilo.com.ar/int/Products/engines/tb/ Tablebases] by [[Eugene Nalimov]]
* [http://www.playwitharena.com/?User_Files%2C_Engines:Axon%2C_EloStat%2C_Nalimov:Nalimov_Tablebases Nalimov Tablebases] from [[Arena|Arena Chess GUI]]
* [http://archive.today/HFYs Eugene Nalimov: Winner of the ChessBase Award and Guest of Honor in Maastricht] by [[Eric van Reem]], [[ChessBase]] events, July 9, 2002 (archived)
* [http://www.mathematik.uni-stuttgart.de/~thiel/misc/endgames/ Theoretical statistics for chess endgames with up to five pieces] by [[Mathematician#UlrichThiel|Ulrich Thiel]]
* [http://en.chessbase.com/post/engines-and-endgame-tablebases Engines and endgame tablebases] by [[Albert Silver]], [[ChessBase|ChessBase News]], December 12, 2013
==Online Lookup==
* [http://chessok.com/?page_id=361 Endgame Nalimov Tablebases Online] - [[ChessOk]]
* [http://www.gmchess.com/endgames/ Nalimov EGTB] from [http://www.gmchess.com/index.html GMchess.com]
* [http://www.lokasoft.nl/tbweb.htm Nalimov Tablebase server (DTM)] by [[Lokasoft]]
* [http://www.k4it.de/index.php?lang=en&topic=egtb Web Query for Nalimov Endgame Tablebases] from [http://www.k4it.de/index.php?topic=impressum&lang=en Knowledge4IT] by [[Eiko Bleicher]]
==Download==
* [http://www.cis.uab.edu/hyatt/crafty/TB/ Index of /hyatt/crafty/TB] hosted by [[Robert Hyatt]]
* [http://kirill-kryukov.com/chess/tablebases-online/ Endgame Tablebases Online - 6-men endgame analysis free for everyone] by [[Kirill Kryukov]] (3,4,5,6 pieces - via [https://en.wikipedia.org/wiki/EMule emule])
* [http://tablebase.sesse.net/ tablebase.sesse.net] by [[Steinar H. Gunderson|Sesse]]

=References=
<references />

'''[[Endgame Tablebases|Up one level]]'''

Navigation menu