Endgame tablebases: A short history

by Albert Silver
3/16/2018 – One of the keystones to improving our understanding of the endgame is the endgame tablebase, a sort of oracle that first came into existence over 40 years ago. This revolutionary technology, that first saw light in the chess world thanks to computer scientist and pioneer Ken Thompson, has evolved a great deal since then. Here is a look at its beginnings and what each generation brought.

Endgame Turbo 5 USB flash drive Endgame Turbo 5 USB flash drive

Perfect endgame analysis and a huge increase in engine performance: Get it with the new Endgame Turbo 5!

More...

What are endgame tablebases?

Simply put: they are perfect chess. We all know that the number of possible positions in chess outnumbers the number of atoms in the universe, or at least that is what we are told (begging the question who counted the atoms), but suffice it to say no computer will ever calculate them all. However, that is with all 32 pieces on the board. For reduced numbers of pieces (such as the position above) databases have been created in which every possible position resulting from it has been calculated and stored so that you or a computer can instantly know the best moves. There is no need to ‘calculate’ anything at this point, you just consult the database of endgame positions known as tablebases.

A brief history

The first steps toward the creation of tablebases came from the noted applied mathematician Richard Bellman, who proposed building a database to solve chess and checkers endgames using retrograde analysis. Although not properly analysis, the idea was to analyze backwards from the simplest positions (i.e. three pieces, which include the two kings) and gradually adding more.

This turned into practical reality with Ken Thompson’s KQKR (King and Queen vs King and Rook) database used in 1977 in a match against the reigning US Champion, GM Walter Browne. Ken Thompson then extended the tablebases to cover all four and five-piece endgames.

From zero to six in ...

Then in 1991, the next step was taken when Lewis Stiller built the first six-piece database using a computer with 65,536 processors working in parallel. The endgame of choice was rook and bishop vs two knights. The computer generated 100 billion legal positions, and Stiller used the method pioneered by Ken Thompson, described in detail in the article How God plays chess. His startling result: the rook and bishop can generally win, though in some cases requiring (and this is no joke) well over two hundred moves to do so! For instance, the position below is a win for White…

 

…if he finds 223 accurate moves that will allow him to capture one of the knights. 

Around this time, experts who replayed the examples provided by Stiller could not discern any strategy that human beings could comprehend. The endgame database seemed to play completely pointlessly until — almost 200 moves later — the black king had somehow been pushed to the edge of the board and the two knights are struggling to defend each other. Then one of them falls.

Frederic Friedel tells me that at this time he showed two positions from this endgame to one of the most powerful analytical teams imaginable: Garry Kasparov’s world championship training camp. Frederic did not ask them to solve the positions, he simply told them that in one of the two positions White had to find 28 unique moves to force the other position in order not to relinquish the win. What the Kasparov team had to do was simply to tell him which was the earlier position and which the one that had to be forced in order not to draw. There was a fair amount of merriment as the greatest chess minds in the world could not decide which was which. “They look completely equivalent, it is impossible to say which one is more advanced,” Garry said. He understood that humans could never play the ending perfectly and would always be inferior to the computer. He just needed to make sure that while playing imperfectly he handled it slightly better than his (human) opponent, who would also never be able to comprehend the intricacies of the endgame. That is why he and other top grandmasters would practice against the computer and use it to hone their strategy.

Thompson CD

An image of the CDs published for the Thompson's tablebases | Image: Gerard Holzman

The next evolution: Edwards and Nalimov

In spite of this, progress in completing the entire six-piece files was slow. Thompson’s tablebases were the first foray but had problems that made it unusable within a program’s search. This was solved by Steven Edwards, who built a set in the early 90s for his program ‘Spector’ using a new design, and coding, that addressed the shortcomings. After finishing the construction procedure in 1994, Steven Edwards made the whole data, documentation and a test program written in ANSI-C publicly available on the Internet. It must be added that this was not the extent of his contributions to chess, as Edwards, a computer scientist, would also devise the PGN, EPD and FEN standards that are used to this day. The PGN files you download to view games are thanks to his efforts.

