The history of Syzygy tablebases

Discussion of anything and everything relating to chess playing software and machines.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Re: The history of Syzygy tablebases

Post by Isaac » Wed Mar 07, 2018 7:55 pm

syzygy wrote: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.
Thanks for the reply Ronald. I have another questions:
1)Do you think there is still room for improvement in terms of compression of the Syzygy as they are now? I mean using conventional programming and not quantum computers programming if that makes a difference.
2) How much of a pain would it be to make them perfect in the sense of adding en passant and castling cases?

syzygy
Posts: 4809
Joined: Tue Feb 28, 2012 10:56 pm

Re: The history of Syzygy tablebases

Post by syzygy » Wed Mar 07, 2018 8:32 pm

Nordlandia wrote:Page file advice is good solution but keeping windows oscillating between 97-98% may inflict compromised windows stability.
Did it crash your machine?

syzygy
Posts: 4809
Joined: Tue Feb 28, 2012 10:56 pm

Re: The history of Syzygy tablebases

Post by syzygy » Wed Mar 07, 2018 8:49 pm

Isaac wrote:1)Do you think there is still room for improvement in terms of compression of the Syzygy as they are now? I mean using conventional programming and not quantum computers programming if that makes a difference.
If you let the probing code do more, you can get the TBs smaller. It is a space-time tradeoff.

For example, I believe Shredderbases do not store the correct WDL value for in-check positions. The probing code therefore has to do extra work when probing such positions (basically try all check-evasion moves, probe the resulting positions, and back up the result). Instead of the correct WDL value, the TB can now store a value that compresses better.

My TBs don't use this trick for in-check positions, but it does use the trick for positions with winning and drawing captures.

If there is a winning capture, the position is won and the TB can store any value it likes.

If there is a drawing capture, the position is either won or drawn. If it is won, the TB has to store a win value. If the position is drawn, the TB stores either a draw or a loss value. The probing code knows that a loss in the TB means a draw (because it will see the drawing capture).

(With cursed wins and blessed losses in the mix things get still more complicated, but the principle stays the same.)

The problem with doing this for in-check position is that the probing code would have to probe a number of 6-piece positions to know the value of a 6-piece in-check position. Limiting the trick to captures, the probing code only needs to probe 5-piece positions (and the actual 6-piece position being probed). Probing 5-piece TBs should normally be fast because those files are much smaller and will quickly be cached into RAM.

In principle a TB can be generated on the fly if you don't care about access speed (and memory usage of the probing code), so there is no real lower limit to the size of the compressed TB.
2) How much of a pain would it be to make them perfect in the sense of adding en passant and castling cases?
They contain en passant in the sense that the probing code will return the correct results.

Adding castling requires more code than it is worth (to me), but the generator code is available for anyone who wants to try.

Getting en passant right is absolutely critical for TBs to be useful for game play. Getting castling right is absolutely non-critical.

User avatar
Nordlandia
Posts: 2664
Joined: Fri Sep 25, 2015 7:38 pm
Location: Sortland, Norway

Re: The history of Syzygy tablebases

Post by Nordlandia » Wed Mar 07, 2018 9:02 pm

syzygy wrote:Did it crash your machine?
No, but it's advisable to keep a portion of ram available for the OS. 2% is very little and if any background task start it will interfere.

I tried visualize it at page 2.

Dann Corbit
Posts: 11627
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: The history of Syzygy tablebases

Post by Dann Corbit » Wed Mar 07, 2018 9:14 pm

Short history of the Syzygy tablebase files:

In days of old, we troglodytes stooped over, dragging our knuckles on the ground and chewing up our disks with oceans full of SJE and Nalimov tablebase files.

We would wallow in sweaty pools of lameness as we waited eons for Nalimov permission. This was the true cause of the death of the dinosaurs. They too, waited on permission. In their case, a little too long.

Then came the GTB, and lo, there was much rejoicing. They had many clever features and you did not have to wait to use them. Just plug and go. The sweaty pools of lameness started to evaporate.

Then came the stroke of wonder: Syzygy was born. He was tiny. He was fast. He was easy to use, and purred like a kitten.
But not all was joyous in the swamp. These ( though beauteous and bounteous ) did not give us minimal distance to mate: Only a sure path to victory. Those seeking the utter purity of the whitest possible light and the cleanest loin cloths had their gleaming smiles darkened to the Mona Lisa sort of smiles.

But not all was lost. The shining knight prepared the mighty DTM Syzygy tables. We wait on bended knee. Sir De Man: We wait on thee.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

syzygy
Posts: 4809
Joined: Tue Feb 28, 2012 10:56 pm

Re: The history of Syzygy tablebases

Post by syzygy » Wed Mar 07, 2018 9:56 pm

Nordlandia wrote:
syzygy wrote:Did it crash your machine?
No, but it's advisable to keep a portion of ram available for the OS. 2% is very little and if any background task start it will interfere.
If it gets too low the OS will simply free RAM used for caching TB data. Being low on unused (= useless) RAM is not a problem if there is lots of RAM that can be freed whenever it is needed,

It's not different if you use Nalimov TBs. Windows will use all of its free memory to cache the Nalimov TB files (not to be confused with the engine's TB cache which is caching some of the uncompressed data). When Windows needs memory for something, it will just free some of the file system cache.

The only difference with Syzygy TBs is that the Syzygy probing code accesses that cached data directly without having to uncompress whole blocks. To access the data directly, it maps the cached data into the address space of the engine. And that you can see in the task manager.

Somewhat unfortunately, if Windows gets low on memory and a page file is available, Windows prefers to swap programs to the page file instead of simply freeing some of the RAM used for caching TB files (when they are mapped into the engine's address space). This can be solved by disabling the page cache.

Dann Corbit
Posts: 11627
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: The history of Syzygy tablebases

Post by Dann Corbit » Wed Mar 07, 2018 10:37 pm

For a bit more detail, try this:
https://chessprogramming.wikispaces.com ... /tablebase
Quick, before it evaporates forever.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Post Reply