4 ms·

Very cool. I suspect that much better compression is possible in principle (not that I'd want to implement it) using an openings book or game database and an en

by bo1024 11y ago

Very cool. I suspect that much better compression is possible in principle (not that I'd want to implement it) using an openings book or game database and an engine. The idea would be to first record the opening played in the game and the move number at which the game deviates. A lot of work would need to go into figuring out the optimal opening-book size. Then, use a deterministic chess engine with predefined parameters at each move, and record which move number on its suggested list was played (e.g. the top move, second move, third move, etc) with a fallback to manually encode the move if none of the top 8 or so moves are played. A more sophisticated version would use arithmetic coding, with the predictions of the next move initially coming from an opening book / game database, then coming from the engine. The idea being that most games you want to compress are at a high enough level that the engine gives good predictions ... perhaps one could even tune the engine's parameters for better results. But again, like I said, it doesn't sound like fun to code. A separate comment: I wonder if the time efficiency issues mentioned are really that severe? Since the problem is so small/finite.

simcop2387 11y ago
That sounds a lot like how LZ77 works, with a predefined dictionary. Probably the only way to do it given the potential symbol size at any given moment.
billforsternz 11y ago
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.
billforsternz 11y ago
>A separate comment: I wonder if the time efficiency issues mentioned are really that severe? Since the problem is so small/finite. Just noticed this. The beauty of my "sweet spot" scheme is that processing these 8 bit moves is almost as quick as processing a straightforward normal move representation (32 bits in my code because I store extra information to make moves "undo-able" - although 16 bits is reasonable). This is important for some of the things I want to do - For example I am experimenting with the idea of implementing a query to search a database of games for a position by literally playing through every game looking for the position (actually the hash of the position). The standard approach is (I think) to index all the positions in the database - which swells the database a lot. If you do a little math you'll see that you need the move processing to be lightning fast for this to be responsive in a multi-million game database. Move processing involving generating move lists in every position would leave the user waiting minutes (maybe hours!).

by bo1024 11y ago

simcop2387 11y ago

That sounds a lot like how LZ77 works, with a predefined dictionary. Probably the only way to do it given the potential symbol size at any given moment.

billforsternz 11y ago

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.

billforsternz 11y ago

>A separate comment: I wonder if the time efficiency issues mentioned are really that severe? Since the problem is so small/finite. Just noticed this. The beauty of my "sweet spot" scheme is that processing these 8 bit moves is almost as quick as processing a straightforward normal move representation (32 bits in my code because I store extra information to make moves "undo-able" - although 16 bits is reasonable). This is important for some of the things I want to do - For example I am experimenting with the idea of implementing a query to search a database of games for a position by literally playing through every game looking for the position (actually the hash of the position). The standard approach is (I think) to index all the positions in the database - which swells the database a lot. If you do a little math you'll see that you need the move processing to be lightning fast for this to be responsive in a multi-million game database. Move processing involving generating move lists in every position would leave the user waiting minutes (maybe hours!).