HOME

TheInfoList



OR:

An endgame tablebase is a computerized
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
that contains precalculated exhaustive analysis of
chess endgame In chess and other similar games, the endgame (or end game or ending) is the stage of the game when few pieces are left on the board. The line between middlegame and endgame is often not clear, and may occur gradually or with the quick exchange o ...
positions. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysing a game that has already been played. The tablebase contains the game-theoretical value (win, loss, or
draw Draw, drawing, draws, or drawn may refer to: Common uses * Draw (terrain), a terrain feature formed by two parallel ridges or spurs with low ground in between them * Drawing (manufacturing), a process where metal, glass, or plastic or anything ...
) in each possible position, and how many moves it would take to achieve that result with
perfect play A solved game is a game whose outcome (win, lose or draw) can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full informa ...
. Thus, the tablebase acts as an
oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The word '' ...
, always providing the optimal moves. Typically the database records each possible position with certain pieces remaining on the board, and the best moves with
White White is the lightest color and is achromatic (having no hue). It is the color of objects such as snow, chalk, and milk, and is the opposite of black. White objects fully reflect and scatter all the visible wavelengths of light. White on ...
to move and with
Black Black is a color which results from the absence or complete absorption of visible light. It is an achromatic color, without hue, like white and grey. It is often used symbolically or figuratively to represent darkness. Black and white have o ...
to move. Tablebases are generated by
retrograde analysis In chess problems, retrograde analysis is a technique employed to determine which moves were played leading up to a given position. While this technique is rarely needed for solving ordinary chess problems, there is a whole subgenre of chess pr ...
, working backward from a
checkmate Checkmate (often shortened to mate) is any game position in chess and other chess-like games in which a player's king is in check (threatened with ) and there is no possible escape. Checkmating the opponent wins the game. In chess, the king is ...
d position. By 2005, all chess positions with up to six pieces, including the two kings, had been solved. By August 2012, tablebases had solved chess for almost every position with up to seven pieces, but the positions with a lone king versus a king and five pieces were omitted because they were considered to be "rather obvious." These positions were included by August 2018. , work is still underway to solve all eight-piece positions. The solutions have profoundly advanced the chess community's understanding of endgame theory. Some positions which humans had analyzed as draws were proven to be winnable; in some cases the tablebase analysis could find a mate in more than five hundred moves, far beyond the
horizon The horizon is the apparent line that separates the surface of a celestial body from its sky when viewed from the perspective of an observer on or near the surface of the relevant body. This line divides all viewing directions based on whether i ...
of humans, and beyond the capability of a computer during play. For this reason, tablebases also called into question the 50-move rule, since many positions are now seen to exist that would be a win for one side but are drawn because of the 50-move rule; initially, as individual cases were found, exceptions to the rule were introduced, but when more extreme cases were later discovered, the exceptions were removed. Tablebases provide a powerful analytical tool, enhancing competitive play and facilitating the composition of
endgame studies In the game of chess, an endgame study, or just study, is a composed position—that is, one that has been made up rather than played in an actual game—presented as a sort of puzzle, in which the aim of the solver is to find the essentially uniqu ...
. While endgame tablebases exist for other board games, such as
checkers Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...
,
nine men's morris Nine men's Morris is a strategy board game for two players dating at least to the Roman Empire. The game is also known as nine-man morris, mill, mills, the mill game, merels, merrills, merelles, marelles, morelles, and ninepenny marl in English. ...
, and some
chess variant A chess variant is a game related to, derived from, or inspired by chess. Such variants can differ from chess in many different ways. "International" or "Western" chess itself is one of a family of games which have related origins and could be co ...
s, the term ''endgame tablebase'' is assumed to refer to the chess tablebase by default.


Background

