Endgame tablebase - AbsoluteAstronomy.com

An endgame tablebase is a computerized database

Database

A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...

that contains precalculated exhaustive analysis of a chess

Chess

Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

endgame position. 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

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

value (win, loss, or draw

Draw (chess)

In chess, a draw is when a game ends in a tie. It is one of the possible outcomes of a game, along with a win for White and a win for Black . Usually, in tournaments a draw is worth a half point to each player, while a win is worth one point to the victor and none to the loser.For the most part,...

) of each possible move in each possible position, and how many moves it would take to achieve that result with perfect play. Thus, the tablebase acts as an oracle

Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...

, always providing the optimal moves. Typically the database records each possible position with certain pieces

Chess piece

Chess pieces or chessmen are the pieces deployed on a chessboard to play the game of chess. The pieces vary in abilities, giving them different values in the game...

remaining on the board, and the best moves with White

White and Black in chess

In chess, the player who moves first is referred to as "White" and the player who moves second is referred to as "Black". Similarly, the pieces that each conducts are called, respectively, "the white pieces" and "the black pieces". The pieces are often not literally white and black, but some...

to move and with Black to move.

Tablebases are generated by retrograde analysis

Retrograde analysis

In chess, retrograde analysis is a computational method used to solve game positions for optimal play by working backward from known outcomes , such as the construction of endgame tablebases. In game theory at large, this method is called backward induction...

, working backwards from a checkmate

Checkmate

Checkmate is a situation in chess in which one player's king is threatened with capture and there is no way to meet that threat. Or, simply put, the king is under direct attack and cannot avoid being captured...

d position. Tablebases have solved chess for every position with six or fewer pieces (including the two kings

King (chess)

In chess, the king is the most important piece. The object of the game is to trap the opponent's king so that its escape is not possible . If a player's king is threatened with capture, it is said to be in check, and the player must remove the threat of capture on the next move. If this cannot be...

). The solutions have profoundly advanced the chess community's understanding of endgame theory. Some positions which humans had analyzed as draws were proved to be winnable; the tablebase analysis could find a mate in more than a hundred moves, far beyond the horizon

Horizon effect

The horizon effect is a problem in artificial intelligence where, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of it, typically a few ply down the game tree...

of humans, and beyond the capability of a computer during play. Tablebases have enhanced competitive play and facilitated the composition of endgame studies. They provide a powerful analytical tool.

Endgame tablebases for other board games like checkers, chess variant

Chess variant

A chess variant is a game related to, derived from or inspired by chess. The difference from chess might include one or more of the following:...

s or Nine Men's Morris

Nine Men's Morris

Nine Men's Morris is an abstract strategy board game for two players that emerged from the Roman Empire. The game is also known as Nine Man Morris, Mill, Mills, Merels, Merelles, and Merrills in English....

exist, but without a specific mention of the game, one is talking about chess.

Background

Physical limitations of computer hardware aside, in principle it is possible to solve any game

Solved game

A solved game is a game whose outcome can be correctly predicted from any position when each side plays optimally. Games which have not been solved are said to be "unsolved"...

under the condition that the complete state is known

Perfect information

In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....

and there is no random chance

Game of chance

A game of chance is a game whose outcome is strongly influenced by some randomizing device, and upon which contestants may or may not wager money or anything of monetary value...

. Strong solutions, i.e. algorithms that can produce perfect play from any position, are known for some simple games such as Tic Tac Toe (draw with perfect play) and Connect Four

Connect Four

Connect Four is a two-player game in which the players first choose a color and then take turns dropping their colored discs from the top into a seven-column, six-row vertically-suspended grid...

(first player wins). Weak solution

Weak solution

In mathematics, a weak solution to an ordinary or partial differential equation is a function for which the derivatives may not all exist but which is nonetheless deemed to satisfy the equation in some precisely defined sense. There are many different definitions of weak solution, appropriate for...

s exist for somewhat more complex games, such as checkers

English draughts

English draughts or checkers , also called American checkers or straight checkers or in Israel damka, is a form of draughts board game. Unlike international draughts, it is played on an eight by eight squared board with twelve pieces on each side...

