Changes

Jump to: navigation, search

Endgame Tablebases

1,716 bytes added, 22:05, 30 November 2021
no edit summary
=Purposes=
When a [[Chess Game|chess game]] goes to the [[Endgame|endgame]] phase, it may complete soon with the result as a draw or a win/loss. Both human/chess engines can finish the endgame by continuing searching, applying some endgame rules. The Even the game can finish in this way but it is not in a perfect way: it takes much time to make movecompute moves, may use more moves than necessary. Sometimes the winning side may lose the change since the rule 50 movesand/or making blunders. Both human and chess engines may miss badly the chances if they don’t know or not good enough about the endgame they are playing.
An EGTB can help to solve this period. It is a kind of a dictionary of all endgame positions which can answer immediately for a given position:
The main advantages of using EGTBs:
* Engines don’t have to search but retrieves data thus they can move instantly* The move is Moves are the perfect oneones, leading the shortest line to win* Engines don’t need to have the knowledge and code about those endgames or just some simple implementations
The main disadvantages of using EGTBs:
=Data=
An EGTB is a set of endgames. Each endgame is a set of records about positions’ information. All involving positions in an endgame must have the same material. Each Typically each position 's record associates with an integer number which informs how far that position is from mating/being mated or converting (depends on the type of its metrics).
Based on values of those integer numbers it can answer directly two questions of the EGTB: 1) for a given position it is a draw or a win/loss position and 2) how far it is from mating/being mated or converting. From those numbersTo answer the 3rd question, the best move of a position can be indirectly calculated as below part mentions: generate all legal moves, make them, probe all new positions, compare probing scores for the highest one and the associated move is the best one.
Theoretically, we can add more information to each position’s record. However, due to large numbers of involving positions, any additional information may make the whole EGTB becomes significantly larger. Thus so far none of popular EGTBs store any extra information for each item and each record their records actually contains that integer contain those integers only.
All records of an endgame are simply organized as two arrays (one array for one side/color). In other words, each item in those arrays is an integer and its index on an array is mapped to a unique position. For a given chess position, we will calculate its index then access its data record/integer via that index without searching.
==Endgame files==
Those arrays of an endgame can be stored in files. Typically each array is stored in one file. However, sometimes they can be combined into one larger file or splitted into more files to easier copy or manage. Those files may be in the form of none compressed or compresseduncompressed forms. If they are compressed, they are typically divided and compressed by small blocks thus they don't need to load and decompress all data to extract just a position.
==In memory==
* [[Ernst A. Heinz]] ('''1999'''). ''Endgame Databases and Efficient Index Schemes for Chess.'' [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]], [http://people.csail.mit.edu/heinz/ps/edb_index.ps.gz ps]
* [[Ernst A. Heinz]] ('''1999'''). ''Knowledgeable Encoding and Querying of Endgame Databases.'' [[ICGA Journal#22_2|ICCA Journal, Vol. 22, No. 2]], [http://people.csail.mit.edu/heinz/ps/know_edb.ps.gz ps]
* [[Christoph Wirth]], [[Jürg Nievergelt]] ('''1999'''). ''Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame.'' [[ICGA Journal#22_2|ICCA Journal, Vol. 22, No. 2]]<ref>[http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=2923 Chris Wirth's endgame tablebases] by [[Denis Mendoza|Denis P. Mendoza]], [[Computer Chess Forums|CCRL Endgame Tablebases]], December 13, 2007 » [[Chessterfield]]</ref>
* [[Eugene Nalimov]], [[Christoph Wirth]], [[Guy Haworth]] ('''1999'''). ''[http://centaur.reading.ac.uk/4564/ KQQKQQ and the Kasparov-World Game]''. [[ICGA Journal#22_4|ICCA Journal, Vol. 22, No. 4]]
* [[Ulrich Thiemonds]] ('''1999'''). ''Ein regelbasiertes Spielprogramm für Schachendspiele''. [https://en.wikipedia.org/wiki/University_of_Bonn University of Bonn], Diplom thesis, [https://www.idb.uni-bonn.de/publications/da/da_thiemonds_1999.pdf pdf] (German)
==2020 ...==
* [[Guy Haworth]] ('''2020'''). ''CEN: Thomas Ströhlein’s Endgame Tables, a 50th Anniversary''. [[ICGA Journal#42_23|ICGA Journal, Vol. 42, Nos. 2-3]]
* [[Rejwana Haque]], [[Ting Han Wei]], [[Martin Müller]] ('''2021'''). ''On the Road to Perfection? Evaluating Leela Chess Zero Against Endgame Tablebases''. [[Advances in Computer Games 17]]
* [[Dave Gomboc]], [[Christian R. Shelton]] ('''2021'''). ''Chess endgame compression via logic minimization''. [[Advances in Computer Games 17]]
=Forum Posts=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4307 EGTB compression] by [[Stef Luijten]], [[Computer Chess Forums|Winboard Forum]], February 10, 2006
* [http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=2759 utility for testing tablebases integrity] by [[Victor Zakharov]], [[Computer Chess Forums|CCRL Discussion Board]], October 24, 2007
* [http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=2923 Chris Wirth's endgame tablebases] by [[Denis Mendoza|Denis P. Mendoza]], [[Computer Chess Forums|CCRL Endgame Tablebases]], December 13, 2007 » [[Chessterfield]]
* [http://www.talkchess.com/forum/viewtopic.php?t=19178 EGTB compression (H. G. Muller tablebase...)] by [[Dann Corbit]], [[CCC]], January 25, 2008
* [http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=3220 Endgame Metrics] by [[Joshua Shriver]], [[Computer Chess Forums|CCRL Discussion Board]], March 04, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=25546 Creating EGTBs] by [[Carey Bloodworth|Carey]], [[CCC]], December 21, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=26184 Other endgame tablebase generators] by [[Denis Mendoza|Denis P. Mendoza]], [[CCC]], January 23, 2009
* [http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=4219 Other endgame tablebase generators] by [[Denis Mendoza|Denis P. Mendoza]], [[Computer Chess Forums|CCRL Endgame Tablebases]], January 28, 2009
==2010 ...==
* [http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=5163 KK partitioning+very cheap compression fit in 8 GB (7-man)] by [[Urban Koistinen]], [[Computer Chess Forums|CCRL Discussion Board]], May 30, 2010
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73481 Using Freeware AI and Dynamically Generated Endgame Tablebases] by Steve Schooler, [[CCC]], March 27, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73598 Almost perfect DTM tablebase] by [[Dann Corbit]], [[CCC]], April 08, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76089 Asynchronous tablebase lookups] by [[Steinar H. Gunderson|Sesse]], [[CCC]], December 17, 2020 <ref>[https://kernel.dk/io_uring.pdf?source=techstories.org io_uring.pdf]</ref>'''2021'''* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76089 Asynchronous tablebase lookups76659 Stalemate Tablebases] by Dries De Clercq, [[Steinar HCCC]], February 21, 2021 » [[Stalemate]]* [http://www.talkchess.com/forum3/viewtopic. Gunderson|Sessephp?f=7&t=77249 knbk DTM] by [[Martin Sedlak]], [[CCC]], December 17May 05, 2020 <ref>2021 » [[KBNK Endgame]], [[#DTM|DTM]]: [httpshttp://kernelwww.talkchess.dkcom/forum3/io_uringviewtopic.pdfphp?sourcef=7&t=77249&start=techstories4 Re: knbk DTM] by [[Harm Geert Muller]], [[CCC]], May 05, 2021 » [[Marcel van Kervinck|Marcel van Kervinck's]] pretty fast kbnk generator* [http://www.talkchess.org io_uringcom/forum3/viewtopic.pdfphp?f=7&t=77899 tablebase neural nets] by [[Robert Pope]], [[CCC]], August 07, 2021 » [[Neural Networks]]</ref>
=External Links=

Navigation menu