Until the advent of the compressed Nalimov Tablebases, Edwards' Tablebases were quite popular and used in several chess programs, such as Crafty, Gromit, and the commercial MChess Pro, to name a few. The only problem was that the full five-piece set alone was well over 50 GB! Furthermore, if you consider that each additional piece to a tablebase takes up about 160 times more space, then a full six-piece set could be expected to need roughly ten terabytes of space or 10,000 GB. If today 10 TB still seems like a lot, imagine 25 years ago. Enter Nalimov.

Eugene Nalimov is a Russian computer scientist, who was living in the US, working for Microsoft as a member of the team developing the Visual C++ compiler. In 1998, he published his work to vastly reduce the space needed to store the full five-piece tablebases, as well as optimize it for engines so they could use them within their search. The full five-piece set now took a mere 7.1 GB. This also had serious repercussions on the six-piece set, which would need much less space, and in 2005, the final six-piece files were released. The full six-piece Nalimov tablebases took up 1.2 TB. Although the files were free to download from university servers where they were stored, the very idea was more than a little daunting. There were other practical issues too. The speed of consulting a full TB hard disk on-the-fly for millions of positions by an engine just wasn’t practical and led to such slowdowns overall, that it was not clear an engine played better with them than without. Another was that they were not designed for multi-thread searches, in other words, multi-core processors.

Syzygy arrives

It would take a few years, but the next big leap came in 2013 when Ronald de Man announced in a specialized computer chess forum (much as Nalimov had done) the creation of a new tablebase generator with new ideas. Ronald is a Dutch mathematician and computer scientist who got a silver medal in the 1990 International Mathematical Olympiad (for example). He is co-developer of the Linux desktop environment GNOME, and a chess and computer chess aficionado. His new endgame tablebases, released for free to the public, introduced several important innovations. The first concerned the issue of 200+ move solutions. The bases included five evaluations for a position in the context of the FIDE 50-move rule in chess:

+2 = unconditional win for the side to move
+1 = win which can be frustrated by best play and a 50 move rule draw claim
+0 = unconditional draw
–1 = loss saved by a 50 move rule draw claim
–2 = unconditional loss

Contrary to previous versions of the bases which took on the names of their creators, de Man chose to call them Syzygy (pronounced Sih-Zih-Gee), which means a pair of connected or corresponding things. These new bases are not only best suited for multithread searches, but the full set also takes up a mere 150 GB. As such, they are now the de facto choice for use with an engine.

So how can you, the user, enjoy this technological marvel without compromise? Well, with our latest product, the Endgame Turbo 5. Now you can run all important six-piece endings in ChessBase or a Fritz compatible program directly from a USB stick!

143 six piece Syzygy Tablebases on USB 3.0 Flash drive (128 GB)