(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 (from the starting position) and Go, have not been solved because their game complexity

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 complexity:...

is 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

Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...

is one of the oldest domains of artificial intelligence

Artificial intelligence

Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

, having begun in the early 1930s. Claude Shannon proposed formal criteria for evaluating chess moves in 1949. In 1951, Alan Turing

Alan Turing

Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...

designed a primitive chess playing program, which assigned values for material and mobility; 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

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

s for the endgame – for example, the king

King (chess)

should move to the center of the board. However, a more comprehensive solution was needed.

In 1965, Richard Bellman

Richard Bellman

Richard Ernest Bellman was an American applied mathematician, celebrated for his invention of dynamic programming in 1953, and important contributions in other fields of mathematics.-Biography:...

proposed the creation of a database to solve chess and checkers endgames using retrograde analysis

Retrograde analysis

. Instead of analyzing forward from the position currently on the board, the database would analyze backward from positions where one player was checkmate

Checkmate

d or stalemate

Stalemate

Stalemate is a situation in chess where the player whose turn it is to move is not in check but has no legal moves. A stalemate ends the game in a draw. Stalemate is covered in the rules of chess....

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 the KQKR database was used in a match versus Grandmaster Walter Browne, see Computer chess#Using endgame databases.

Ken Thompson 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 1995.

More recent contributors have included the following people:

Eugene Nalimov
Eugene Nalimov
Eugene Nalimov is a chess programmer and former Microsoft employee.Starting in 1998, he wrote a tablebase generator which included many different endgames. He received a ChessBase award at the ChessBase meeting in Maastricht in 2002 for his work.Nalimov has an M.Sc. from Novosibirsk State...

, 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
University of Reading
The University of Reading is a university in the English town of Reading, Berkshire. The University was established in 1892 as University College, Reading and received its Royal Charter in 1926. It is based on several campuses in, and around, the town of Reading.The University has a long tradition...

, who has published extensively in the ICGA Journal
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 1977....

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
Kasparov versus the World was a game of chess played in 1999 over the Internet. Conducting the white pieces, Garry Kasparov faced the rest of the world in consultation, with the World Team moves to be decided by plurality vote. Over 50,000 individuals from more than 75 countries participated in the...

online match.

The tablebases of all endgames with up to six 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

Terabyte

The terabyte is a multiple of the unit byte for digital information. The prefix tera means 1012 in the International System of Units , and therefore 1 terabyte is , or 1 trillion bytes, or 1000 gigabytes. 1 terabyte in binary prefixes is 0.9095 tebibytes, or 931.32 gibibytes...

of storage space.

Metrics: Depth to conversion and depth to mate

Before creating a tablebase, a programmer must choose a metric

Metric (mathematics)

In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...

of optimality – in other words, he 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). These metrics support the fifty-move rule, but DTR tablebases have not yet been computed, and DTZ tablebases have not yet been generally released to the public.

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.

Metric	Play	DTC	DTM
DTC	1. Qxd1 Kc8 2. Qd2 Kb8 3. Qd8 mate	1	3
DTM	1. Qc7+ Ka8 2. Qa7 mate	2	2

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.)

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

Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...

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 not more than ten moves. Some positions are draws because of stalemate

Stalemate

Stalemate is a situation in chess where the player whose turn it is to move is not in check but has no legal moves. A stalemate ends the game in a draw. Stalemate is covered in the rules of chess....

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é is a Dutch journalist and novelist.Krabbé was born in Amsterdam. His writing has appeared in most major periodicals in the Netherlands. He is known to Dutch readers for his novel De Renner , first published in 1978...

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 [note: 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

Retrograde analysis

is only necessary from the checkmate

Checkmate

d positions. Other positions need not be worked from because every position that is not reached from a checkmated position is a draw.

Figure 1 illustrates the idea of retrograde analysis. White mates in two moves with 1. Kc6, leading to the position in Figure 2. Then if 1...Kb8 2. Qb7 mate, and if 1...Kd8 2. Qd7 mate (Figure 3).

Figure 3, before White's second move, is defined as "mate in one ply

Ply (game theory)

In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....

." 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

Consistency

Consistency can refer to:* Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...

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

Promotion (chess)

Promotion is a chess rule describing the transformation of a pawn that reaches its eighth rank into the player's choice of a queen, knight, rook, or bishop of the same color . The new piece replaces the pawn on the same square and is part of the move. Promotion is not limited to pieces that have...

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

Castling is a special move in the game of chess involving the king and either of the original rooks of the same color. It is the only move in chess in which a player moves two pieces at the same time. Castling consists of moving the king two squares towards a rook on the player's first rank, then...

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

Chess problem

A chess problem, also called a chess composition, is a puzzle set by somebody using chess pieces on a chess board, that presents the solver with a particular task to be achieved. For instance, a position might be given with the instruction that White is to move first, and checkmate Black in two...

and studies

Endgame study

An endgame study, or just study, is a composed chess position—that is, one that has been made up rather than one from an actual game—presented as a sort of puzzle, in which the aim of the solver is to find a way for one side to win or draw, as stipulated, against any moves the other side...

.) 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
En passant is a move in the board game of chess . It is a special pawn capture which can occur immediately after a player moves a pawn two squares forward from its starting position, and an enemy pawn could have captured it had it moved only one square forward...

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 assumptions:

