Endgame tablebase
Encyclopedia : E : EN : END : Endgame tablebase
In chess, a tablebase is a database containing the win/loss status of every possible position of pieces in the endgame. Such a database acts as an oracle for the remainder of the game, providing perfect play. On the winning side, a tablebase will show how to force a win in the shortest possible way; on the losing side, a tablebase will show how to prolong loss as long as possible. Any position that is not a win or loss is a guaranteed draw (with best play).
Tablebases were generated for six pieces (including both kings) on the board and below. There are some seven pieces already generated - for example KNNNN-KQ (win in 85 moves) http://web.quick.cz/EVCOMP/tablebase.htm#7menfirst. The six-piece tablebases factored heavily into the analysis of Kasparov versus The World.
There are various kinds of tablebase formats widely in use named by author, including Ken Thompson, Steven J. Edwards, Eugene Nalimov tablebases. Most chess programs can use tablebases.
Using tablebases
Some computer chess operators have suggested that endgame tablebases will actually weaken performance strength in chess computers. Because some positions are analyzed as forced wins for one side, the program will avoid the losing side of positions at all costs. However, many endgames are forced wins only with flawless play, where an even slight error would produce a different result. Consequently, most modern engines will play many endgames well enough on their own. A symptom of this problem is that computers may resign too early because they see that they are being forced into a position that is theoretically dead lost (although they may be thirty or more moves away from the end of the game, and most human opponents would find it hard to win in that time).The Nalimov tablebases do not consider the fifty move rule, under which a game where fifty moves pass without a capture or pawn move can be claimed to be a draw by either player. This results in the tablebase returning results such as "Forced mate in 66 moves" in some positions which are actually be drawn in competition because of the fifty move rule.
One reason for this is that if the rules of chess were to be changed once more, giving more time to win such positions, it will not be necessary to regenerate all the tablebases. It is also very easy for the program using the tablebases to notice and take account of this 'feature'. Also, chess problems do not take the fifty-move rule into account.
The Nalimov tablebases, which use state-of-the-art compression techniques, require 7.05 GB of hard disk space for all five-piece endings. The six-piece endings require approximately 1.2 terabyte. Nalimov seven-piece tablebases require more hard drive storage capacity and RAM to operate than will be practical to use for the foreseeable future, but other tablebase formats that are far less resource-hungry are in development.
Since endgame positions are typically very simple, and with the power of desktop computers growing exponentially, most engines can calculate in endgames very effectively, making the usefulness of endgame databases questionable in light of these serious shortcomings.
Algorithm
The basic algorithm for creating a tablebase is relatively simple. Optimization and handling the "stateful" cases of en passant and castling are more complicated. (Castling is usually ignored in a tablebase, because games in practice rarely reach the endgame without a king or rook moving.)Notes
External links
- [Guide to the use of Computer Chess Endgame Tablebases]
- ftp://ftp.cis.uab.edu/pub/hyatt/TB/3-4-5 Hyatt's FTP for 3-4-5 pieces
- [Great Nalimov Tablebase Server]
- [Nalimov Tablebase Server]
- [tablebase with known 6-piece endings]
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.