Syzygy endgame tables: Generation and first impressions

[syzygy]

Also is still unclear for me if Syzygy Bases are a sort of bitbases ( loaded into the RAM memory) with general informations (sort win-draw-loss) or show us the distance to mate (access at the root) ? Maybe both ?

Both, sort of.

If the root position is not yet in the tablebases, then the engine should use the WDL tables. These are a kind of bitbases, but with win/draw/loss information including information on whether the 50-move rule affects the win or loss. Engines can do with the 50-move rule information whatever they want (e.g. ignore it for correspondence games once ICCF has abolished the 50-move rule for tablebase positions, which appears to be the silly plan).

Once the root position is in the tablebases, the engine should use the DTZ tables. These tables give the distance to the earliest winning capture or pawn move. So they are not distance-to-mate (DTM) but distance-to-zero (zeroing move: captures and pawn moves "zero" the 50-move counter).

My adaptation of Stockfish does exactly this, but at the root does not automatically play the winning move with the lowest DTZ value. Instead, it takes all the winning moves (taking into account the 50-move rule) and then searches among those. The result is more natural play (not giving preference to pawn moves only because they have DTZ = 1), but the engine might show confusing scores (in particular if the win is still too deep for the engine to see). When I find some time I will try to improve this.

See also under "What to expect" here: https://github.com/syzygy1/Stockfish

[Vinvin]

...and I expect the full 7-piece DTZ set to be of similar size or maybe even smaller. In some years this might be practical.

Note that all the DTZ files can be drastically reduced by only storing partial information : reduce the file by 4 with only storing mates in 4, in 8, in 12, ... the engine would easily connect the winning nodes by tree search.

[Vinvin]

...and I expect the full 7-piece DTZ set to be of similar size or maybe even smaller. In some years this might be practical.

Note that all the DTZ files can be drastically reduced by only storing partial information : reduce the file by 4 with only storing mates in 4, in 8, in 12, ... the engine would easily connect the winning nodes by tree search.

More precisely I mean : Divide by 4 by storing only winning positions and mate in 2, 4, 6, 8, ...

[syzygy]

...and I expect the full 7-piece DTZ set to be of similar size or maybe even smaller. In some years this might be practical.

Note that all the DTZ files can be drastically reduced by only storing partial information : reduce the file by 4 with only storing mates in 4, in 8, in 12, ... the engine would easily connect the winning nodes by tree search.

But that would need a lot of probes into the DTZ tables which I want to avoid.
I might still use this technique though for 7-piece tables with very large max DTZ. In principle my format allows encoding very high values, but my compressor would have to be adapted. It seems easier, and acceptable, to divide DTZ by 2. (And this would only have to be done for positions that are drawn by the 50-move rule anyway.)

For saving space I see more in setting all positions with DTZ <= 10 (or so) to the same value. Those can than be resolved by searching and probing into the WDL tables.

[syzygy]

...and I expect the full 7-piece DTZ set to be of similar size or maybe even smaller. In some years this might be practical.

Note that all the DTZ files can be drastically reduced by only storing partial information : reduce the file by 4 with only storing mates in 4, in 8, in 12, ... the engine would easily connect the winning nodes by tree search.

More precisely I mean : Divide by 4 by storing only winning positions and mate in 2, 4, 6, 8, ...

The idea of storing only a subset of positions is flawed. You need to store a value for each and every position. But if a value does not matter, you can store any value, for example a value that gives good compression. But you always need to be sure that you can reconstruct the correct value. Storing a random value for mate in 3 positions will leave you no way to reconstruct that it is a mate in 3 position (unless you are prepared to do a 5-ply search, but then you have problems for mate in 13 etc. or you could as well not use a tablebase at all). Storing a random value for draws is fine in my case, because the WDL tables already encode the position as drawn.

I store correct values for both winning and losing positions in DTZ tables, because I only store one half of the table (either wtm or btm). (For WDL I store both sides for speed reasons.)

The DTZ <= 10 idea would work, but complicate stuff for engines. I considered the current DTZ size to be sufficiently small to avoid those complications.

Other ideas likely don't work or would be a bad trade off. You can be sure I did not leave any big free gains on the table.

[IQ]

Another compression idea would be to do a small search and/or SEE, which would result in a postive,0, or negative eval (without any TB access). If positve and position is winning (according to TB) encode with bit that maximal compressen, if 0 and position is draw do the same. Only if eval and tablebase info disagree store all info as ususally necessary. I could imagine that this would compress a whole lot of positions away.... This small search should be really brief and simplified (most likely only material balance suffices), like a 2 ply + SEE

On second thought, maybe storing if that search is sufficient or not, nullifies all gains- so its probably a bad idea - should only be tested with arithmetic coding, as huffman ist probably not efficient enough. But then again arithmetic coding is more computationally demaning.

[syzygy]

