Endgame database

Example of a database query. The database shows the mate distance of all possible moves of the player on move (here white). Of these, 1. Kc6 and 1. Qa6 + lead to the fastest possible mate in five moves, so they are the “best” moves here.

Endgame databases have complete endgame knowledge about chess positions with few stones. There are now endgame DVDs with almost all types of positions up to six pieces, for example the important rook ending "King, rook and two pawns against king and rook" has been completely analyzed . A query in the database shows in every position whether white or black wins in the best game on both sides and which is the “best” move, or whether the position is a draw and which moves are drawn.

In 2012 the University of Moscow reported that the databases with seven stones were completely created. They cover approximately 140 terabytes.

Basics

There are several ways to set a destination for a particular location. The American computer scientist Ken Thompson has determined mate and the transition to another winning endgame (by capturing a piece or by converting ) as equivalent. In a queen against rook position (without further pieces), capturing the rook (without a subsequent queen loss) as a partial goal was as good as instant mate. Nowadays (established by Nalimov and other developers before), mate in the shortest number of moves is the goal, either with or without the 50 move rule .

Apart from programming errors and minor exceptions, the results of the computer generated endgame databases are complete and error-free. The possibility of programming errors can almost be ruled out because many endgames have already been calculated in different ways and the results have been checked against each other. Castling , for example, is an exception , which in most cases is ignored in endgame databases.

The endgame theory, which had grown over the centuries of chess development, could be specified more precisely using endgame databases. With the five stone players it was remarkable that the final “king and two bishops against king and knight” , which was previously considered a draw, can generally be won. However, there are positions in which checkmate can only be forced after 66 moves. This collides with the 50-move rule, which is laid down for practical reasons, so that such positions end up in a draw with the best game on both sides in a game of chess, although mate would be inevitable.

In the meantime, in more recent endgame books (e.g. by John Nunn and in the two principal works by Frank Lamprecht and Karsten Müller ), the inadequacies in the classical works of André Chéron , Juri Awerbach , Max Euwe and Reuben Fine have been corrected, specified and completed.

During a practical game on the board, the endgame databases (especially for these lengthy endgames) play no role. On the one hand, outside help is prohibited during the game. On the other hand, even the best players cannot play so precisely in more complicated positions. This can e.g. B. can be observed in a queens endgame "checkers and pawns against checkers" if you check the course of the game with an endgame database. The shortage of cooling-off times and the abolition of hanging games have led to a decrease in quality in the final phase of chess games.

Endgame databases can be used in correspondence chess , for game analyzes, for proving the correctness of studies or multiple moves in chess composition and in chess programs .

production method

On a large scale, Ken Thompson at Bell Laboratories created endgame databases with a computer program under the advice of John Roycroft . However, there was already earlier work in limited areas by Ströhlein, Zagler and in the Soviet Union. At that time computers were still too expensive to be widely used. It was not until after some time that Thompson's results could be passed on and used on CD that they caught the attention of broader circles of chess players.

The algorithm for creating it was published in 1912 by Ernst Zermelo at a mathematicians' congress. Later he found himself as a special case in mathematical game theory. This retrograde analysis procedure is relatively easy to describe in four steps:

Step 1: Creating all possible positions with no more than n stones
An index is reserved in a file for all permissible positions with at most n stones. At Thompson (for n = 5) this file was several gigabytes in size.

Step 2: Finding all winning positions for White

Find all positions where black is matt . Mark these positions in the file.
Find all positions in which it is White's turn and White has at least one move that leads to a position under 1.. These are all positions in which White can checkmate with one move. Mark these positions in the file.
Find all positions in which it is Black's turn and each move by him leads to a position under 2.. Black cannot prevent mate in one move. Mark these positions in the file.
Find all positions in which it is White's turn and White has at least one move that leads to a position under 3. These are all positions in which White can checkmate with 2 moves. Mark these positions in the file.
Find all positions in which it is Black's turn and each black move leads to a position under 4. or 2.. Black cannot prevent mate in two moves here. Mark these positions in the file.
Find all positions in which it is White's turn and White has at least one move that leads to a position under 5.. These are all positions in which White can checkmate with 3 moves. Mark these positions in the file.

etc.

At some point this process breaks off because in one step the new set of positions to be created remains empty and so no further non-empty sets can be generated. Then all positions are found in which White wins. Go to step 3.

Step 3: Finding all winning positions for Black
These positions are found using the same procedure as in step 2.

Step 4: The remaining positions are drawn.
The remaining positions cannot be won by either white or black. So there are draw positions.

The method used by Nalimov today includes some technical improvements. The algorithm presented remains basically the same.