1. 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.

2. The White pawn stays on a2; capture moves are handled by the 1st rule.

3. 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 can produce a tablebase for seven-piece positions with blocked pawns, even though seven-piece tablebases are generally not available.

Correspondence chess

In correspondence chess

Correspondence chess

Correspondence chess is chess played by various forms of long-distance correspondence, usually through a correspondence chess server, through email or by the postal system; less common methods which have been employed include fax and homing pigeon...

, a player may consult a chess computer for assistance, provided that the etiquette of the competition allows this. 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

Kasparov versus the World was a game of chess played in 1999 over the Internet. Conducting the white pieces, Garry Kasparov faced the rest of the world in consultation, with the World Team moves to be decided by plurality vote. Over 50,000 individuals from more than 75 countries participated in the...

. Players have also used tablebases to analyze endgames from over-the-board play after the game is over.

Competitive players need to know that tablebases ignore the fifty-move rule. According to that rule, if fifty moves have passed without a capture or a pawn move, either player may claim a draw. FIDE 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.

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 draw game.

However, some computer chess

Computer chess

experts have observed practical drawbacks. 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

Computer memory

In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...

to store the many thousands of positions. The Nalimov tablebases, which use special-purpose compression technique, require 7.05 GB

Gigabyte

The gigabyte is a multiple of the unit byte for digital information storage. The prefix giga means 109 in the International System of Units , therefore 1 gigabyte is...

of hard disk space for all five-piece endings. The six-piece endings require approximately 1.2 terabyte

Terabyte

s. Nalimov seven-piece tablebases require more hard drive storage capacity and RAM to operate than will be practical to use for the foreseeable future. Bitbases, however, take much less space. Shredderbases, for example, used by the Shredder

Shredder (chess)

Shredder is a commercial chess program developed in Germany by Stefan Meyer-Kahlen in 1993. Shredder won the World Microcomputer Chess Championship in 1996 and 2000, the World Computer Chess Championship in 1999 and 2003, the World Computer Speed Chess Championship in 2002, 2003, 2004, 2005, and...

program, compress all three, four and five piece bases into 157 MB

Megabyte

The megabyte is a multiple of the unit byte for digital information storage or transmission with two different values depending on context: bytes generally for computer memory; and one million bytes generally for computer storage. The IEEE Standards Board has decided that "Mega will mean 1 000...

. This is a mere fraction of the 7.05 GB that the Nalimov tablebases require.

Some computers play better overall if their memory is devoted instead to the ordinary search and evaluation function. Modern computers analyze far enough ahead conventionally to handle the elementary endgames without needing tablebases (i.e. without suffering from the horizon effect

Horizon effect

). It is only for more sophisticated positions that the tablebase will improve significantly over the ordinary computer.

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
Bernhard Horwitz was a German English chess master and chess writer.Horwitz was born in Neustrelitz, and went to school in Berlin, where he studied art. From 1837 to 1843, he was part of a group of German chess players known as "The Pleiades".He moved to London in 1845...

and Josef Kling
Josef Kling
Josef Kling was a German chess master and chess composer. In 1851 he wrote Chess Studies with Bernhard Horwitz.-External links:* at Chessgames.com...

(1851) proposed that Black can draw by entering a defensive fortress
Fortress (chess)
In chess, the fortress is an endgame drawing technique in which the side behind in material sets up a zone of protection around their king that cannot be penetrated by the opponent. This only works when the opponent does not have a passed pawn or cannot create one, unless that pawn can be stopped...

, but tablebases demonstrated a general win, with maximum DTC = 66 or 67 and maximum DTM = 78. (Also see pawnless chess endgame.)
KNNKP — Alexey Troitsky
Alexey Troitsky
Alexey Alexeyevich Troitsky, or Alexei, or Troitzky is considered to have been one of the greatest composers of chess endgame studies. He is widely regarded as the founder of the modern art of composing chess studies...

established this as a win for the knights if the pawn was blocked behind the Troitzky line. Analysis of the tablebases has clarified that even if the pawn has crossed the Troitzky line, White can sometimes win by forcing zugzwang
Zugzwang
Zugzwang is a term usually used in chess which also applies to various other games. The term finds its formal definition in combinatorial game theory, and it describes a situation where one player is put at a disadvantage because he has to make a move when he would prefer to pass and make no move...

