3 ms·
Chess move compression was an interesting topic back when the games were stored on 360k floppy disks. Nowadays every master chess game ever played in the histor
by slm_HN 11y ago
Chess move compression was an interesting topic back when the games were stored on 360k floppy disks. Nowadays every master chess game ever played in the history of chess fits easily on one DVD, uncompressed.
So it's not clear what the point of compressing the moves, especially since at some points the article is concerned about size and sometimes about speed. If it's just an intellectual exercise then consider the following scheme:
Generate the legal moves for a position, then sort them. However don't sort them using a naive method like alphabetical order. Instead sort them in order of likeliness of being played. For example moves that capture the last moved piece are at the top of the list. So for example 1.e4 d5, now the first move in the list would be exd5, capturing the last moved piece. So the move exd5 can be encoded in 1 bit. Now imagine a 40 move game where every move played was the first one on the sorted list. This takes 80 bits to store the entire game. Of course moves farther down the list take more bits to encode.
This is similar to one of the schemes in the article, but the article gets hung up with fixing bit sizes rather than just using the exact number of bits required for each move which results in variable bit lengths for each move.
This is, more or less, the scheme Chessbase first used for their data files almost 30 years ago.
- steveridout 11y ago> Nowadays every master chess game ever played in the history of chess fits easily on one DVD, uncompressed. If someone created a mobile app containing this database, I would certainly appreciate those multiple gigabytes of data being compressed.
- billforsternz 11y agoIt's not quite that simple. I discuss variable bit schemes like the one you describe in the article. Your suggested scheme is an extreme variant, and it's by no means obvious it's optimal. I'd be prepared to be convinced if some statistical evidence were presented. As I say, designing these schemes is "a lot of fun". Under your scheme; 1st move in the list takes one bit (great) 2nd move in the list takes two bits (good) 3rd move in the list takes three bits (okay) 4th move in the list takes four bits (average) 5th move in the list takes five bits (worse than average) ...etc There are many positions where there are lots of plausible moves, in such positions your scheme could use many bits. I would estimate your scheme would take around 4 bits per move on average, much like the similar scheme I describe. You are correct that a good modern database of 5 million plus games stored uncompressed occupies about 5 gigabytes or 1 DVD. Clearly compression is very useful for online distribution, which is what people expect these days. Chessbase compression reduces the 5 gigs to 0.5 gigs, about 10:1. The scheme I describe is a nice compromise between performance and maximum compression. In my database program I achieve much faster position search than Chessbase. I am trying to achieve similar results without massive position indexes, and my performant compressed move scheme is a key ingredient in my work. Edit: But as I state in the intro to my article, I am just an amateur playing around - I am not expecting to 'beat' Chessbase. I'll settle for having some innovative aspects to my program.
- billforsternz 11y agoToo late to edit my earlier reply, so I'll reply again instead. I've subsequently learned more, mainly from a discussion with "mxtppy" in the programming subreddit. I've updated my blog post with a new section "One Move in 2 Bits, Maybe?" to reflect my improved understanding.