25,161
edits
Changes
no edit summary
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|Ken Thompson's]] earlier [[Thompson's Databases|database]] of positions with the weaker and hence potentially losing side to move only <ref>[[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]</ref> .
=PurposePurposes=When a playing [[Chess Game|chess game ]] goes to the [[Endgame|endgame period]] phase, it may complete soon by 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 game can finish in this way but it is not in a perfect way: it takes much time to make move, use more moves than necessary. Sometimes the winning side may lose the change since the rule 50 moves. 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 directly or indirectly immediately for a given position:* If it is a draw or a win/loss* how How far/how many move from matting/being mated* what What is the best move
The main advantages of using EGTBs:
* It does not Engines don’t have search but retrieves data thus it they can move instantly
* The move is the perfect one, leading the shortest line to win
* Engines don’t need to have the code about those endgames or just some simple implementations
The main disadvantages of using EGTBs:
* Data Their data typically are too large for downloading and storing* They may slow down the search* Require complicated code codes for probing
=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 position 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 those integer numbers can answer directly two questions of the EGTB: for a given position it is a draw or a win/loss position and how far it is from mating/being mated or converting. From those numbers, the best move of a position can be indirectly calculated as below part mentions.
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 actually contains that integer only.
==Sizes==
The size of an endgame depends on:
* The number of involving pieces: more pieces, the bigger size
=Retrieving=
==Probe==
When a chess program (e.g., a chess engine or a chess GUI) works with an EGTB, it needs to retrieve data (integer numbers) for some given chess positions. The process named probe. It is not a search but retrieve data which and has below steps:
* convert a given chess position into an index via indexing algorithms
* access data (typically organized organised as an integer arrayarrays of integers) using the index to retrieve the integer of that chess position
If data of that endgame is not ready in memory, usually the probe process has to do some extra work:
* From data index calculate to the block index
* Read data of that block from storage into memory
* Uncompress the block data (if it is compressed)* Convert the endgame index into block index and retrieve the right needed data
==Search==
==Speed==
Typically the probe process requires some computing and it may access storage and decompress which is usually so slow, compared with one stored in memory. All may make it be a slow one. An engine that probes EGTB when searching may make the whole search be slower. Sometimes the benefit from probing EGTBs maybe not enough to cover the loss of slower search. That’s why the probing should be planned and implemented carefully. EGTB files may have to store in fast storage and/or using some huge systems’ caches. The good point is that the engine can stop searching on the branch probed the EGTB.
=Brief Info=
* [[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]]
* [[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], Diploma Diplom thesis, [httphttps://www.iaiidb.uni-bonn.de/~idbpublications/diplomarbeitenda/thiemonds99.psda_thiemonds_1999.gz zipped pspdf pdf] (German)
* [[Chrilly Donninger]] ('''1999'''). ''Der Fortschritt ist nicht aufzuhalten - Chrilly Donninger über Endspieldatenbanken''. [[Computerschach und Spiele|CSS]] 6/99, [http://www.mustrum.de/chrilly/tbs.pdf pdf] (German)
==2000 ...==
* [[Karsten Müller]], [[Guy Haworth]] ('''2019'''). ''FinalGen revisited: new discoveries''. [[ICGA Journal#41_1|ICGA Journal, Vol. 41, No. 1]] » [[FinalGen]]
* [[Karsten Müller]], [[Guy Haworth]] ('''2019'''). ''Stalemate and ‘DTS’ depth to stalemate endgame tables''. [[ICGA Journal#41_4|ICGA Journal, Vol. 41, No. 4]] » [[Stalemate]]
==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]]
=Forum Posts=
* [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=76659 Stalemate Tablebases] by Dries De Clercq, [[CCC]], February 21, 2021 » [[Stalemate]]
=External Links=
==Online Lookup==
* [https://www.chessdb.cn/queryc_en/ Chess Cloud Database Query Interface] by [[Bojun Guo|noobpwnftw]] [[Syzygy Bases|Syzygy]] DTZ50 probing
* [http://tb7.chessok.com/ Lomonosov - online 7-man tablebases]
* [http://chessok.com/?page_id=361 Endgame Nalimov Tablebases Online] by [[ChessOK]]
