I'd suggest a slight change. Code all the pawns into 2 'pieces' and have a special piece for promoting. The 16 moves for the special piece can be an index from a list of possible promotions which is easier to generate and canonicalise than the total move list. This frees up 5 pieces for promoted queens. You could special case the king into the spare entropy in the rooks and bishops to save one more piece.
Chess Move Compression
21–30 of 35 posts
Re: Chess Move Compression
#22"An amusing point is that some moves really would require zero bits – this happens when there is only one legal move in the position, there’s no need to store anything at all in that case."
What if a player decides to resign before making that move?
Re: Chess Move Compression
#23Why does every move have to occupy the same number of bits? That looks inefficient to me. Why not make the movement of pawns occupy fewer and the queen more bits?
Re: Chess Move Compression
#24Very 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…
>A separate comment: I wonder if the time efficiency issues mentioned are really that severe? Since the problem is so small/finite.
Just noticed this. The beauty of my "sweet spot" scheme is that processing these 8 bit moves is almost as quick as processing a straightforward normal move representation (32 bits in my code because I store extra information to make moves "undo-able" - although 16 bits is reasonable). This is important for some of the things I want to do - For example I am experimenting with the idea of implementing a query to search a database of games for a position by literally playing through every game looking for the position (actually the hash of the position). The standard approach is (I think) to index all the positions in the database - which swells the database a lot. If you do a little math you'll see that you need the move processing to be lightning fast for this to be responsive in a multi-million game database. Move processing involving generating move lists in every position would leave the user waiting minutes (maybe hours!).
Re: Chess Move Compression
#25Why does every move have to occupy the same number of bits? That looks inefficient to me. Why not make the movement of pawns occupy fewer and the queen more bits?
In the worst case pawns can be quite demanding - because of underpromotion - there can be up to 12 moves available to a pawn - more than a knight or a king. Of course it is possible to design a scheme where moves take a variable number of bits - I discuss some promising methods in the article. But you will always need 8 bits for some moves (information theory says so) and the beauty of my "sweet spot" scheme is that it simple and quick, whilst still offering reasonable compression.
Re: Chess Move Compression
#26"An amusing point is that some moves really would require zero bits – this happens when there is only one legal move in the position, there’s no need to store anything at all in that case." What if a player decides to resign before making that move?
You would need to indicate the number of moves in the game at the start.
Re: Chess Move Compression
#27Chess 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…
It'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.
Re: Chess Move Compression
#28Earlier 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.
That's interesting, as you say it sounds like magic. I will have a look at the paper when I get a chance. No doubt there is some amazing tree data structures involved. That's what chess endgame tablebases use, but it's not something I pretend to understand.
Re: Chess Move Compression
#29Interesting. What are the practical implications of using 8 vs 12 bits? Does using fewer bits allow chess engines compute more moves ahead?
Re: Chess Move Compression
#30Interesting. What are the practical implications of using 8 vs 12 bits? Does using fewer bits allow chess engines compute more moves ahead?
No, chess engines use the simple highly performant "native" move representations. My 8 bit scheme approaches the performance of native representation, but is only (potentially) useful for other types of applications, particularly chess databases.