Theoretically, you can completely analyze the entire chess game by expanding the process to 32 pieces. In practice, however, this is not yet possible because with each additional stone the number of positions and thus the computing time increases drastically. Regardless of this fact, the relevant analyzes will continue to be carried out with the help of powerful computers. At the end of 2002, all positions with a maximum of five figures had already been recorded and analyzed; positions with six figures were finished in August 2005. Since the spring of 2006, the first results of positions with seven stones (without pawns) have been available. You can now purchase all endgame positions with up to five stones as well as the most important six - stone in Syzygy format on commercially available DVDs . The tables on hard drives or solid-state drives are stored and allow modern chess programs such as Komodo , Deep Fritz , Houdini and stockfish to use the data during the duration of the program, resulting in a substantial increase in the skill level in the final also if there are more than six stones.

In 2012 the University of Moscow reported that the databases with seven stones were completely created. Currently, the data is being imported into a format that can be used by chess programs. It is estimated that the complete seven-stone database is approximately 140 terabytes.

Metrics

Endgame databases come in several metrics. In the DTM metric ( depth to mate , so depth to Matt ) the distance is stored, which is needed for the longest opponent's counterplay for Matt. However, the 50-move rule is not taken into account. For this reason, databases with the metrics DTC ( Depth to Conversion , i.e. depth to change ) and DTZ ( Depth to Zero , i.e. depth to zero ) were created. This then resulted in the DTZ-50 metric, which takes the 50-move rule into account. With DTC, the distance required from a particular position to a conversion or a stroke case is stored.

Use

Chess players are limited in the direct use of recent research on their own computer due to the size and number of files and the disk space required. However, there are special servers on the Internet where the results of a specific endgame position can be determined through queries. Thompson gave his results to interested parties at the production price of the CD, at one company these four CDs with positions of up to five stones and at most one farmer could be purchased. Thompson compressed his data with the Huffman method in order to be able to get along with a CD for the query. This decision proved to be a hindrance to the further development and optimization of chess programs .

In a chess program with an activated endgame database, one notices a significantly higher move frequency in the endgame, as the computer now calculates less and has to look more often in its endgame database, similar to searching for positions already calculated in its hash table .

50-move rule

The 50-move rule , which is useful for practical chess games, makes computer calculations extremely difficult, especially in endgames with pawns. Either the program ignores the draw rule and goes straight to mate, or the pawn is drawn primarily, but this can lead to a much longer variant, even in positions that are mated under 50 moves. The correct solution must further subdivide all endgames with the exact pawn positions such as "King, queen and pawn on the 5th row against king and queen". As soon as the pawn moves, the 50-move rule is interrupted and the endgame takes over the number of moves from the endgame with the pawn on the 6th row, which has to be calculated, and so on. The number of positions gained in this way will hardly deviate from the direct mate path, so that the practical benefit for the much more complex procedure seems too small.

Example:

	a	b	c	d	e	f	G	H
8th									8th
7th									7th
6th									6th
5									5
4th									4th
3									3
2									2
1									1
	a	b	c	d	e	f	G	H

For this specific example, the endgame database shows that if the 50-move rule is disregarded and if both sides play optimally, White must checkmate after 65 moves. It is an endgame “tower and bishop against tower”. According to the 50 move rule, this endgame is a draw with Black's best defense. This type of endgame led to FIDE temporarily replacing the 50-move rule with a 100-move rule .

Grandmaster Edmar Mednis presented the database solution and commented on the process in detail. However, he refers to studies by Ken Thompson on the computer Belle in 1986. This does not find Black's best defense on move 55 and ends with mate after only 59 moves.

Chess composition

Endgame databases can be used to review Orthodox problems and studies . Refuting false assumptions can also make a large number of studies incorrect. An example of this are studies in which it was assumed that two runners could normally only draw against one jumper. However, blind trust in the database can lead to incorrect results, for example if a database move is faster, but only later leads to the author's solution, who does not always provide the longest resistance, but the one where White only has one possible winning move.

At the congress of the Standing Commission for Chess Composition at FIDE in Rhodes in 2007 it was determined that an endgame database does not anticipate chess compositions.

Examples:

Paul Heuäcker
German chess sheets 1938

	a	b	c	d	e	f	G	H
8th									8th
7th									7th
6th									6th
5									5
4th									4th
3									3
2									2
1									1
	a	b	c	d	e	f	G	H

White moves and wins

Genrich Gasparjan
Shachmaty w SSR 1946

	a	b	c	d	e	f	G	H
8th									8th
7th									7th
6th									6th
5									5
4th									4th
3									3
2									2
1									1
	a	b	c	d	e	f	G	H

White moves and wins

Left: The database shows that in addition to Heuäcker's solution 1. Bf6 + Ke8 2. Bg2 Kd7 3. Be5 Ng4 4. Bh3 Ke6 5. Bf4 Kf5 6. Bc1 d3 7. Bd2 also 1. Bxd4 wins - a move not by Heuäcker was overlooked, but was misjudged at the time, as the final of two bishops against a knight was considered a draw before the corresponding databases were calculated, also due to a supposed fortress .

Right: The database confirms that only Gasparjan's solution 1. Ka2 !! Rh3 2nd Kb2 Rg3 3rd Kc2 Rh3 4th Kd2 Rg3 5th Ke2 Rh3 6th Kf2 wins.