The History of Creating Seven-Piece Endgame Tablebases

The idea to create chess endgame tablebases (EndGame Table Bases or in abbreviated form EGTB) arose in the late 1970s. Now this idea looks obvious and it is seems strange that EGTBs were not generated earlier. The idea behind such bases is that for a concrete combination of pieces, for example, the king and the queen against the king and the rook, it is possible to generate the complete table which contains evaluation for every concrete position – win in n moves, loss in m moves, draw, impossible positions.

Such table needs to be generated only once by the widely known method of retrograde analysis (the other name – width-first search). The key moment in construction of the table is the size, which strongly depends on the number of chess pieces on the board. With the tables containing three or four pieces, in general, there are no problems, and such EGTBs were created many years ago.

Tables for five pieces are hundreds of megabytes even compressed, but at the modern level of computer development, are constructed easily enough. They too have already been around a long time.

Tables for six pieces occupy, not compressed, on the order of several gigabytes. Here already there are some problems with their construction, mainly with time to generate them and hard drive storage space. Nevertheless, all six-piece tables in the Nalimov format (the most popular now) had been constructed by 2005. It is curious to note that the popular belief that tables with five pieces against a lone king do not exist, is not accurate; they have already been constructed. The six-piece Nalimov tables requires 1200 gigabytes of hard disk space.

The size of seven-piece tables is measured already in terabytes, and in 2005 many experts predicted the impossibility of construction of these tables given the modern level of hardware. The approximate parameters were not specified before 2010. Nevertheless, by the beginning of 2005, the American scientist and programmer Marc Bourzutschky had constructed the first seven-piece table base – a king and four knights against a king and a queen. This ending had been studied by the early 20th century study composer Alexei Troitsky. It is Interesting that his assessment that the four knights win has proven to be true.

Also in 2005, the Russian programmer Yakov Konoval had written a program to quickly generate the six-piece tablebases economically for PCs. The international collaboration of Marc and Yakov for the creation and the analysis of seven-piece databases has begun at the middle of 2005. Yakov developed the generator, and Marc – the program for verification of the constructed base (it guarantees almost absolute correctness of the tablebases) and a number of utilities for extraction of the information from the tablebases.

At present, work on the generator and the program for verifying bases has been completed. They are very efficient and it is possible to construct, with their help, all seven-piece bases. By the end of 2018, all seven-piece bases had been constructed by Marc on standard home computers with total size about 80 Terabytes. The calculation time for one seven-piece base fluctuates from several hours to one month, and the sizes of the bases generated are in the approximate range of one to 300 gigabytes.

Bases use the DTC measurement DTC – distance to conversion (i.e., captures and/or promotions of a pawn) unlike the Nalimov tablebases of Nalimov, which use the DTM measurement – distance to mate. Basically the measurement type is insignificant as the win with the tablebase will be reached using any measurement. The standard belief that the win with the DTM-base is faster, is at least debatable – a game usually does not proceed to mate. For example, in the ending the king and a queen against the king, the opponent, most likely, will resign. Karsten Müller believes that the DTM metric is often easier for human understanding as in the DTC metric, there might be hidden deep wins after the first conversion, e.g., in a resulting six-piece ending. But of course both metrics can have their advantages in certain specific positions: (D)

1.e7 is the normal human move and best according to the DTC metric.

1.Kc6 which is shortest in DTM-metric looks odd to the human eye.

00.01A DTC is better

00.01B DTM is better

The next position is mate in two and conversion in one:

1.Rg1! is DTM optimal and the human move.

1.Qg7+! is odd, but DTC optimal.

00.01C Underpromotions – 50-move rule, History table

Like in the Nalimov tablebases, in our bases, the en passant capture is considered, but the possibility of castling is not considered. Also we do not consider the rule of 50 moves; see below. At the end of 2006, we started construction of the seven-piece endings with pawns.

All three-seven piece endings from Understanding Rook Endgames were verified by Mark Bourzutschky and Yakov Konoval’s tablebases with all promotions. For Understanding Minor Piece Endgames we used seven-piece tablebases with only queen promotions, and then verified them with Lomonosov’s tablebases with all promotions. By the end of 2018, Marc Bourzutschky and Yakov Konoval had finished all their seven-piece tablebases with all promotions and we used these tablebases for this book.

Now some words about records and the rule of 50 moves. Before the construction of seven-piece bases, the longest known win in the endings was a win in 243 moves (before conversion) in the ending R+N vs. 2Ns, found by Lewis Stiller in 1991. Later it was established that the record to mate in this class of the endings would be 262 moves. It was further established that in the seven-piece endings there are longer wins. The previously mentioned win in 290 moves in the ending 2Rs+N vs. 2Rs became the first of them. And there are more.

In May 2006, the position with a win in 517 moves was found in the ending a QN vs. RBN. In general, in many pawnless endings, more than 50 moves before conversion are necessary for a win, which was already known for a number of six-piece and even five-piece endings, including an ending such as QR vs. Q. In this situation the rule of 50 moves, in Yakov Konoval’s opinion, demands clarification, as it apparently defies the logic of a chess struggle.

