Endgame tablebases: A short history

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…

Endgame Turbo 5 USB flash drive

Perfect endgame analysis and a huge increase in engine performance: Get it with the new Endgame Turbo 5! This brings the full 6-piece Syzygy endgame tablebases on a pendrive. Just plug it in a USB socket and you are set!

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

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)

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

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! This brings the full 6-piece Syzygy endgame tablebases on a pendrive. Just plug it in a USB socket and you are set!