There are several reasons:stevemulligan wrote:Nice work Ronald! How can they be so much smaller than the compressed Gaviota tables?
- 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.