Chess Move Compression

Love the disclaimer at the start.

Zbg Xyz proof of work steganography. Heliox 2010.

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.

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-...

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.