KBNPvKQ
KBNPvKR
KBNvKBN
KBNvKBP
KBNvKNN
KBNvKNP
KBNvKPP
KBPPvKB
KBPPvKN
KBPPvKP
KBPPvKQ
KBPPvKR
KBPvKBP
KBPvKNN
KBPvKNP
KBPvKPP
KNNPvKB
KNNPvKN
KNNPvKP
KNNPvKQ
KNNPvKR
KNNvKNN
KNNvKNP
KNNvKPP
KNPPvKB
KNPPvKN
KNPPvKP
KNPPvKQ
KNPPvKR
KNPvKNP
KNPvKPP
KPPPvKB
KPPPvKN
KPPPvKP
KPPPvKQ
KPPPvKR
KPPvKPP
KQBPvKQ
KQBvKBP
KQBvKNP
KQBvKPP
KQBvKQB
KQBvKQN
KQBvKQP
KQBvKRP
KQBvKRR
KQNNvKP
KQNNvKQ
KQNPvKQ
KQNvKBP
KQNvKNN
KQNvKNP
KQNvKPP
KQNvKQN
KQNvKQP
KQNvKRP
KQNvKRR
KQPPvKQ
KQPvKBB
KQPvKBN
KQPvKBP
KQPvKNN
KQPvKNP
KQPvKPP
KQPvKQP
KQPvKRB
KQPvKRN
KQPvKRP
KQPvKRR
KQQvKQP
KQQvKQQ
KQQvKQR
KQRvKPP
KQRvKQB
KQRvKQN
KQRvKQP
KQRvKQR
KQRvKRR
KRBBvKQ
KRBNvKQ
KRBPvKQ
KRBPvKR
KRBvKBB
KRBvKBN
KRBvKBP
KRBvKNN
KRBvKNP
KRBvKPP
KRBvKRB
KRBvKRN
KRBvKRP
KRNNvKP
KRNNvKQ
KRNNvKR
KRNPvKQ
KRNPvKR
KRNvKBB
KRNvKBN
KRNvKBP
KRNvKNN
KRNvKNP
KRNvKPP
KRNvKRN
KRNvKRP
KRPPvKQ
KRPPvKR
KRPvKBB
KRPvKBN
KRPvKBP
KRPvKNN
KRPvKNP
KRPvKPP
KRPvKRP
KRRBvKQ
KRRNvKQ
KRRPvKQ
KRRvKBB
KRRvKBN
KRRvKBP
KRRvKNN
KRRvKNP
KRRvKPP
KRRvKRB
KRRvKRN
KRRvKRP
KRRvKRR
KBBNvKQ
KBBPvKQ
KBBPvKR
KBBvKBB
KBBvKBN
KBBvKBP
KBBvKNN
KBBvKNP
KBBvKPP
KBNNvKB
KBNNvKN
KBNNvKP
KBNNvKQ
KBNNvKR
KBNPvKB
KBNPvKN
KBNPvKP

It only takes a few seconds to install: insert the USB stick and start the program ChessBaseEndgameTurboSetup.exe. You only need to do this once – the setup simply sets the paths to the tablebases correctly.

Note that you can also copy the tablebases to your hard drive, if you have enough space (at least 128 GB) free. But that is not advisable or necessary: Endgame Turbo 5 is optimized for running off the USB 3.0 stick, and the performance in that configuration will definitely be superior.

After this short installation process you can start ChessBase 13/14 or your Fritz 15/16 program. If you now have a six-piece ending on the board and start an engine (Fritz, Komodo, Houdini), a list of all legal moves with evaluations is displayed:

Click or tap to enlarge

If the positions are won or lost a number in brackets tells you in how many moves the next irreversible position will be reached. That is, when a pawn is moved or material vanishes from the board. In pawn endings this information is hardly ever relevant because pawns will often be moved. But in endgames without pawns and in which no pieces are captured for long periods the 50-move rule comes into play. In the example above the minimum number of moves until a new irreversible position is reached (in this case the advance of the black passed pawn) is 12.

Note that when you are using the Komodo or Houdini engines the Syzygy Tablebases are also consulted in the search. This means that even when there are considerably more than six pieces on the board, when they occur in the search tree the engine will retrieve them and evaluate the positon far more accurately than without the tablebases. Here's an example provided by our endgame expert Dr. Karsten Müller (with many more to follow):

