Improved chess game compression (2018)
lichess.org
Improved chess game compression (2018)
1–10 of 36 posts
Re: Improved chess game compression (2018)
#2The 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.
Re: Improved chess game compression (2018)
#3The to slow approach is fun. If you freeze and use a reasonable engine a bit string could represent which moves match the engine move. (lets call it block 1) The missing moves could be 3 bit numbers like 000 for second best engine move, 001 for 3rd, 010 for 4th, 011 for 5th, 100 for 6th best move, 101 for 7th, 110 for 8th and 111 for other moves. (block 2) The other moves are simply put like E4, E24 or NF3G5.(block 3)
Re: Improved chess game compression (2018)
#4I have always loved just how much of computer science you could learn by doing nothing but working on chess your entire life.
Re: Improved chess game compression (2018)
#5I have always loved just how much of computer science you could learn by doing nothing but working on chess your entire life.
Usually the earliest computers were made so that they can play chess and "crack" it
Re: Improved chess game compression (2018)
#6The to slow approach is fun. If you freeze and use a reasonable engine a bit string could represent which moves match the engine move. (lets call it block 1) The missing moves could be 3 bit numbers like 000 for second best engine move, 001 for 3rd, 010 for 4th, 011 for 5th, 100 for 6th best move, 101 for 7th, 110 for 8th and 111 for other moves. (block 2) The other moves are simply put like E4, E24 or NF3G5.(block 3…
In that case decompression might use significant CPU time, the cost of which can offset the storage savings.
Re: Improved chess game compression (2018)
#7Hmm, 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 should be at the same kind of level as you get by just having a text file with one line per game, and gzipping the whole thing. I'd expect it to be an order of magnitude smaller than per-document compression.
Re: Improved chess game compression (2018)
#8The to slow approach is fun. If you freeze and use a reasonable engine a bit string could represent which moves match the engine move. (lets call it block 1) The missing moves could be 3 bit numbers like 000 for second best engine move, 001 for 3rd, 010 for 4th, 011 for 5th, 100 for 6th best move, 101 for 7th, 110 for 8th and 111 for other moves. (block 2) The other moves are simply put like E4, E24 or NF3G5.(block 3…
For optimum compression with this approach, you'd use an engine that generated the most likely moves (perhaps given the time control and the players' ratings, since Lichess stores those anyway), not the strongest moves. That might not look much like a regular chess engine.
Re: Improved chess game compression (2018)
#9Re: Improved chess game compression (2018)
#10This 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 liklihood estimate that the printed characters were particular glyphs. Despite very low quality of the printing, the journal had very high quality editing. The source material was self consistent. Completely illegible characters could mostly be filled in as the sensible game moves that were allowed. It took hundreds of hours of human review time to find a single OCR mistake from this process!