New 6-piece tablebases

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

syzygy
Posts: 5646
Joined: Tue Feb 28, 2012 11:56 pm

New 6-piece tablebases

Post by syzygy »

I have just released my tablebase generator for up to 6 pieces on github:
https://github.com/syzygy1/tb

It generates two sets of files:
- WDL files (extension: .rtbw) storing win/draw/loss information for access during search.
- DTZ files (extension: .rtbz) storing distance-to-zero information for access at the root.

In addition to win/draw/loss information, the WDL files also store whether the win or loss can be enforced within 50 moves.

The tables use custom compression. Total compressed size:

Code: Select all

                       WDL          DTZ
up to 5 pieces       378 MB        561 MB
up to 6 pieces       68.3 GB       81.9 GB
Generation is done (almost) completely in RAM and is fully multithreaded. For 6 pieces, it requires a system with at least 32 GB of RAM. On my system (6-core i3930K @ 4.2Ghz, 64 GB) all 6-piece tables were generated in less than 5 days. At least for now the generator requires Linux and gcc.

Probing code is included, but it requires some work to add it to an engine. As a proof of concept I have adapted the probing code to Stockfish. The probing code is fully multithreaded as well.

My engine (playing on FICS as TrojanKnight(C)) has been using these tables since a couple of months quite successfully. With the WDL tables stored on SSD, it is possible to probe the tables at all depths without much slowdown (I don't probe in qsearch).

The license for the generator is GPLv2. The probing code is released without restrictions. So anyone wanting to add support for these tables to his/her engine is free to do so.
User avatar
nanochess
Posts: 64
Joined: Thu Feb 19, 2009 5:34 pm
Location: Mexico, Mexico

Re: New 6-piece tablebases

Post by nanochess »

Very interesting! I'll give a look

Thanks for sharing :)
All good things are difficult to achieve.
Toledo Nanochess book http://www.amazon.com/Toledo-Nanochess- ... 1304864375
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: New 6-piece tablebases

Post by lucasart »

syzygy wrote:I have just released my tablebase generator for up to 6 pieces on github:
https://github.com/syzygy1/tb

It generates two sets of files:
- WDL files (extension: .rtbw) storing win/draw/loss information for access during search.
- DTZ files (extension: .rtbz) storing distance-to-zero information for access at the root.

In addition to win/draw/loss information, the WDL files also store whether the win or loss can be enforced within 50 moves.

The tables use custom compression. Total compressed size:

Code: Select all

                       WDL          DTZ
up to 5 pieces       378 MB        561 MB
up to 6 pieces       68.3 GB       81.9 GB
Generation is done (almost) completely in RAM and is fully multithreaded. For 6 pieces, it requires a system with at least 32 GB of RAM. On my system (6-core i3930K @ 4.2Ghz, 64 GB) all 6-piece tables were generated in less than 5 days. At least for now the generator requires Linux and gcc.

Probing code is included, but it requires some work to add it to an engine. As a proof of concept I have adapted the probing code to Stockfish. The probing code is fully multithreaded as well.

