The history of Syzygy tablebases

[Isaac]

Hello Ronald de Man,

Could you describe the situation of end game tablebases when you started to work on the Syzygy ones? After the success of Gaviota tablebases which reduced a lot the size of files (due to compression I suppose), what made you think you could come up with something a bit different but as effective, and more importantly, much more "compressed"?

Thanks for your time. It's always a pleasure for me to read you even though many things are over my head.

[CMCanavessi]

Hello Ronald de Man,

Could you describe the situation of end game tablebases when you started to work on the Syzygy ones? After the success of Gaviota tablebases which reduced a lot the size of files (due to compression I suppose), what made you think you could come up with something a bit different but as effective, and more importantly, much more "compressed"?

Thanks for your time. It's always a pleasure for me to read you even though many things are over my head.

I would also like someone to comment on the pros and cons of the different TBs formats, we have Gaviota, Syzygy, Scopriobases, Shredderbases, Nalimov, Lomonosov, etc.. Why would you choose one over the other? What are their differences? Which ones are already considered obsolete?

[syzygy]

Could you describe the situation of end game tablebases when you started to work on the Syzygy ones? After the success of Gaviota tablebases which reduced a lot the size of files (due to compression I suppose), what made you think you could come up with something a bit different but as effective, and more importantly, much more "compressed"?

I had generated 5-piece WDL+DTZ TBs for regular chess and suicide chess in 2005 with a similar compression scheme (based on "Re-Pair compression" followed by Huffman). The current generator is an almost complete rewrite which made the generator much faster and multi-threaded and which added many ideas to improve the compression, basically by not storing information that can easily be reconstructing when probing.

[Evert]

I would also like someone to comment on the pros and cons of the different TBs formats, we have Gaviota, Syzygy, Scopriobases, Shredderbases, Nalimov, Lomonosov, etc.. Why would you choose one over the other? What are their differences? Which ones are already considered obsolete?

Scorpio and (iirc) Shredder are bitbases: they store whether a position is won for the side to move or not. Typically that is enough during the search, as long as the root position is not a tablebase position. In that case you need a way to make progress, and the bitbases don't really help. However, in practice chess programs can win many endgames without tablebases.
Nalimov and Gaviota store distance to mate (DTM) for the side to move (or not-won if the position is not won), but they ignore draws by the 50-move rule. Nalimov has 6 men, but comes with an obnoxious custom license. Gaviota probing code is open source under a liberal license, but it only has up to 5 men. Compression is (iirc) much better than Nalimov.
Lomonosov is DTM up to 7 pieces, but not available for free (and impractically large).
Syzygy bases store the number of moves needed to win a position under the 50-move rule (DTZ50). You win by either mating the opponent, making a winning pawn push or by converting to another won ending. The generator and probing code are open source.

For practical purposes, if you pick just one, Syzygy is probably the best pick. In a pinch, Syzygy+Gaviota might be better, since they will give you the shortest DTM in positions that are won under the 50-move rule. Syzygy alone doesn't do that. If that is better or not is a matter of taste.
Nalimov should be a no-go because of the license and Lomonosov is simply not an option.
Pure bitbases are probably the least useful these days (Syzygy and I think Gaviota actually already include bitbases for the search).

[syzygy]

Scorpio and (iirc) Shredder are bitbases: they store whether a position is won for the side to move or not.

If I am not mistaken, both store W/D/L.

Gaviota probing code is open source under a liberal license, but it only has up to 5 men. Compression is (iirc) much better than Nalimov.

I think Gaviota's compression ratio is similar to Nalimov's (I see 6.5GB being mentioned where Nalimov is a bit above 7GB). I don't know how they compare in terms of decompression speed.

[Nordlandia]

It would be interesting to know how Nalimov-6 performs on high-end ssds. I don't have SSDs larger than 256 GB.

Nalimov pros and cons

My observations

Pluss | Does not eat RAM during analysis
Pluss | Display depth-to-mate (DTM)
Minus | Cumbersome size
Minus | No 50-move rule

Gaviota is slightly lower in size but only limited to 5-man.

The only drawback of syzygy is no dtm information.

[hgm]

"Does not eat RAM during analysis"... Isn't that the same thing as saying "Fails to profit from RAM that otherwise would be idle, and just leaves that go to waste"?

[Robert Pope]

"Does not eat RAM during analysis"... Isn't that the same thing as saying "Fails to profit from RAM that otherwise would be idle, and just leaves that go to waste"?

Not really. Suppose you have two programs: one does tons of disk thrashing if it doesn't have 8GB of RAM available, the other doesn't:

Code: Select all

       4GB    8GB
A    2400   2450
B    1800   2480

I would say "B plays poorly with less than 8GB of RAM". I would never say "A isn't taking as good advantage of the extra RAM".

[Nordlandia]

Nalimov algorithm does not cache egtb in ram, this mean more ram is available for engines in analysis. Also there is no worries about 99% ram usage.

For example with syzygy-6, ram usage can go to 98 or 99% without sufficient ram installed. Windows don't perform well if ram is filled up.

[Laskos]

"Does not eat RAM during analysis"... Isn't that the same thing as saying "Fails to profit from RAM that otherwise would be idle, and just leaves that go to waste"?

Well, RAM usage is the property of an engine, like hash. Engine with larger hash is often favored. Another point: have you ran 6-men Syzygy from fast SSD on 8GB RAM machine (with say another 8GB cache on HDD) for several hours from close to endgame positions? It becomes practically unresponsive. What I did, I now have 16GB RAM and 0 cache, but my machine sometimes is in danger to simply nastily crash due to Syzygy.

Sure, otherwise, Syzygy are by far the best endgame bases for all practical purposes. DTM shortened in say SF9, with Ronald's patch. The best implementation is in Texel of Peter, who made use of Syzygy + Gaviota.