[Event "CSR-ch"] [Site "Trencianske Teplice"] [Date "1979.??.??"] [Round "9"] [White "Uhlmann, Wolfgang"] [Black "Jansa, Vlastimil"] [Result "0-1"] [ECO "A30"] [WhiteElo "2530"] [BlackElo "2495"] [Annotator "Müller,Konoval"] [SetUp "1"] [FEN "8/8/8/4pk2/6p1/2R1K1P1/r7/8 w - - 0 62"] [PlyCount "30"] [EventDate "1979.11.??"] [EventRounds "15"] [EventCountry "CSR"] [EventCategory "9"] [SourceTitle "URE"] [SourceDate "2001.11.25"] [SourceVersion "1"] [SourceVersionDate "2015.05.17"] [SourceQuality "1"] {Source: Understanding Rook Endgames, Müller and Konoval, GAMBIT 2016. In this constellation there is a surprising number of deep draws, when the defender gives the g-pawn:[#]This position occured many times in practical games, and in many of these the weaker side couldn't find the correct way to draw:} 62. Rc8 $1 Rg2 63. Rf8+ $1 Ke6 64. Re8+ $1 (64. Ke4 $2 Rxg3 65. Re8+ Kf6 $1 66. Re6+ $5 (66. Rxe5 Rf3 $19) (66. Rf8+ Kg7 67. Rf5 Kg6 68. Rxe5 Rf3 $1 $19) 66... Kg5 $1 67. Rxe5+ Kh4 $1 $19) (64. Rg8 $2 Rxg3+ 65. Kf2 Rf3+ 66. Kg2 Kf5 67. Rf8+ Ke4 68. Ra8 Ke3 69. Ra3+ Kf4 $19) 64... Kf6 65. Rf8+ $1 Ke7 {[#]The critical position. All previous moves look obvious, but now the drawing move is very tricky.} 66. Rb8 $2 (66. Rf5 $2 Ke6 $1 67. Rg5 Rxg3+ {This 6-man ending is won in 28 moves} 68. Kf2 (68. Ke4 Kf6 $1 69. Rf5+ Kg6 70. Rxe5 Rf3 $1 $19) 68... Kf6 $1 69. Rg8 Rf3+ 70. Kg2 Kf5 $19) ({The correct move is} 66. Rg8 $3 Rxg3+ 67. Kf2 (67. Ke4 $2 Kf7 68. Rg5 Kf6 69. Rxe5 Rf3 70. Ra5 Rf1 $19) 67... Rf3+ 68. Kg2 $1 Rf4 69. Kg3 {[#]Now the 6-man ending is drawn, in an analogous way to the defence in the ending with rook's and bishop's pawn:} Ke6 70. Ra8 Kf5 71. Rf8+ (71. Kh4 Ke4 72. Ra4+ Kf3 73. Ra3+ Kg2 74. Ra2+ Rf2 75. Ra3 $11) 71... Ke4 72. Ra8 Rf1 (72... Rf3+ 73. Kxg4 Rd3 74. Ra4+ Rd4 75. Ra1 Ke3+ 76. Kg3 $11) 73. Ra7 {[#]The rook just stays in the north west corner.} Rd1 74. Ra8 Ke3 75. Kxg4 e4 (75... Rg1+ 76. Kf5 e4 77. Ra3+ $11) 76. Ra3+ Rd3 77. Ra2 $11) 66... Rxg3+ 67. Ke4 Kf6 68. Rf8+ Kg6 69. Rg8+ Kf6 70. Rf8+ Kg6 71. Rg8+ Kf7 72. Rh8 Kg7 73. Re8 Rf3 74. Re6 Rf1 75. Rd6 Rf6 76. Rd5 Kg6 0-1

Order your Endgame Turbo 5 on USB flash drive now in the ChessBase Shop


Endgame Turbo 5 USB flash drive

Perfect endgame analysis and a huge increase in engine performance: Get it with the new Endgame Turbo 5!

More...



Born in the US, he grew up in Paris, France, where he completed his Baccalaureat, and after college moved to Rio de Janeiro, Brazil. He had a peak rating of 2240 FIDE, and was a key designer of Chess Assistant 6. In 2010 he joined the ChessBase family as an editor and writer at ChessBase News. He is also a passionate photographer with work appearing in numerous publications.
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register

Werewolf Werewolf 3/19/2018 09:10
"It only takes a few seconds to install: insert the USB stick and start the program ChessBaseEndgameTurboSetup.exe. You only need to do this once – the setup simply sets the paths to the tablebases correctly.
Note that you can also copy the tablebases to your hard drive, if you have enough space (at least 128 GB) free. But that is not advisable or necessary: Endgame Turbo 5 is optimized for running off the USB 3.0 stick, and the performance in that configuration will definitely be superior."

This last sentence is clearly in reference to Turbo 5, not Nalimov, and it's not correct if one has a SSD.
Bertman Bertman 3/19/2018 06:45
@Martin - Lomonosov is indeed great except it takes up a mere... 140 TB.
@Crispy - The Endgame Turbo 5 is the first time ChessBase offers the full 6-piece TB experience. the previous edition was a very reduced set on four DVDs.
MartinG1949 MartinG1949 3/19/2018 05:46
Is there more to come?
What about the 7-man Lomonosov tablebases? OK. You can't load these into your chess engine for direct use during play but the free program from Google Play Store loaded onto your mobile phone is a fantastic study resource - giving you instant free access to the Giga-billions of nodes stored on the super-computer at Moscow State University. It's the most amazing endgame resource to date.
crispyambulance crispyambulance 3/18/2018 08:44
"Note that you can also copy the tablebases to your hard drive, if you have enough space (at least 128 GB) free. But that is not advisable or necessary: Endgame Turbo 5 is optimized for running off the USB 3.0 stick, and the performance in that configuration will definitely be superior."
As I've already bought endgame turbo, any support from chessbase on how to optimise it to work off a pendrive if I buy one?

Thanks
Lars Rasmussen Lars Rasmussen 3/17/2018 12:37
The number og possible games in chess is far greater than the number of atoms in the observable universe, but the number of legal positions is not. See f.ex. the Wikipedia article about Shannon number.
Bertman Bertman 3/16/2018 04:59
@werewolf - You are overlooking the timeline. This was in reference to the full Nalimov set, completed in 2005. There were no 1.5-2TB SSD drives to fit the full 1.2TB set.
Bertman Bertman 3/16/2018 04:32
Hi Ingo,

Thanks for the Pachman references, which I did not know. Great stuff. I was aware of Strohlein's work, but at some point had to make some choices on what to cover, else I'd mention Gaviota TBs, Scorpio, etc as well. Thompson's design was really the first major breakthrough, as it led to the creation of the 4 and 5-piece sets eventually, and public consumption.

Albert
flachspieler flachspieler 3/16/2018 04:03
On my previous posting: I found Pachman's representation of the
event in an old chess magazine from January 1975: He was asked
to play the stronger side of one of the endgames KBN-K,
KRB-KR, KR-KN, KQ-KR against the database (although Pachman
did not understand what a database is...).
I have taken a photo of the article und put it here:
http://www.dgob.de/yabbse/index.php?action=dlattach;topic=6053.0;attach=6328;image

Some more photos and some text (in German) is here:
http://www.dgob.de/yabbse/index.php?topic=6053.msg216314#msg216314

Ingo Althoefer.
flachspieler flachspieler 3/16/2018 12:49
A nice article, but the first ten (or so) years are missing. In 1970 Thomas Stroehlein got his Ph.D. title at TU Munich for complete computation of several chess endgames. For some information see
https://chessprogramming.wikispaces.com/Thomas+Str%C3%B6hlein
And an anecdote: The database should be demonstrated against GM Ludek Pachman
in the early 1970's, with the database defending the weaker side in K+Queen vs K+Rook. When the database
moved the rook away from its king, Pachman stopped the demonstration with the comment: Such a move must be nonsense. (Well known by experiments of Dave Callander about ten years later it became common knowledge that these rook excursions are indeed the most stubborn defense.)

Ingo Althöfer.
Werewolf Werewolf 3/16/2018 11:46
Great article.

Just one thing: I don't think it is correct to say that running the tablebases off a hard drive will necessarily be slower, if that hard drive is a SSD. In that case it would be faster than a USB drive.
1