Another compression idea would be to do a small search and/or SEE, which would result in a postive,0, or negative eval (without any TB access). If positve and position is winning (according to TB) encode with bit that maximal compressen, if 0 and position is draw do the same.

I already do a round of captures (if there are any) to see if there is a winning capture or a drawing capture. If there is a winning capture, the value stored is whatever compresses best. If there is a drawing capture and the position is a draw, the value stored is either loss or draw, whichever compresses best. (And there are more possibilities if you also take into account wins/losses that are drawn by the 50-move rule.)

Note that "whatever compresses best" is actually not so easy to determine at all. The first thing that comes to mind is to select the value with the highest frequency for the whole table. This is a reasonable choice, but more local heuristics give considerably improved compression.

When I had almost finalised my compression algorithm I thought of a new heuristic to try. On the first two tables it performed worse, so I was already happy that I could dismiss the idea. But on the third table I tried it did very well. This was very annoying, because now I might have to try both the new and old heuristic on each table and pick the one that works best for that table. In the end I managed to refine the new heuristic so that it worked significantly better on practically all tables. I believe this reduced the 5-piece tables more than 10% in size.

On second thought, maybe storing if that search is sufficient or not, nullifies all gains- so its probably a bad idea - should only be tested with arithmetic coding, as huffman ist probably not efficient enough. But then again arithmetic coding is more computationally demaning.

Huffman is fine in my case, because I do not apply it directly to win/draw/loss values but to up to 4095 symbols that encode strings of win/draw/loss values.

[IQ]

Could you clarify you point about Huffman vs. Arithmetic Compression. As Huffman is only a special case of Arithmetic encoding the latter should be better in almost all cases. Only when the frequencies of the symbols are powers of 1/2 huffman is at best equal. I imagined you opted for Huffman because its easier to implement. Differences might be small though - but in view of the 7 piece bases, maybe something to think about.

Anyhow: Syzygybases are the most efficient, most-thought out (cursed wins, 50 move rule) 6 piece bases devised up to now. I cannot praise them enough! Really a fantastic Job! I just hope the Stockfish team decides one day to use them in their main branch, this would simplify so much of the endgame code, improve parameter tuning (no more regression from endgame interdependencies), and improve endgame play. The only drawback is size - but as nobody really needs maximum strength on hand held devices - its a small price to pay.

Another compression idea would be to do a small search and/or SEE, which would result in a postive,0, or negative eval (without any TB access). If positve and position is winning (according to TB) encode with bit that maximal compressen, if 0 and position is draw do the same.

I already do a round of captures (if there are any) to see if there is a winning capture or a drawing capture. If there is a winning capture, the value stored is whatever compresses best. If there is a drawing capture and the position is a draw, the value stored is either loss or draw, whichever compresses best. (And there are more possibilities if you also take into account wins/losses that are drawn by the 50-move rule.)

Note that "whatever compresses best" is actually not so easy to determine at all. The first thing that comes to mind is to select the value with the highest frequency for the whole table. This is a reasonable choice, but more local heuristics give considerably improved compression.

When I had almost finalised my compression algorithm I thought of a new heuristic to try. On the first two tables it performed worse, so I was already happy that I could dismiss the idea. But on the third table I tried it did very well. This was very annoying, because now I might have to try both the new and old heuristic on each table and pick the one that works best for that table. In the end I managed to refine the new heuristic so that it worked significantly better on practically all tables. I believe this reduced the 5-piece tables more than 10% in size.

On second thought, maybe storing if that search is sufficient or not, nullifies all gains- so its probably a bad idea - should only be tested with arithmetic coding, as huffman ist probably not efficient enough. But then again arithmetic coding is more computationally demaning.

Huffman is fine in my case, because I do not apply it directly to win/draw/loss values but to up to 4095 symbols that encode strings of win/draw/loss values.

[syzygy]

Could you clarify you point about Huffman vs. Arithmetic Compression. As Huffman is only a special case of Arithmetic encoding the latter should be better in almost all cases. Only when the frequencies of the symbols are powers of 1/2 huffman is at best equal. I imagined you opted for Huffman because its easier to implement. Differences might be small though - but in view of the 7 piece bases, maybe something to think about.

It is true that Arithmetic Compression in almost all cases beats Huffman in compression ratio because unlike Huffman it can encode symbols in a fractional number of bits, but the difference is small on large alphabets and Huffman is significantly faster to decode.

Anyhow: Syzygybases are the most efficient, most-thought out (cursed wins, 50 move rule) 6 piece bases devised up to now. I cannot praise them enough! Really a fantastic Job!

Thanks

[Laskos]

I got an amazing result in some 2,600 games, 15 +/- 8 Elo (2SD) points benefit from 3-5 Syzygy on HD using Stockfish 21.10.2013 at 15+0.15 time control. I have never seen such improvement with any other TBs. On SSD they are probably even better. Kudos to Ronald.