Physical limitations of
computer hardware Computer hardware includes the physical parts of a computer, such as the computer case, case, central processing unit (CPU), Random-access memory, random access memory (RAM), Computer monitor, monitor, Computer mouse, mouse, Computer keyboard, ...
aside, in principle it is possible to solve any game under the condition that the complete state is known and there is no
random chance In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
. Strong solutions, i.e. algorithms that can produce perfect play from any position, are known for some simple games such as
Tic Tac Toe Tic-tac-toe (American English), noughts and crosses ( Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. ...
/Noughts and crosses (draw with perfect play) and
Connect Four Connect Four (also known as Connect 4, Four Up, Plot Four, Find Four, Captain's Mistress, Four in a Row, Drop Four, and Gravitrips in the Soviet Union) is a two-player connection board game, in which the players choose a color and then take tur ...
(first player wins). Weak solutions exist for somewhat more complex games, such as
checkers Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...
(with perfect play on both sides the game is known to be a draw, but it is not known for every position created by less-than-perfect play what the perfect next move would be). Other games, such as chess and Go, have not been solved because their
game complexity Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity. Measures of game comple ...
is far too vast for computers to evaluate all possible positions. To reduce the game complexity, researchers have modified these complex games by reducing the size of the board, or the number of pieces, or both.
Computer chess Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
is one of the oldest domains of
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
, having begun in the early 1930s.
Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory". As a 21-year-o ...
proposed formal criteria for evaluating chess moves in 1949. In 1951,
Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
designed a primitive chess-playing program, which assigned values for material and
mobility Mobility may refer to: Social sciences and humanities * Economic mobility, ability of individuals or families to improve their economic status * Geographic mobility, the measure of how populations and goods move over time * Mobilities, a contemp ...
; the program "played" chess based on Turing's manual calculations. However, even as competent chess programs began to develop, they exhibited a glaring weakness in playing the endgame. Programmers added specific
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
s for the endgame – for example, the
king King is the title given to a male monarch in a variety of contexts. The female equivalent is queen, which title is also given to the consort of a king. *In the context of prehistory, antiquity and contemporary indigenous peoples, the tit ...
should move to the center of the board. However, a more comprehensive solution was needed. In 1965,
Richard Bellman Richard Ernest Bellman (August 26, 1920 – March 19, 1984) was an American applied mathematician, who introduced dynamic programming in 1953, and made important contributions in other fields of mathematics, such as biomathematics. He founde ...
proposed the creation of a database to solve chess and
checkers Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...
endgames using
retrograde analysis In chess problems, retrograde analysis is a technique employed to determine which moves were played leading up to a given position. While this technique is rarely needed for solving ordinary chess problems, there is a whole subgenre of chess pr ...
. Instead of analyzing ''forward'' from the position currently on the board, the database would analyze ''backward'' from positions where one player was
checkmate Checkmate (often shortened to mate) is any game position in chess and other chess-like games in which a player's king is in check (threatened with ) and there is no possible escape. Checkmating the opponent wins the game. In chess, the king is ...
d or
stalemate Stalemate is a situation in the game of chess where the player whose turn it is to move is not in check and has no legal move. Stalemate results in a draw. During the endgame, stalemate is a resource that can enable the player with the inferior ...
d. Thus, a chess computer would no longer need to analyze endgame positions during the game because they were solved beforehand. It would no longer make mistakes because the tablebase always played the best possible move. In 1970, Thomas Ströhlein published a doctoral thesis with analysis of the following classes of endgame: , , , , , and . In 1977 Thompson's KQKR database was used in a match versus Grandmaster
Walter Browne Walter Shawn Browne (10 January 1949 – 24 June 2015) was an Australian-born American chess and poker player. Awarded the title Grandmaster by FIDE in 1970, he won the U.S. Chess Championship six times. Early years Browne was born to an Am ...
.
Ken Thompson Kenneth Lane Thompson (born February 4, 1943) is an American pioneer of computer science. Thompson worked at Bell Labs for most of his career where he designed and implemented the original Unix operating system. He also invented the B programmi ...
and others helped extend tablebases to cover all four- and five-piece endgames, including in particular , , and . Lewis Stiller published a thesis with research on some six-piece tablebase endgames in 1991.
John Nunn John Denis Martin Nunn (born 25 April 1955) is an English chess grandmaster, a three-time world champion in chess problem solving, a chess writer and publisher, and a mathematician. He is one of England's strongest chess players and was former ...
foremost data miner of chess endgames, and prolific endgame author and endgame authority. More recent contributors have included the following people: *
Eugene Nalimov Eugene Nalimov (born Евгений Викторович Нали́мов (Yevgeny Viktorovich Nalimov) in 1965 in Novosibirsk, U.S.S.R.) is a chess programmer and former Microsoft employee, currently working for Context Relevant. Starting in 1998 ...
, after whom the popular Nalimov tablebases are named; * Eiko Bleicher, who has adapted the tablebase concept to a program called "Freezer" (see below); * Guy Haworth, an academic at the
University of Reading The University of Reading is a public university in Reading, Berkshire, England. It was founded in 1892 as University College, Reading, a University of Oxford extension college. The institution received the power to grant its own degrees in 192 ...
, who has published extensively in the
ICGA Journal The ''ICGA Journal'' is a quarterly academic journal published by the International Computer Games Association. It was renamed in 2000. Its previous name was the ''ICCA Journal'' of the International Computer Chess Association, which was founded in ...
and elsewhere; * Marc Bourzutschky and Yakov Konoval, who have collaborated to analyze endgames with seven pieces on the board; * Peter Karrer, who constructed a specialized seven-piece tablebase () for the endgame of the
Kasparov versus The World Kasparov versus the World was a game of chess played in 1999 over the Internet. It was a , in which a World Team of thousands decided each move for the black pieces by plurality vote, while Garry Kasparov conducted the white pieces by himself. Mo ...
online match; * Vladimir Makhnychev and Victor Zakharov from Moscow State University, who completed 4+3 DTM-tablebases (525 endings including KPPPKPP) in July 2012. The tablebases are named Lomonosov tablebases. The next set of 5+2 DTM-tablebases (350 endings including KPPPPKP) was completed during August 2012. The high speed of generating the tablebases was because of using a
supercomputer A supercomputer is a computer with a high level of performance as compared to a general-purpose computer. The performance of a supercomputer is commonly measured in floating-point operations per second ( FLOPS) instead of million instructions ...
named Lomonosov
top500
. The size of all tablebases up to seven-man is about 140 TB. Later on, Syzygy tablebase managed to reduce that to 18.4 TB. The tablebases of all endgames with up to seven pieces are available for free download, and may also be queried using web interfaces (see the external links below). Nalimov tablebase requires more than one
terabyte The byte is a units of information, unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character (computing), character of text in a computer and for this ...
of storage space.


Generating tablebases


Metrics: Depth to conversion and depth to mate

Before creating a tablebase, a programmer must choose a
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathem ...
of optimality – in other words, they must define at what point a player has "won" the game. Every position can be defined by its distance (i.e. the number of moves) from the desired endpoint. Two metrics are generally used: * Depth to mate (DTM). A checkmate is the only way to win a game. * Depth to conversion (DTC). The stronger side can also win by capturing material, thus converting to a simpler endgame. For example, in KQKR, conversion occurs when White captures the Black rook. Haworth has discussed two other metrics, namely "depth to zeroing-move" (DTZ) and "depth by the rule" (DTR). A zeroing-move is a move which resets the move count to zero under the fifty-move rule, i.e. mate, a capture, or a pawn move. These metrics support the
fifty-move rule The fifty-move rule in chess states that a player can claim a draw if no has been made and no pawn has been moved in the last fifty moves (for this purpose a "move" consists of a player completing a turn followed by the opponent completing a tur ...
, but DTR tablebases have not yet been computed. 7-man DTZ tablebases were made publicly available in August 2018. The difference between DTC and DTM can be understood by analyzing the diagram at right. How White should proceed depends on which metric is used. According to the DTC metric, White should capture the rook because that leads immediately to a position which will certainly win (DTC = 1), but it will take two more moves actually to checkmate (DTM = 3). In contrast according to the DTM metric, White mates in two moves, so DTM = DTC = 2. This difference is typical of many endgames. Usually DTC is smaller than DTM, but the DTM metric leads to the quickest checkmate. Exceptions occur where the weaker side has only a king, and in the unusual endgame of two knights versus one pawn; then DTC = DTM because either there is no defending material to capture or capturing the material does no good. (Indeed, capturing the defending pawn in the latter endgame results in a draw, unless it results in immediate mate.)


Step 1: Generating all possible positions

Once a metric is chosen, the first step is to generate all the positions with a given material. For example, to generate a DTM tablebase for the endgame of king and queen versus king (KQK), the computer must describe approximately 40,000 unique legal positions. Levy and Newborn explain that the number 40,000 derives from a
symmetry Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
argument. The Black king can be placed on any of ten squares: a1, b1, c1, d1, b2, c2, d2, c3, d3, and d4 (see diagram). On any other square, its position can be considered equivalent by symmetry of rotation or reflection. Thus, there is no difference whether a Black king in a corner resides on a1, a8, h8, or h1. Multiply this number of 10 by at most 60 (legal remaining) squares for placing the White king and then by at most 62 squares for the White queen. The product 10×60×62 = 37,200. Several hundred of these positions are illegal, impossible, or symmetrical reflections of each other, so the actual number is somewhat smaller. For each position, the tablebase evaluates the situation separately for White-to-move and Black-to-move. Assuming that White has the queen, almost all the positions are White wins, with checkmate forced in no more than ten moves. Some positions are draws because of
stalemate Stalemate is a situation in the game of chess where the player whose turn it is to move is not in check and has no legal move. Stalemate results in a draw. During the endgame, stalemate is a resource that can enable the player with the inferior ...
or the unavoidable loss of the queen. Each additional piece added to a pawnless endgame multiplies the number of unique positions by about a factor of sixty which is the approximate number of squares not already occupied by other pieces. Endgames with one or more pawns increase the complexity because the symmetry argument is reduced. Since pawns can move forward but not sideways, rotation and vertical reflection of the board produces a fundamental change in the nature of the position. The best calculation of symmetry is achieved by limiting one pawn to 24 squares in the rectangle a2-a7-d7-d2. All other pieces and pawns may be located in any of the 64 squares with respect to the pawn. Thus, an endgame with pawns has a complexity of 24/10 = 2.4 times a pawnless endgame with the same number of pieces.


Step 2: Evaluating positions using retrograde analysis

Tim Krabbé Tim Krabbé (born 13 April 1943) is a Dutch journalist, novelist and chess player. Krabbé was born in Amsterdam. His writing has appeared in most major periodicals in the Netherlands. Once a competitive cyclist, he is known to Dutch readers for ...
explains the process of generating a tablebase as follows:
"The idea is that a database is made with all possible positions with a given material ote: as in the preceding section Then a subdatabase is made of all positions where Black is mated. Then one where White can give mate. Then one where Black cannot stop White giving mate next move. Then one where White can always reach a position where Black cannot stop him from giving mate next move. And so on, always a ply further away from mate until all positions that are thus connected to mate have been found. Then all of these positions are linked back to mate by the shortest path through the database. That means that, apart from 'equi-optimal' moves, all the moves in such a path are perfect: White's move always leads to the quickest mate, Black's move always leads to the slowest mate."
The
retrograde analysis In chess problems, retrograde analysis is a technique employed to determine which moves were played leading up to a given position. While this technique is rarely needed for solving ordinary chess problems, there is a whole subgenre of chess pr ...
is only necessary from the
checkmate Checkmate (often shortened to mate) is any game position in chess and other chess-like games in which a player's king is in check (threatened with ) and there is no possible escape. Checkmating the opponent wins the game. In chess, the king is ...
d positions, because every position that cannot be reached by moving backward from a checkmated position must be a draw. Figure 1 illustrates the idea of retrograde analysis. White can force mate in two moves by playing 1. Kc6, leading to the position in Figure 2. There are only two legal moves for black from this position, both of which lead to checkmate: if 1...Kb8 2. Qb7#, and if 1...Kd8 2. Qd7# (Figure 3). Figure 3, before White's second move, is defined as "mate in one
ply Ply, Pli, Plies or Plying may refer to: Common uses * Ply (layer), typically of paper or wood ** Plywood, made of layers of wood ** Tire ply, a layer of cords embedded in the rubber of a tire Places * Plymouth railway station, England, station ...
." Figure 2, after White's first move, is "mate in two ply," regardless of how Black plays. Finally, the initial position in Figure 1 is "mate in three ply" (i.e., two moves) because it leads directly to Figure 2, which is already defined as "mate in two ply." This process, which links a current position to another position that could have existed one ply earlier, can continue indefinitely. Each position is evaluated as a win or loss in a certain number of moves. At the end of the retrograde analysis, positions which are not designated as wins or losses are necessarily draws.


Step 3: Verification

After the tablebase has been generated, and every position has been evaluated, the result must be verified independently. The purpose is to check the self-consistency of the tablebase results. For example, in Figure 1 above, the verification program sees the evaluation "mate in three ply (Kc6)." It then looks at the position in Figure 2, ''after'' Kc6, and sees the evaluation "mate in two ply." These two evaluations are consistent with each other. If the evaluation of Figure 2 were anything else, it would be inconsistent with Figure 1, so the tablebase would need to be corrected.


Captures, pawn promotion, and special moves

A four-piece tablebase must rely on three-piece tablebases that could result if one piece is captured. 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 In chess, promotion is the replacement of a pawn with a new piece when the pawn is moved to its last . The player replaces the pawn immediately with a queen, rook, bishop, or knight of the same . The new piece does not have to be a previously ca ...
to a queen or other piece. The retrograde analysis program must account for the possibility of a capture or pawn promotion on the previous move. Tablebases assume that
castling Castling is a move in chess. It consists of moving the king two squares toward a rook on the same and then moving the rook to the square that the king passed over. Castling is permitted only if neither the king nor the rook has previously moved ...
is not possible for two reasons. First, in practical endgames, this assumption is almost always correct. (However, castling is allowed by convention in composed problems and studies.) Second, if the king and rook are on their original squares, castling may or may not be allowed. Because of this ambiguity, it would be necessary to make separate evaluations for states in which castling is or is not possible. The same ambiguity exists for the ''
en passant ''En passant'' (, "in passing") is a method of capturing in chess that occurs when a pawn captures a horizontally adjacent enemy pawn that has just made an initial two-square advance. The capturing pawn moves to the square that the enemy paw ...
'' capture, since the possibility of ''en passant'' depends on the opponent's previous move. However, practical applications of ''en passant'' occur frequently in pawn endgames, so tablebases account for the possibility of ''en passant'' for positions where both sides have at least one pawn.


Using ''a priori'' information

According to the method described above, the tablebase must allow the possibility that a given piece might occupy any of the 64 squares. In some positions, it is possible to restrict the search space without affecting the result. This saves computational resources and enables searches which would otherwise be impossible. An early analysis of this type was published in 1987, in the endgame , where the Black bishop moves on the dark squares (see example position at right). In this position, we can make the following ''
a priori ("from the earlier") and ("from the later") are Latin phrases used in philosophy to distinguish types of knowledge, justification, or argument by their reliance on empirical evidence or experience. knowledge is independent from current ...
'' assumptions: # If a piece is captured, we can look up the resulting position in the corresponding tablebase with five pieces. For example, if the Black pawn is captured, look up the newly created position in KRPKB. # The White pawn stays on a2; capture moves are handled by the 1st rule. # The Black pawn stays on a3; capture moves are handled by the 1st rule. The result of this simplification is that, instead of searching for 48 * 47 = 2,256 permutations for the pawns' locations, there is only one permutation. Reducing the search space by a factor of 2,256 facilitates a much quicker calculation. Bleicher has designed a commercial program called "Freezer," which allows users to build new tablebases from existing Nalimov tablebases with ''a priori'' information. The program could produce a tablebase for positions with seven or more pieces with blocked pawns, even before tablebases for seven pieces became available.


Applications


Correspondence chess

In
correspondence chess Correspondence chess is chess played by various forms of long-distance correspondence, traditionally through the postal system. Today it is usually played through a correspondence chess server, a public internet chess forum, or email. Less common ...
, a player may consult a chess computer for assistance, provided that the etiquette of the competition allows this. Some correspondence organizations draw a distinction in their rules between utilizing
chess engine In computer chess, a chess engine is a computer program that analyzes chess or chess variant positions, and generates a move or list of moves that it regards as strongest. A chess engine is usually a back end with a command-line interface wit ...
s which calculate a position in real time and the use of a precomputed
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
stored on a computer. Use of an endgame tablebase might be permitted in a live game even if engine use is forbidden. Players have also used tablebases to analyze endgames from over-the-board play after the game is over. A six-piece tablebase (KQQKQQ) was used to analyze the endgame that occurred in the correspondence game
Kasparov versus The World Kasparov versus the World was a game of chess played in 1999 over the Internet. It was a , in which a World Team of thousands decided each move for the black pieces by plurality vote, while Garry Kasparov conducted the white pieces by himself. Mo ...
. Competitive players need to know that some tablebases ignore the
fifty-move rule The fifty-move rule in chess states that a player can claim a draw if no has been made and no pawn has been moved in the last fifty moves (for this purpose a "move" consists of a player completing a turn followed by the opponent completing a tur ...
. According to that rule, if fifty moves have passed without a capture or a pawn move, either player may claim a draw.
FIDE The International Chess Federation or World Chess Federation, commonly referred to by its French acronym FIDE ( Fédération Internationale des Échecs), is an international organization based in Switzerland that connects the various national c ...
changed the rules several times, starting in 1974, to allow one hundred moves for endgames where fifty moves were insufficient to win. In 1988, FIDE allowed seventy-five moves for KBBKN, KNNKP, KQKBB, KQKNN, KRBKR, and KQPKQ with the pawn on the seventh rank, because tablebases had uncovered positions in these endgames requiring more than fifty moves to win. In 1992, FIDE canceled these exceptions and restored the fifty-move rule to its original standing. Thus a tablebase may identify a position as won or lost, when it is in fact drawn by the fifty-move rule. Such a position is sometimes termed a "cursed win" (where mate can be forced, but it runs afoul of the 50-move rule), or a "blessed loss" from the perspective of the other player. In 2013,
ICCF ICCF may stand for: * International Conference on Cold Fusion, also known as "International Conference on Condensed Matter Nuclear Science" * International Conservation Caucus Foundation * International Correspondence Chess Federation * Internati ...
changed the rules for correspondence chess tournaments starting from 2014; a player may claim a win or draw based on six-man tablebases. In this case the fifty-move rule is not applied, and the number of moves to mate is not taken into consideration. In 2020, this was increased to seven-man tablebases. Haworth has designed a tablebase that produces results consistent with the fifty-move rule. However most tablebases search for the theoretical limits of forced mate, even if it requires several hundred moves.


Computer chess

The knowledge contained in tablebases affords the computer a tremendous advantage in the endgame. Not only can computers play perfectly within an endgame, but they can simplify to a winning tablebase position from a more complicated endgame. For the latter purpose, some programs use "bitbases" which give the game-theoretical value of positions without the number of moves until conversion or mate – that is, they only reveal whether the position is won, lost or draw. Sometimes even this data is compressed and the bitbase reveals only whether a position is won or not, making no difference between a lost and a drawn game. Shredderbases, for example, used by the Shredder program, are a type of bitbase, which fits all 3-, 4- and 5-piece bitbases in 157  MB. This is a mere fraction of the 7.05 GB that the Nalimov tablebases require. Some
computer chess Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
experts have observed practical drawbacks to the use of tablebases. In addition to ignoring the fifty-move rule, a computer in a difficult position might avoid the losing side of a tablebase ending even if the opponent cannot practically win without himself knowing the tablebase. The adverse effect could be a premature resignation, or an inferior line of play that loses with less resistance than a play without tablebase might offer. Another drawback is that tablebases require a lot of
memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
to store the many thousands of positions. The Nalimov tablebases, which use advanced
compression Compression may refer to: Physical science *Compression (physics), size reduction due to forces *Compression member, a structural element such as a column *Compressibility, susceptibility to compression * Gas compression *Compression ratio, of a ...
techniques, require 7.05  GB of hard disk space for all 5-piece endings. The 6-piece endings require approximately 1.2  TB. The 7-piece Lomonosov tablebase requires 140 TB of storage space. Some computers play better overall if their memory is devoted instead to the ordinary search and evaluation function. Modern engines analyze far enough ahead conventionally to handle the elementary endgames without needing tablebases (i.e., without suffering from the
horizon effect The horizon effect, also known as the horizon problem, is a problem in artificial intelligence whereby, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of them, typically ...
). It is only in more complicated endgames that tablebases will have any significant effect on an engine's performance. Syzygy tablebases were developed by Ronald de Man, released in April 2013, in a form optimized for use by a chess program during search. This variety consists of two tables per endgame: a smaller WDL (win/draw/loss) table which contains knowledge of the 50-move rule, and a larger DTZ table (distance to zero ply, i.e., pawn move or capture). The WDL tables were designed to be small enough to fit on a
solid-state drive A solid-state drive (SSD) is a solid-state storage device that uses integrated circuit assemblies to store data persistently, typically using flash memory, and functioning as secondary storage in the hierarchy of computer storage. It is ...
for quick access during search, whereas the DTZ form is for use at the root position to choose the game-theoretically quickest distance to resetting the 50-move rule while retaining a winning position, instead of performing a search. Syzygy tablebases are available for all 6-piece endings, and are now supported by many top engines, including Komodo, Deep Fritz, Houdini, and Stockfish. Since August 2018, all 7-piece Syzygy tables are also available. Current status of the tablebases is summarized in the following table: Research on creating an eight-piece tablebase is ongoing. In 2020, Ronald de Man estimated that 8-man tablebases would be feasible costwise within 5-10 years, as just 2 PB of disk space would store them in Syzygy format, and they could be generated using existing code on a conventional server with 64 TB of RAM. It is assumed that a 1000-move mate in one of the 8-man endgames may be found. During an interview at
Google Google LLC () is an American multinational technology company focusing on search engine technology, online advertising, cloud computing, computer software, quantum computing, e-commerce, artificial intelligence, and consumer electronics. ...
in 2010
Garry Kasparov Garry Kimovich Kasparov (born 13 April 1963) is a Russian chess grandmaster, former World Chess Champion, writer, political activist and commentator. His peak rating of 2851, achieved in 1999, was the highest recorded until being surpassed by ...
said that "maybe" the limit will be 8 pieces. Because the starting position of
chess Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...
is the ultimate endgame with 32 pieces, he claimed that there is no chance that chess can be solved by computers.


Endgame theory

In contexts where the fifty-move rule may be ignored, tablebases have answered longstanding questions about whether certain combinations of material are wins or draws. The following interesting results have emerged: * KBBKN —
Bernhard Horwitz Bernhard Horwitz (1807 in Neustrelitz – 1885 in London) was a German and British chess master, chess writer and chess composer. Horwitz was born in Neustrelitz and went to school in Berlin, where he studied art. From 1837 to 1843, he was part ...
and
Josef Kling Josef Kling (19 March 1811 – 1 December 1876), also found in English-language sources as Joseph Kling, was a German chess master and chess composer. He has been called "a pioneer of the modern style of chess." Although Kling was an expert on e ...
(1851) proposed that Black can draw by entering a defensive
fortress A fortification is a military construction or building designed for the defense of territories in warfare, and is also used to establish rule in a region during peacetime. The term is derived from Latin ''fortis'' ("strong") and ''facere'' ...
, but tablebases demonstrated a general win, with maximum DTC = 66 or 67 and maximum DTM = 78. (Also see
pawnless chess endgame A pawnless chess endgame is a chess endgame in which only a few chess piece, pieces remain, and no pawn (chess), pawns. The basic checkmates are types of pawnless endgames. Endgames without pawns do not occur very often in practice except for the b ...
.) * KNNKP – Maximum DTC = DTM = 115 moves. * KNNNNKQ – The knights win in 62.5 percent of positions, with maximum DTM = 85 moves. * KQRKQR – Despite the equality of material, the player to move wins in 67.74% of positions. The maximum DTC is 92, and the maximum DTM is 117. In both this endgame and KQQKQQ, the first player to ''check'' usually wins. * KRNKNN and KRBKNN — Friedrich Amelung had analyzed these two endgames in the 1900s. KRNKNN and KRBKNN are won for the stronger side in 78% and 95% of the cases, respectively. Stiller's DTC tablebase revealed several lengthy wins in these endgames. The longest win in KRBKNN has a DTC of 223 and a DTM of 238 moves (not shown). Even more interesting is the position at right, where White wins starting with 1. Ke6! Stiller reported the DTC as 243 moves, and the DTM was later found to be 262 moves. For some years, a "mate-in-200" position (first diagram below) held the record for the longest computer-generated forced mate. ( Otto Blathy had composed a "mate in 292 moves" problem in 1889, albeit from an illegal starting position.) In May 2006, Bourzutschky and Konoval discovered a KQNKRBN position with an astonishing DTC of 517 moves. This was more than twice as long as Stiller's maximum, and almost 200 moves beyond the previous record of a 330 DTC for a position of KQBNKQB_1001. Bourzutschky wrote, "This was a big surprise for us and is a great tribute to the complexity of chess." Later, when the Lomonosov 7-piece tablebase was being completed a position was found with a DTM of 546 (third diagram below)."Who wins from this puzzle?"
A chess position with a mate-in-546 answer presented as a puzzle, and discussion.
Among 8-piece endgames, a record DTC of 581 moves has been reported. Many positions are winnable despite seeming to be non-winnable by force at first glance. For example, the position in the middle diagram is a win for Black in 154 moves (the white pawn is captured after around 80 moves). In August 2006, Bourzutschky released preliminary results from his analysis of the following seven-piece endgames: KQQPKQQ, KRRPKRR, and KBBPKNN.


Endgame studies

Since many composed
endgame studies In the game of chess, an endgame study, or just study, is a composed position—that is, one that has been made up rather than played in an actual game—presented as a sort of puzzle, in which the aim of the solver is to find the essentially uniqu ...
deal with positions that exist in tablebases, their soundness can be checked using the tablebases. Some studies have been proved unsound by the tablebases. That can be either because the composer's solution does not work, or else because there is an equally effective alternative that the composer did not consider. Another way tablebases
cook Cook or The Cook may refer to: Food preparation * Cooking, the preparation of food * Cook (domestic worker), a household staff member who prepares food * Cook (professional), an individual who prepares food for consumption in the food industry * ...
studies is a change in the evaluation of an endgame. For instance, the endgame with a queen and bishop versus two rooks was thought to be a draw, but tablebases proved it to be a win for the queen and bishop, so almost all studies based on this endgame are unsound. For example, Erik Pogosyants composed the study at right, with White to play and win. His intended main line was 1. Ne3 Rxh2 2. 0-0-0#! A tablebase discovered that 1. h4 also wins for White in 33 moves, even though Black can capture the pawn (which is not the best move – in case of capturing the pawn black loses in 21 moves, while Kh1-g2 loses in 32 moves). Incidentally, the tablebase does not recognize the composer's solution because it includes castling. While tablebases have cooked some studies, they have assisted in the creation of other studies. Composers can search tablebases for interesting positions, such as
zugzwang Zugzwang (German for "compulsion to move", ) is a situation found in chess and other turn-based games wherein one player is put at a disadvantage because of their obligation to make a move; a player is said to be "in zugzwang" when any legal move ...
, using a method called data mining. For all three- to five-piece endgames and pawnless six-piece endgames, a complete list of mutual zugzwangs has been tabulated and published. There has been some controversy whether to allow endgame studies composed with tablebase assistance into composing tournaments. In 2003, the endgame composer and expert
John Roycroft Arthur John Roycroft (born 25 July 1929, London) is an English chess endgame study composer and author. Chess career In 1959 he was awarded the title International Judge of Chess Compositions. In 1965 he founded '' EG'', the first long-running j ...
summarized the debate:
t only do opinions diverge widely, but they are frequently adhered to strongly, even vehemently: at one extreme is the view that since we can never be certain that a computer has been used it is pointless to attempt a distinction, so we should simply evaluate a 'study' on its content, without reference to its origins; at the other extreme is the view that using a 'mouse' to lift an interesting position from a ready-made computer-generated list is in no sense composing, so we should outlaw every such position.
Roycroft himself agrees with the latter approach. He continues, "One thing alone is clear to us: the distinction between classical composing and computer composing should be preserved for as long as possible: if there is a name associated with a study diagram that name is a claim of authorship."
Mark Dvoretsky Mark Izrailevich Dvoretsky (russian: Марк Изра́илевич Дворе́цкий; December 9, 1947 – September 26, 2016) was a Russian chess trainer, writer, and International Master. Biography Dvoretsky was born in Moscow in 1947. ...
, an
International Master FIDE titles are awarded by the international chess governing body FIDE (''Fédération Internationale des Échecs'') for outstanding performance. The highest such title is Grandmaster (GM). Titles generally require a combination of Elo rating and ...
, chess trainer, and author, took a more permissive stance. He was commenting in 2006 on a study by
Harold van der Heijden Harold van der Heijden is a Dutch composer of chess endgame studies. He was born in Veghel, The Netherlands, on 18 December 1960. By profession, after finishing his PhD in 2009, he is head of the Research and Development laboratory of a veterinary ...
, published in 2001, which reached the position at right after three introductory moves. The drawing move for White is 4. Kb4!! (and not 4. Kb5), based on a mutual zugzwang that may occur three moves later. Dvoretsky comments:
Here, we should touch on one delicate question. I am sure that this unique endgame position was discovered with the help of Thompson’s famous computer database. Is this a 'flaw,' diminishing the composer's achievement?

Yes, the computer database is an instrument, available to anyone nowadays. Out of it, no doubt, we could probably extract yet more unique positions – there are some chess composers who do so regularly. The standard for evaluation here should be the result achieved. Thus: miracles, based upon complex computer analysis rather than on their content of sharp ideas, are probably of interest only to certain aesthetes.


"Play chess with God"

On the
Bell Labs Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...
website,
Ken Thompson Kenneth Lane Thompson (born February 4, 1943) is an American pioneer of computer science. Thompson worked at Bell Labs for most of his career where he designed and implemented the original Unix operating system. He also invented the B programmi ...
once maintained a link to some of his tablebase data. The headline read, "Play chess with God." Regarding Stiller's long wins, Tim Krabbé struck a similar note:
Playing over these moves is an eerie experience. They are not human; a grandmaster does not understand them any better than someone who has learned chess yesterday. The knights jump, the kings orbit, the sun goes down, and every move is the truth. It's like being revealed the Meaning of Life, but it's in Estonian.


Nomenclature

Originally, an endgame tablebase was called an "endgame data base" or "endgame database". This name appeared in both '' EG'' and the ''
ICCA Journal The ''ICGA Journal'' is a quarterly academic journal published by the International Computer Games Association. It was renamed in 2000. Its previous name was the ''ICCA Journal'' of the International Computer Chess Association, which was founded in ...
'' starting in the 1970s, and is sometimes used today. According to Haworth, the ''ICCA Journal'' first used the word "tablebase" in connection with chess endgames in 1995. According to that source, a tablebase contains a complete set of information, but a database might lack some information. Haworth prefers the term "Endgame Table", and has used it in the articles he has authored. Roycroft has used the term "oracle database" throughout his magazine, ''EG''.For example, in Nonetheless, the mainstream chess community has adopted "endgame tablebase" as the most common name.


Books

John Nunn John Denis Martin Nunn (born 25 April 1955) is an English chess grandmaster, a three-time world champion in chess problem solving, a chess writer and publisher, and a mathematician. He is one of England's strongest chess players and was former ...
has written three books based on detailed analysis of endgame tablebases: * * *


Tables


Notes


References

* * *


External links


Guide to the use of Computer Chess Endgame Tablebases by Aaron Tay
* Downloading tablebases *
Torrent site for Gaviota, Scorpio, and Syzygy 3,4,5 and 6-men EGTB's
*
Torrent for Nalimov Tablebases (3+4+5+6) complete
*
Distribution site for tablebases up to six pieces
*
3-4-5 pieces
on Robert Hyatt's FTP site * Querying tablebases on the web *
Web query server for Nalimov tablebases by Eiko Bleicher
(up to six pieces) *
Web query server for Nalimov tablebases at ChessOK
(up to six pieces) *
Web query server for Nalimov tablebases by Lokasoft
(up to six pieces) *
Web query server for Syzygy tablebases by Niklas Fiekas
(up to seven pieces)
Maximal positions
i.e. longest DTM positions for endgames with up to five pieces and some with six pieces, compiled by Kirill Kryukov {{Chess * Chess terminology Computer chess Types of databases