Nice. A touchy balance between overengineering and too much overengineering. Maybe you could better compress combinations of moves, like exchanges.
If you also store move times, there’s not much of a win to this.
Improved chess game compression (2018)
11–20 of 36 posts
Re: Improved chess game compression (2018)
#12Hmm, a lot of effort to make documents small, but then storing it in mongodb?!?! If size and performance are a focus, just store them in a normal sorted table with compression (e.g. leveldb, or mysql using rocksdb). This means all these small documents can be compressed with repetition between games and not just within each game. And probably much much faster and simpler etc. Basically, the size taken by the database…
I wonder if you could store them as a trie, I feel like that would give you quite good savings given the commonality of openings. Or at least use a trie for the openings and then apply the Huffman coding to the rest of the game and store that separately.
Re: Improved chess game compression (2018)
#13The article includes a brief but clear explanation of Huffman coding. I didn’t understood how it works until now!
Re: Improved chess game compression (2018)
#14Re: Improved chess game compression (2018)
#15Hmm, a lot of effort to make documents small, but then storing it in mongodb?!?! If size and performance are a focus, just store them in a normal sorted table with compression (e.g. leveldb, or mysql using rocksdb). This means all these small documents can be compressed with repetition between games and not just within each game. And probably much much faster and simpler etc. Basically, the size taken by the database…
Postgres TEXT columns are pretty good for compression as well [1]
[1] https://www.postgresql.org/docs/current/storage-toast.html
Re: Improved chess game compression (2018)
#16As I understand it uses the Huffman-code for all moves including the opening moves. Alternatively statistics could be gathered for all first moves, all second moves, etc..., then different Huffmann-code could be applied for opening moves.
I wouldn't be surprised if the statistics for the first few moves were significantly different to the moves deep into the game.
Re: Improved chess game compression (2018)
#17the basis of this algorithm is to rank the possible moves from the current position, then use that to choose a Huffman encoding. In essence, they use a very naive single-move-look ahead chess AI to quickly rank moves giving them a crude measure for how ‘surprising’ a particular move would be at that point in the game.
Interesting question: If you just generated the bit string that corresponded to taking the ‘most obvious move’ according to their heuristics, what game would that play out? In a way, that would be the ‘most obvious chess game’, or perhaps the ‘least creative chess game’...
In theory a more optimal version would be to use a more sophisticated AI to rank the next moves, and even to choose how aggressively to Huffman code the possible options.
In a sense this would measure the information content of a chess game (at least relative to the ‘knowledge’ of that AI) . I wonder what the variance in the number of bits needed to encode various games would tell you about the play style of different players, or the nature of the game, or even the relationship betweeen information theory and creativity....
Re: Improved chess game compression (2018)
#18This reminds me where many years ago I learned about the world record holder for computer optical character recognition (OCR) accuracy. The computer scientists took as a target an eastern European chess journal which printed move-by-move reports of tournament chess matches. They incorporated a crude chess engine in the recognition step estimating the liklihood of next moves and combining that with the OCR engine likl…
That's really awesome, but it feels like cheating to call it the OCR record holder. It's really OCR + context. However it would be interesting if you could apply the same idea at the word and sentence level of written language. I'm guessing there are people that already do this.
Re: Improved chess game compression (2018)
#19The article doesn't say it anywhere but I sure hope all the games are backed up to disk/tape in txt format and that this is just used to keep in-memory DB/memcache size down. Otherwise an interesting article about injecting domain knowledge to improve beyond what's possible with a normal compression algorithm.
Indeed, you can download this backup yourself if you'd like: https://database.lichess.org/
Re: Improved chess game compression (2018)
#20Hmm, a lot of effort to make documents small, but then storing it in mongodb?!?! If size and performance are a focus, just store them in a normal sorted table with compression (e.g. leveldb, or mysql using rocksdb). This means all these small documents can be compressed with repetition between games and not just within each game. And probably much much faster and simpler etc. Basically, the size taken by the database…
I wonder if you could store them as a trie, I feel like that would give you quite good savings given the commonality of openings. Or at least use a trie for the openings and then apply the Huffman coding to the rest of the game and store that separately.
Right. Every possible chess game as a sequence of legal positions can be uniquely enumerated. Per Wikipedia the game-tree complexity is around 10^123, so you'll need about a 124 digit number to represent them. This is as dense as it can possibly get.
On the other hand, lichess supports alternative chess modes and starting boards that may or may not be reachable from the standard initial configuration and legal moves, so this won't work for those use cases.