New 6-piece tablebases

[syzygy]

Ron - what are these magic tablebases called?

Good question. I've always called my engine Sjaak, but this name is not unique anymore. It's playing on FICS as TrojanKnight. TrojanKnight tablebases? Trojanbases?

syzygybases?

Fine with me as well. Syzygy bases actually exist in mathematics.

[Gerd Isenberg]

Ron - what are these magic tablebases called?

Good question. I've always called my engine Sjaak, but this name is not unique anymore. It's playing on FICS as TrojanKnight. TrojanKnight tablebases? Trojanbases?

syzygybases?

Fine with me as well. Syzygy bases actually exist in mathematics.

Apparently quite sophisticated ...
http://en.wikipedia.org/wiki/Syzygy_%28mathematics%29

Buchberger's algorithm for computing Gröbner bases allows to compute the first syzygy module: The reduction to zero of the S-polynomial of a pair of polynomials in a Gröbner basis provides a syzygy, and these syzygies generate the first module of syzygies.

Somehow it sounds like generating endgame tablebases

[tano-urayoan]

Aye, understand the logic behind it. Just been itching for 7-men data for nearly a decade now. Meant no disrespect toward Mr Ronald de Man. Was just curious .

There are already 7 pieces tablebases available but just accessible via internet using convekta software, either latest Aquarium or Chess Assistant.

Here is the info.

[jshriver]

There are already 7 pieces tablebases available but just accessible via internet using convekta software, either latest Aquarium or Chess Assistant.

Here is the info.

Interesting... knew they existed but thought only for rare cases or lots of money to actually access them.

This might be the push I need to get Aquarium or one of the engines that comes bundled with it

[stevemulligan]

Nice work Ronald! How can they be so much smaller than the compressed Gaviota tables?

[syzygy]

Nice work Ronald! How can they be so much smaller than the compressed Gaviota tables?

There are several reasons:

- Distance to zeroing move (DTZ) instead of distance to mate (DTM).

- DTZ and WDL (win/draw/loss) information is stored in separate tables without duplicating the WDL information in the DTZ table. This allows me to store for DTZ only the "smaller half" of white-to-move / black-to-move information, because DTZ is only probed at the root.

- Tricks in encoding WDL information. Positions with a winning capture are stored as "don't care". Something similar (but more complicated) for positions with a drawing capture. Of course illegal positions (side to move can capture the king) are set to don't care as well. The compression algorithm sets these values to what compresses best. The cost is a round of captures in the probing code, which I consider acceptable because these probe into much smaller tables which may be assumed to be cached in RAM.

- Tricks in encoding DTZ information. As already mentioned WDL information is removed, so draws are "don't care" and only the distance to win or loss is stored. Positions with a winning capture or pawn move are set to don't care, as this can be tested easily when probing.

- My compression algorithm seems to do quite well. It's not a general purpose compressor, so it is hard to compare to e.g. LZMA used by Gaviota, but LZMA and other compressors that compress "online" (i.e. read input and produce output in a single pass) suffer from small block sizes. My compressor constructs a (small) dictionary on the basis of the whole table which results in a sort of "random access" compression/decompression with very small blocks (at most 64 bytes for WDL, at most 1024 bytes for DTZ). The only efficiency lost by making blocks smaller is a few bits lost at the end of each block (because the next symbol does not fit anymore).

- The order of piece types in the indexing function can have a large impact on compression ratio. My indexing function therefore allows for many permutations of piece types. Before compressing a table a search is done for a good permutation (by testing on a subset of the data).

The size of my tables is slightly increased by the inclusion of information on the 50-move rule (without losing the ability to play out wins affected by the 50-move rule), but my compression deals with this efficiently and it adds something that I think was not available before.

Size is one thing, probing overhead another. Throwing away the "bigger half" of DTZ of course increases probing overhead of DTZ, but this is only done at the root so I find this completely acceptable. The trick with winning/drawing captures has a cost when probing WDL, but it should not lead to more I/O and it reduces the size quite a bit, which means that more compressed data can be cached and I/O is reduced. Overall I think it is a win. I don't cache decompressed data but instead make use of the small block size and the fact that it is faster to extract a single value from a block than to decompress the whole block.

[stevemulligan]

I'm not sure I understand DTZ? What is a zeroing move?