. 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
Friedrich Amelung
Friedrich Ludwig Balthasar Amelung was a Baltic German chess player, endgame composer, and journalist.Amelung was born at Võisiku manor in Governorate of Livonia of the Russian Empire . He played a few games with Adolf Anderssen, Gustav Neumann, Carl Mayet, Emil Schallopp, Andreas Ascharin,...

had analyzed these two endgames in the 1900s. KRNKNN and KRBKNN are won for the strongest 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 amazing 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, this position held the record for the longest computer-generated forced mate (Otto Blathy

Ottó Bláthy

Ottó Titusz Bláthy was a Hungarian electrical engineer. In his career, he became the co-inventor of the modern electric transformer, the tension regulator, , the AC watt-hour meter, the single-phase alternating current electric motor, the turbo generator, and the high efficiency turbo...

had composed a "mate in 292 moves" problem already in 1889). However, 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."

In August 2006, Bourzutschky released preliminary results from his analysis of the following seven-piece endgames: KQQPKQQ, KRRPKRR, and KBBPKNN.
Many positions are winnable although at first sight they appear to be non-winnable. For example, this position is a win for Black in 154 moves (during which white pawn is liquidated after around 80 moves) (absolutely non-typical for this kind of endgame) (see Six-Man Endgame Server -
http://www.k4it.de/index.php?topic=egtb&lang=en).

Endgame studies

Since many composed endgame studies deal with positions that exist in tablebases, their soundness can be checked using the tablebases. Some studies have been cooked, i.e. 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 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. O-O-O mate! 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). Coincidentally, 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

Zugzwang is a term usually used in chess which also applies to various other games. The term finds its formal definition in combinatorial game theory, and it describes a situation where one player is put at a disadvantage because he has to make a move when he would prefer to pass and make no 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 tourneys. In 2003, the endgame composer and expert John Roycroft

John Roycroft

Arthur John Roycroft is an English chess endgame study composer and author, who lives in North West London. He is married to Betty Roycroft...

summarized the debate:

"[N]ot 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 Dvoretsky

Mark Izrailovich Dvoretsky is a world-renowned Russian chess trainer, writer and International Master.He was awarded the International Master title in 1975 and for a while, was widely regarded as the strongest IM in the world...

, an International Master, 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

Harold van der Heijden is a Dutch composer of chess endgame studies. He was born in Veghel, The Netherlands, on December 18, 1960. By profession, after finishing his PhD in 2009, he is head of the R&D department of a veterinary institute....

, 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

Bell Labs

Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...

website, Ken Thompson

Ken Thompson

Kenneth Lane Thompson , commonly referred to as ken in hacker circles, is an American pioneer of computer science...

maintains a link to some of his tablebase data. The headline reads, "Play chess with God."

Regarding Stiller's long wins, Tim Krabbé struck a similar note:

"A grandmaster wouldn't be better at these endgames than someone who had learned chess yesterday. It's a sort of chess that has nothing to do with chess, a chess that we could never have imagined without computers. The Stiller moves are awesome, almost scary, because you know they are the truth, God's Algorithm – it's like being revealed the Meaning of Life, but you don't understand one word."

Nomenclature

Originally, an endgame tablebase was called an "endgame data base" or "endgame database". This name appeared in both EG and the ICCA Journal 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. Nonetheless, the mainstream chess community has adopted "endgame tablebase" as the most common name.

External links

Guide to the use of Computer Chess Endgame Tablebases by Aaron Tay
Downloading tablebases
- Distribution site for tablebases up to six pieces
- [ftp://ftp.cis.uab.edu/pub/hyatt/TB/3-4-5 3-4-5 pieces] on Robert Hyatt's
  Robert Hyatt
  Dr. Robert Hyatt is an Associate Professor of Computer science at the University of Alabama at Birmingham, in the Department of Computer and Information Sciences . He is the author of the computer chess program Crafty and the co-author of Cray Blitz, a two-time winner of the World Computer Chess...
  
  FTP site
Querying tablebases on the web
- 7-piece tablebase wins (and other very long wins)
- Web query server for Nalimov tablebases by Eiko Bleicher (up to six pieces)
- Web query server for Nalimov tablebases by Lokasoft (up to five pieces)
Maximal positions, i.e. longest DTM positions for endgames with up to five pieces and some with six pieces, compiled by Kirill Kryukov

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Background

Metrics: Depth to conversion and depth to mate

Step 1: Generating all possible positions

Step 2: Evaluating positions using retrograde analysis

Step 3: Verification

Captures, pawn promotion, and special moves

Using a priori information

Correspondence chess

Computer chess

Endgame theory

Endgame studies

"Play chess with God"

Nomenclature

See also

External links