Love the disclaimer at the start.
Article author here: Hope you are not being sarcastic/ironic. I thought the disclaimer was necessary and complete :-)
Chess Move Compression
11–20 of 35 posts
Re: Chess Move Compression
#12That 8-bit code is clever.
At http://stackoverflow.com/questions/1831386/programmer-puzzle... I suggested combining the sort-the-moves-by-their-evaluation scheme with arithmetic coding according to statistics from a database of games -- how often do people choose the move the engine picks as best? Etc. (It's always easy to propose work for someone else.) (The third paragraph of that answer is irrelevant to real games, which always start from the same configuration.)
Re: Chess Move Compression
#13Very 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 parame…
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…
Sorry I missed the engine part!
Re: Chess Move Compression
#14Very 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 parame…
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…
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.
Re: Chess Move Compression
#15Earlier quoted context omitted.
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…
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.
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.
Re: Chess Move Compression
#16Re: Chess Move Compression
#17Chess 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.
Re: Chess Move Compression
#18Related: 100TB of all the possible 7-piece chess board states and their solutions http://tb7.chessok.com/about-site
Re: Chess Move Compression
#19Chess 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 f…
> 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.
Re: Chess Move Compression
#20I've been doing some spare chess programming on a GUI myself (non-intensive on-off work for 1 year so far) and I decided to stay with the naive method (12 bits, straightforward src and dest squares) for compressing moves. It's obviously easier and faster to implement, I'm not hostage for some wacky bugs I could have done, and it's straightforward to parse and to format to long algebraic form (e2e4), which is the format UCI likes to receive (stockfish, for instance) and to store to a file.
Having said that, I might take a look into this 8 bit format :)