Don't you need the DTM to determine which is the best? Like if there are 2 moves where you can get checkmate but one of them is in 35 moves and the other is in 10? Is DTM derived from DTZ somehow?

[michiguel]

Nice work Ronald! How can they be so much smaller than the compressed Gaviota tables?

There are several reasons:

- Distance to zeroing move (DTZ) instead of distance to mate (DTM).

- DTZ and WDL (win/draw/loss) information is stored in separate tables without duplicating the WDL information in the DTZ table. This allows me to store for DTZ only the "smaller half" of white-to-move / black-to-move information, because DTZ is only probed at the root.

- Tricks in encoding WDL information. Positions with a winning capture are stored as "don't care". Something similar (but more complicated) for positions with a drawing capture. Of course illegal positions (side to move can capture the king) are set to don't care as well. The compression algorithm sets these values to what compresses best. The cost is a round of captures in the probing code, which I consider acceptable because these probe into much smaller tables which may be assumed to be cached in RAM.

- Tricks in encoding DTZ information. As already mentioned WDL information is removed, so draws are "don't care" and only the distance to win or loss is stored. Positions with a winning capture or pawn move are set to don't care, as this can be tested easily when probing.

- My compression algorithm seems to do quite well. It's not a general purpose compressor, so it is hard to compare to e.g. LZMA used by Gaviota, but LZMA and other compressors that compress "online" (i.e. read input and produce output in a single pass) suffer from small block sizes. My compressor constructs a (small) dictionary on the basis of the whole table which results in a sort of "random access" compression/decompression with very small blocks (at most 64 bytes for WDL, at most 1024 bytes for DTZ). The only efficiency lost by making blocks smaller is a few bits lost at the end of each block (because the next symbol does not fit anymore).

- The order of piece types in the indexing function can have a large impact on compression ratio. My indexing function therefore allows for many permutations of piece types. Before compressing a table a search is done for a good permutation (by testing on a subset of the data).

The size of my tables is slightly increased by the inclusion of information on the 50-move rule (without losing the ability to play out wins affected by the 50-move rule), but my compression deals with this efficiently and it adds something that I think was not available before.

Size is one thing, probing overhead another. Throwing away the "bigger half" of DTZ of course increases probing overhead of DTZ, but this is only done at the root so I find this completely acceptable. The trick with winning/drawing captures has a cost when probing WDL, but it should not lead to more I/O and it reduces the size quite a bit, which means that more compressed data can be cached and I/O is reduced. Overall I think it is a win. I don't cache decompressed data but instead make use of the small block size and the fact that it is faster to extract a single value from a block than to decompress the whole block.

Congratulations!

I am busy now to take a close look a this, but sounds like a very interesting approach. I know that you must invested a lot of effort in this.

Miguel

[michiguel]

I'm not sure I understand DTZ? What is a zeroing move?

Don't you need the DTM to determine which is the best? Like if there are 2 moves where you can get checkmate but one of them is in 35 moves and the other is in 10? Is DTM derived from DTZ somehow?

It is the distance to a move that resets the "50 move clock". That is, distance to the next capture, promotion, or pawn move that wins. You have to choose the lowest DTZ with the highest 50 move clock (o lowest material, more advanced pawns) and you will always make progress.

Miguel

[syzygy]

I'm not sure I understand DTZ? What is a zeroing move?

Captures and pawn moves (including promotions) are zeroing moves, because they reset ("zero") the 50-move counter.

Don't you need the DTM to determine which is the best? Like if there are 2 moves where you can get checkmate but one of them is in 35 moves and the other is in 10? Is DTM derived from DTZ somehow?

If you want the fastest checkmate, then you need DTM. But you don't need DTM to make sure that you can always play out a win. All you need is the guarantee that you make progress towards the win. DTZ gives this guarantee: with every non-zeroing move it decreases, and zeroing moves either leave less pieces on the board or more advanced pawns.

Actual play along DTZ-optimal lines can be quite ugly, but this can be handled by letting the engine, once the game has reached a tablebase position, do short searches on the subset of winning moves and switch to DTZ-optimal play once the engine stops making progress (e.g. a position is repeated or the number of moves left before the 50-move rule kicks in starts to approach the DTZ value for the position).

One problem with DTM is that a winning position might be drawn due to the 50-move rule. My tables guarantee that this cannot happen. Using my tables an engine will win positions that will be drawn with DTM-optimal play.