My engine (playing on FICS as TrojanKnight(C)) has been using these tables since a couple of months quite successfully. With the WDL tables stored on SSD, it is possible to probe the tables at all depths without much slowdown (I don't probe in qsearch).

The license for the generator is GPLv2. The probing code is released without restrictions. So anyone wanting to add support for these tables to his/her engine is free to do so.
Impressive work. Congratulations!

How does the size of 5-men table size base compare with: the Nalimov TB ? the Gaviota TB ? And in terms of "average probing speed" ?

I'm wondering, if I ever implement TB probing in DiscoCheck, which one to choose from. The smaller/faster the better :D
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
mar
Posts: 2592
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: New 6-piece tablebases

Post by mar »

Truly impressive Ronald.
If I understand correctly you first probe WDL and then DTZ table to make progress?
Having such 5-men info fit below 1 gigabyte is awesome, DTM can't beat that for sure, but it would be unfair to compare since DTM contains more information.
Thanks for sharing.
User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 12:00 pm
Location: Slovakia, EU

Re: New 6-piece tablebases

Post by rvida »

syzygy wrote: The tables use custom compression. Total compressed size:

Code: Select all

                       WDL          DTZ
up to 5 pieces       378 MB        561 MB
up to 6 pieces       68.3 GB       81.9 GB
Is the custom compression scheme any better than LZMA (which is used in Gaviota) ?
AlvaroBegue
Posts: 931
Joined: Tue Mar 09, 2010 3:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: New 6-piece tablebases

Post by AlvaroBegue »

Perhaps a bit more googling on my part could answer this, but I couldn't find it after a few minutes: What do people mean by "distance to zero"? Is it what I would call "distance to capture or pawn move"?
User avatar
hgm
Posts: 28010
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New 6-piece tablebases

Post by hgm »

Indeed. Zero refers to zeroing of the 50-move counter.
syzygy
Posts: 5646
Joined: Tue Feb 28, 2012 11:56 pm

Re: New 6-piece tablebases

Post by syzygy »

lucasart wrote:How does the size of 5-men table size base compare with: the Nalimov TB ? the Gaviota TB ? And in terms of "average probing speed" ?
The 5-piece Nalimov TB are over 7 GB. I believe the 6-piece are over 1.2 TB (and those lack the 5v1 tables).
The 5-piece Gaviota TB are 6.5GB with LZMA compression, see here.

Average probing speed of my tables should be considerably better than that of Nalimov tables, but to be honest I have not measured it. But probing 1.2 TB Nalimov 6-piece tables will of course lead to much more disk trashing than probing 68.3 GB of tables. And 68.3 GB on SSD is much more affordable than 1.2 TB on SSD.
syzygy
Posts: 5646
Joined: Tue Feb 28, 2012 11:56 pm

Re: New 6-piece tablebases

Post by syzygy »

mar wrote:If I understand correctly you first probe WDL and then DTZ table to make progress?
Correct. During the search only the WDL tables are accessed. Once a position with 6 or fewer pieces is on the board, the DTZ tables are used to make progress.

To make sure the engine makes progress towards a tablebase win, the search should treat tablebase positions that are won or lost similar to mate positions, but using a different range of values.

Of course pure DTZ-optimal play (i.e. minimaxing the number of moves to the next capture or pawn move by either side) can be very unnatural, so it might be desirable to let the engine do searches on the winning moves until it becomes clear that insufficient progress is being made and only then switch to DTZ-optimal play (e.g. by detecting repetitions and monitoring the 50-move counter).

The main reason for DTZ is clearly size, but also important is the fact that DTZ plays well with the 50-move rule. Actually it is not really DTZ but what I would call DTZ50+. For a position that is won or lost under the 50-move rule, my tables give the number of moves to the next zeroing move with optimal play respecting the 50-move rule (the "DTZ50" value). For a position that is drawn under the 50-move rule, but won or lost without the 50-move rule, my tables give the number of moves either to a position that is won or lost under the 50-move rule, or to a zeroing move leading to a position that is drawn under the 50-move rule but won or lost without it.

This may look a bit complicated, but the result is that when ignoring the 50-move rule, a winning path can be found for all positions that are won, and when respecting the 50-move rule, all positions that are won under the 50-move rule can be won and all positions that are drawn under the 50-move rule (but otherwise lost) can be drawn.

Similarly, the WDL tables are in fact WDL50+ tables. The probe returns -2,-1,0,1,2 depending on whether the position is lost under the 50-move rule, lost but drawn under the 50-move rule, drawn, won but drawn under the 50-move rule, won under the 50-move rule.
syzygy
Posts: 5646
Joined: Tue Feb 28, 2012 11:56 pm

Re: New 6-piece tablebases

Post by syzygy »

rvida wrote:
syzygy wrote: The tables use custom compression. Total compressed size:

Code: Select all

                       WDL          DTZ
up to 5 pieces       378 MB        561 MB
up to 6 pieces       68.3 GB       81.9 GB
Is the custom compression scheme any better than LZMA (which is used in Gaviota) ?
My compression scheme allows for compressed blocks of just 64 bytes that can be decompressed quickly, which means that there is no need to cache uncompressed data.

In addition, my compression scheme allows me more control on what to do with "don't care" values. The value of illegal positions can be set to whatever compresses best (which is not necessarily the value occurring with the highest frequency but depends on the neighbouring values). To further improve compression, the WDL probing code does a round of captures and probes the resulting positions (which should be fast because tables with 1 piece less are much smaller and may be assumed to be cached in RAM). This means that for positions with a winning capture I can store whatever I want. For drawn positions with a drawing capture I can store either a loss value or a draw value. (And since WDL50+ is 5-valued there are even more possibilities.) Theoretically this is possible with other compression schemes as well, but it is an integral part of my compression scheme.

Getting DTZ small was done by making them 1-sided (only wtm or only btm, whichever is smaller), storing draws as don't cares, and not storing whether a position wins or loses (since that information is available from the WDL tables). In addition, if a capture or pawn move is winning I store a don't care. Where possible I store distance in number of moves, but where necessary for accurate 50-move rule play I store distance in plies.

I believe the capture resolution idea is from Chinook. It is also used for Robbobases and I would be surprised if the Shredderbases (5-piece WDL, 441 MB 2-sided and 157 MB 1-sided) did not use it as well. Chinook uses a run-length encoding scheme and sets the don't care value to the most frequent of W, D, L (Robbobases is said to do the same). My scheme is a bit more complicated.