25,161
edits
Changes
no edit summary
'''Endgame Tablebases''', (EGTBs or EGTs)<br/>
precalculated [[Endgame|endgame]] [https://en.wikipedia.org/wiki/Table_%28database%29 tables] generated by an exhaustive [[Retrograde Analysis|retrograde analysis]]. During its [[Chess Game|game play]] and/or [[Search|search]], [[Interior Node Recognizer|recognizing]] a specific [[Material|material composition]], a chess program can probe, or in principle compute these tables to determine the outcome of positions definitively and act as an [[Oracle|oracle]] providing the optimal moves. The tables are usually divided into separate [https://en.wikipedia.org/wiki/Computer_file files] for each material configuration and [[Side to move|side to move]]. What all different [[Endgame Tablebases#Formats|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 EGTB but typically are not.
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> .
=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 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.
EGTB can help to solve this period. It is a kind of dictionary of all endgame positions which can answer directly or indirectly for a given position:
* it is a draw or a win/loss
* how far/how many move from matting/being mated
* what is the best move
The main advantages of using EGTBs:
* It does not search but retrieves data thus it can move instantly
* The move is the perfect one, leading the shortest line to win
The main disadvantages of using EGTBs:
* Data too large for downloading and storing
* If use when searching, it may slow down the search
* Require a complicated code for probing
=Data=
An EGTB is a set of endgames. Each endgame is a set of positions (they must have the same material). Each position 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). All numbers of an endgame are simply organized as two arrays of integers (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.
Based on values those integer numbers can answer directly two purposes 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 item. However, due to large involving positions, any additional information may make the whole EGTB becomes significantly larger. None of the popular EGTBs store any extra information for each item.
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 file or device into more files to be easy to copy or manage. Those files may be in the form of none or compressed. If they are compressed, they are divided and compressed by small blocks thus they don't need to decompress all to extract data of just a few positions.
The size of an endgame depends on:
* The number of involving pieces: more pieces, the bigger size
* Type of pieces: for standard chess, more Pawns is the smaller size
* Type of metric
* The largest value: the integer number should be large enough to cover the largest value. Different endgames will have different largest values. Thus some endgames need only one byte per item but some need 2 bytes
* Indexing: The algorithms to map between an array item and a position
* Compress ratio
So far the size of an EGTB is the most important factor of success.
=Metrics=
* The side to move may not give check.
* The distance between the two Kings must be greater than one.
=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 and has below steps:
* convert a given chess position into an index via indexing algorithms
* access data (typically organized as an integer array) 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 block index
* Read data of that block from storage into memory
* Uncompress the block (if it is compressed)
* Convert the endgame index into block index and retrieve the right data
==Search==
After probing the chess engine may have the result as an integer number for the queried position. Depending on the metric, the number may be a distance to mate or distance to conversion, the position is a draw or a win or loss for the querying side. Sometimes that value (state of draw/win/loss) may be enough for searching. However, sometimes that state is not enough and it needs to know which is the best move to make. The solution is to generate all legal moves from that position, make one by one, probe that EGTB for values of each new position. After all, compare the values of all children's positions to find which one is the best to make.
==Speed==
Typically the probe process requires some computing and it may access storage 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 search be slower. The good point is that the engine can stop searching on the branch probed the EGTB.
=Brief Info=
* [[Guy Haworth]] ('''2017'''). ''Chess Endgame News''. [[ICGA Journal#39_2|ICGA Journal, Vol. 39, No. 2]]
* [[Hung-Jui Chang]], [[Gang-Yu Fan]], [[Jr-Chang Chen]], [[Chih-Wen Hsueh]], [[Tsan-sheng Hsu]] ('''2017'''). ''[https://link.springer.com/chapter/10.1007/978-3-319-75931-9_10 Validating and Fine-Tuning of Game Evaluation Functions Using Endgame Databases]''. [[Conferences#IJCAI2017|CGW@IJCAI 2017]]
'''2018'''
* [[Hung-Jui Chang]], [[Jr-Chang Chen]], [[Gang-Yu Fan]], [[Chih-Wen Hsueh]], [[Tsan-sheng Hsu]] ('''2018'''). ''Using Chinese dark chess endgame databases to validate and fine-tune game evaluation functions''. [[ICGA Journal#40_2|ICGA Journal, Vol. 40, No. 2]] » [[Chinese Dark Chess]]
'''2019'''
* [[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]]
=Forum Posts=
* [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://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=6&t=3934 DTR is no good!] by [[Harm Geert Muller]], [[Computer Chess Forums|CCRL Discussion Board]], September 24, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=25311 Gaviota's Endgame Tablebases] by [[Miguel A. Ballicora]], [[CCC]], December 07, 2008 » [[Gaviota Tablebases]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50962 On-demand tablebase generation] by [[Evert Glebbeek]], [[CCC]], January 19, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=51847 Endgame tablebase generation for newbies] by [[Alberto Sanjuan]], [[CCC]], April 04, 2014
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=51883 Reducing tablebase size with search] by [[Russell Reagan]], [[CCC]], April 07, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53244 A different tablebase encoding format] by [[Steven Edwards]], [[CCC]], August 10, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54064 Tablebase access using a Solid State Disk] by [[Steven Edwards]], [[CCC]], October 16, 2014 » [[Memory]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69447 Generate EGTB with graphics cards?] by [[Pham Hong Nguyen|Nguyen Pham]], [[CCC]], January 01, 2019 » [[GPU]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=72158 longest 6-man EGTB win] by Zenmastur, [[CCC]], October 24, 2019
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73332 Retrograde analysis - TBs move sequences to checkmate] by Hedinn Steingrimsson, [[CCC]], March 12, 2020
* [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
=External Links=
* [[ICGA#Topics]]: [httphttps://ilkicga.uvt.nlorg/icga/games/chess/endgames.php Chess Endgames] , [[ICGA]] site compiled by [[Guy Haworth]] and colleagues
* [https://en.wikipedia.org/wiki/Endgame_tablebase Endgame tablebase from Wikipedia]
* [http://computer-chess.org/doku.php?id=computer_chess:wiki:lists:egtbs_list Endgame Tablebases and Bitbases List] from [http://computer-chess.org/doku.php?id=home Computer-Chess Wiki] by [[Ron Murawski]]
* [http://www.horizonchess.com/FAQ/Winboard/weaktablebase.html Can use of endgame tablebases weaken play?] from [http://www.horizonchess.com/FAQ/Winboard/index.html FAQ on Winboard and Chess Engines] by [[Aaron Tay]]
* [http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/ Can We Solve Chess One Day? | Gödel's Lost Letter and P=NP] by [[Mathematician#RJLipton|Dick Lipton]], May 12, 2010
* [https://pluslevelup.googlegitconnected.com/100454521496393505718/posts 7build-your-own-chess-endgame-monster-a3fb23bb3ec1 Build Your Own Chess Endgame Monster -man TBLevel Up Coding] - by [[https://en.wikipedia.org/wiki/Google%2B Google+Don Cross]], February 17, 2020 ==GitHub==
* [https://github.com/syzygy1/tb syzygy1/tb · GitHub] by [[Ronald de Man]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681 New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 01, 2013</ref>
* [https://github.com/dshawul/Scorpio dshawul/Scorpio · GitHub] includes Six men egbb code » [[Scorpio Bitbases]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=50894 Scorpio 6men EGBB Now available] by [[Joshua Shriver]], [[CCC]], January 14, 2014</ref>
* [https://github.com/kervinck/pfkpk kervinck/pfkpk · GitHub] » [[KPK]] [[Endgame Bitbases|Bitbase]] by [[Marcel van Kervinck]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57517 Yet another KPK endgame table generator: pfkpk] by [[Marcel van Kervinck]], [[CCC]], September 05, 2015</ref>
* [https://github.com/cosinekitty/endgame GitHub - cosinekitty/endgame: Chess endgame database generator] by [[Don Cross]]
==[[ChessBase]]==