Note that in chess composition, i.e., studies and problems, this rule it is not taken into consideration at all. Of course it is easy to find positions where this rule is taken in account, but in some absolutely drawn positions, it is possible to play more than 500 moves.

Karsten Müller thinks that for a human over-the-board play, the 50-move rule should remain, as human play is not perfect anyway.

There were two interesting results which had been achieved by in 2009. The first was the construction of several eight-piece bases without pawns in which one side has two dark-square and two light-square bishops. The most interesting of them is the tablebase 4Bs vs. 2Rs. It appeared that generally four bishops win, and more than 50 moves are necessary to win.

The second result is the use of the idea about the limited promotions for finding of positions in which two underpromotions into different pieces are necessary for a win. This approach was suggested by well known mathematician and chess composer Noam Elkies and was implemented by Marc and Yakov. Thus the computer acts in a role of the composer of chess studies, while the human needs only to analyze the found positions and to decide, whether are they actual studies or not, possibly adding additional moves.

In fact, two studies by computer were already published and according to experts in chess composition (Oleg Pervakov and others) they are good enough.

In 2012 the team from the Moscow State University (Vladimir Makhnychev and Victor Zakharov) constructed seven-piece EGTBs using the supercomputer Lomonosov in the DTM format. Now their EGTBs are available online (for an honorarium) and it is possible to verify online any seven-piece position (except six pieces versus a lone king).

However, in our book, we use many utilities developed by Marc Bourzutschky and Yakov Konoval which allow the discovery of many interesting positions automatically from different chess bases.

Some main events in the history of creating chess endgame tablebases:

In 1965, Richard Bellman proposed the creation of a database to solve chess and checkers endgames using retrograde analysis. Instead of analyzing forward from the position currently on the board, the database would analyze backward from positions in which one player was checkmated or stalemated. 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 Strohlein published a doctoral thesis with analysis of the following classes of endgame: KQ vs. K, KR vs. K, KP vs. K, KQ vs. KR, KR vs. KB, and KR vs. KN.

In 1977 Thompson’s KQ vs. KR database was used in a match versus grandmaster Walter Browne. Ken Thompson and others helped extend tablebases to cover all four- and five-piece endgames, including in particular KBB vs. KN, KQP vs. KQ, and KRP vs. KR.

Lewis Stiller published a thesis with research on some six-piece tablebase endgames in 1995. More recent contributors have included the following: Eugene Nalimov, after whom the popular Nalimov tablebases are named; Eiko Bleicher, who adapted the tablebase concept to a program called “Freezer”; Guy Haworth, an academic at the University of Reading, who has been published extensively in the ICGA Journal 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 (KQPP vs. KQP) for the endgame of the Kasparov versus the World online match; Vladimir Makhnychev and Victor Zakharov from Moscow State University, who completed 4+3 DTM-tablebases (525 endings including KPPP vs. KPP) in July 2012.

The tablebases are named Lomonosov tablebases. The next set of 5+2 DTM-tablebases (350 endings including KPPPP vs. KP) was completed in August 2012. The high speed of generating the tablebases was a result of using a supercomputer named Lomonosov. The size of all tablebases up to the seven-piece is about 140 TB. The tablebases of all endgames with up to six pieces are available as a free download, and may also be queried using web interfaces (see the external links below).

The Nalimov tablebase requires more than one terabyte of storage space. See the following URL for more information: https://en.wikipedia.org/wiki/Endgame_tablebase#Tables.

Marc Bourzutschky and Yakov Konoval also have generated some unusual tablebases for non-standard boards and non-standard pieces. The most interesting results from these tablebases are (a) the ending Q vs. R is drawn for a 16x16 board; (b) the ending R vs. B is won on a 6x6 board; and (c) the ending KAN vs. KBNN (“A” means “archbishop” = B+N) is indeed a very deep ending, with a maximum DTC of 568 moves (maximum DTM for usual seven-piece tablebases, created by the Lomonosov team, is “only” 549 moves).

00.01D Longest win – Conventions

B -18

The use of tablebases allows the finding of very deep wins, including wins with maximum length for the given type of ending. We give some record positions in our book for different endings. The annotation conventions are different. Double exclamation points (!!) mean the only winning move and a single exclamation point (!) means the only move with minimum DTC value, but not the only move to win. Double-letter zee (zz) means a position of mutual zugzwang. 1…Kc1 2.Re4 Wins in 18 moves 2.Rf4 or 2.Rh4 also wins in 18 moves. 2…Kb2 3.Re5!! The only winning move. 3…Ka3 4.Kc4!! Bf2 5.Re6!! zz Mutual zugzwang 5…Bg1 6.Re1! The shortest way to win, but not the only winning move. 6…Bf2 7.Rf1 Bb6 8.Rb1!! Bc7 9.Rb3+!! Ka2 10.Kc3!! Bd6 11.Kc2! Bh2 12.Re3 Bg1 13.Re1! Bh2 14.Re2! Bc7 15.Re7! Bb8 16.Rb7 Bd6 17.Ra7+! Ba3 18.Ra8 Ka1 19.Rxa3#! 1-0