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. A chess table is a table with a chessboard painted or engraved on it. ... A database is a collection of data elements (facts) stored in a computer in a systematic way, such that a computer program can consult it to answer questions. ... In chess, the endgame (or end game or ending) refers to the stage of the game when there are few pieces left on the board. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...
Tablebases are generally limited to 6 pieces on the board and below, because it is currently computationally infeasible to be larger. The 6-piece tablebases factored heavily into the analysis of Kasparov versus The World. In 1999, Garry Kasparov agreed to play a game of chess, via the Internet, against the entire rest of the world in consultation, with the World Team moves to be decided by majority vote. ...
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.) En passant (French: in passing) is a maneuver in the board game of chess. ... Castling is a special move in the game of chess involving the king and either rook. ...
Tablebases are generated by retrograde analysis, working backwards from a checkmated or stalemated position.
Similarly, a tablebase containing a pawn must be able to rely on other tablebases that deal with the new set of material after pawn promotion to a queen or other piece.
Thus a tablebase may identify a position as won or lost, when according to the fifty-move rule it is drawn.
Since the early 1990s, with the availability of oracles for certain combinatorial games, also called tablebases (e.g.
The method used is the full force of Scientific Method: extensive experimentation with the tablebases combined with intensive study of tablebase-answers to well designed problems, combined with knowledge of prior art i.e.
Berlekamp in dots-and-boxes etc. and John Nunn in chessendgames are notable examples of people doing this work, though they were not and are not involved in tablebase generation.
Feeds |
Contact