4 ms·

Article author here: I do mention the idea of using a chess engine to improve compression. I propose a simple scheme and calculate/estimate my scheme would comp

Article author here: I do mention the idea of using a chess engine to improve compression. I propose a simple scheme and calculate/estimate my scheme would compress moves in a reasonably played game to about 3.9 bits each on average. I am sure it's possible to do better, but I suspect you'd hit diminishing returns before you get close to 3 bits. I really should have included something about adding an opening book as I thought about that quite a lot. My conclusion was that an opening book is not going to be a really dramatic win. A simple scheme might encode say 64K opening sequences using 2 bytes, and save an average of perhaps 10 (half) moves. So a saving of 10*4 - 16 = 24 bits, spread over an average of 80 (half) moves. So about 0.3 bits per move. You might question my estimate of 10 half moves max, but it's an educated guess. One thing I've discovered whilst working on my chess database is that the standard tabiya positions are reached by huge numbers of different transposition possibilities. See my blog post at https://triplehappy.wordpress.com/2013/11/13/statistics-and-transpositions/ https://triplehappy.wordpress.com/2013/11/13/statistics-and-... This means that the standard canonical way of reaching a well known position doesn't serve as a good proxy for the start of all the games that include that position.

bo1024 11y ago
Sorry I missed the engine part!
howeman 11y ago
In the "Checkers is solved" paper, they state "The complete 10-piece databases contain 39 trillion positions (Table 1). They are compressed into 237 gigabytes, an average of 154 positions per byte!" Do you have any idea how this would be done? It seems crazy.
- mappu 11y ago
  Probably just standard compression techniques - the linked article is mostly discussing a standalone move, but there are a lot more options available when working with large strings of text (dictionaries, BWT, arithmetic coding, ...). The downside is a lack of individual byte accessing without a lot of surrounding decompression work, but it'd be appropriate for stream processing In fact the best compressed size is probably found by reducing some of the clever tricks in the article in order to expose more structure to a general compressor. Similar to running `precomp` or `antiX` before solid-packing multiple already-compressed files.
- billforsternz 11y ago
  That's interesting, as you say it sounds like magic. I will have a look at the paper when I get a chance. No doubt there is some amazing tree data structures involved. That's what chess endgame tablebases use, but it's not something I pretend to understand.

bo1024 11y ago

Sorry I missed the engine part!

howeman 11y ago

In the "Checkers is solved" paper, they state "The complete 10-piece databases contain 39 trillion positions (Table 1). They are compressed into 237 gigabytes, an average of 154 positions per byte!" Do you have any idea how this would be done? It seems crazy.

mappu 11y ago
Probably just standard compression techniques - the linked article is mostly discussing a standalone move, but there are a lot more options available when working with large strings of text (dictionaries, BWT, arithmetic coding, ...). The downside is a lack of individual byte accessing without a lot of surrounding decompression work, but it'd be appropriate for stream processing In fact the best compressed size is probably found by reducing some of the clever tricks in the article in order to expose more structure to a general compressor. Similar to running `precomp` or `antiX` before solid-packing multiple already-compressed files.
billforsternz 11y ago
That's interesting, as you say it sounds like magic. I will have a look at the paper when I get a chance. No doubt there is some amazing tree data structures involved. That's what chess endgame tablebases use, but it's not something I pretend to understand.