4 ms·

FTA: “But they don’t account for the majority of what I’m storing, which are PGNs.” If they’re storing chess games, why do they try to compress individual move

FTA: “But they don’t account for the majority of what I’m storing, which are PGNs.” If they’re storing chess games, why do they try to compress individual moves? If you compress games, you can get much better compression. For example, in any board position, deterministically order all legal moves (they’re already ignoring some illegal moves in their setup, so I think ignoring all is within the rules of the game), and write down the number of the move made. At game start, that will be an integer between 1 and 20 (16 different pawn moves, 4 different knight moves). Black’s reply similarly will be an integer between 1 and 20. For white’s second move, the maximum will depend on the first move. To compress an entire game, use arithmetic encoding (https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding). If there are, on average, n legal moves per position, that will use 2log n bits per move. https://www.chessprogramming.org/Chess_Position https://www.chessprogramming.org/Chess_Position: “The maximum number of moves per chess position seems 218”, so that will give you less than 8 bits per move. In real life, it probably will be less than 6. The only reason I see why this wouldn’t be an option is performance. Decoding would require move generation and thus be more complex. To improve on that, make a deterministic predictor of how likely moves are and use that to improve on the arithmetic encoder. That probably isn’t worth it, though because of the increased decoding complexity.

marcusbuffett 3y ago
I did end up doing something like this: https://mbuffett.com/posts/compressing-chess-moves-even-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt... You’re spot on about the performance reason I didn’t want to do this originally, but I did some testing and turns out move generation in the library I use is Blazing Fast and wouldn’t be a bottleneck
- crdrost 3y ago
  It's also that PGN allows you to encode illegal moves, which is important if your dataset contains over-the-board games. That you only got to about 10-12 bits per move is actually kind of sad in a way, because it means you're not doing substantially better than the approach where you record a move as just (delete-piece-at ____, recreate-that-piece-at ____) 12-bit pairs, where castles are implicitly only recorded by moving the king further than usual and underpromotion has to be explicitly recorded with an extra 12-bit move that is otherwise semantically impossible.
  - lifthrasiir 3y ago
    Such games should be infrequent enough that you don't need to optimize for them. A single unused code (or for arithmetic coding, a single symbol with a very low but non-zero frequency) can be used as an escape for a full non-optimized move format.
- joshka 3y ago
  I just added your blog to my RSS reader and noticed that your blog title in the RSS is a bit weird (in case you were unaware): <title>Posts on A blog</title> <link>https://mbuffett.com/posts/</link> <description>Recent content in Posts on A blog</description>
- lifthrasiir 3y ago
  You don't seem to have a public repository for the code described in your posts (presumably a part of Chessbook?), but you might be using a textbook arithmetic coding algorithm which maintains both lower and upper bounds and does a renormalization by comparing topmost bits. If it's the case rANS would be much simpler to write and more efficient [1]. If your AC code is already well-optimized, there is not much reason to switch though. [1] Fabian Giesen's sample implementation is already as good as is, and also contains a good alias table implementation if you want multi-symbol inputs: https://github.com/rygorous/ryg_rans/blob/master/rans_byte.h https://github.com/rygorous/ryg_rans/blob/master/rans_byte.h
VikingCoder 3y ago
> At game start, that will be an integer between 1 and 20 (16 different pawn moves, 4 different knight moves). And offer draw. And resign. Just to complete that thought.

marcusbuffett 3y ago

I did end up doing something like this: https://mbuffett.com/posts/compressing-chess-moves-even-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt... You’re spot on about the performance reason I didn’t want to do this originally, but I did some testing and turns out move generation in the library I use is Blazing Fast and wouldn’t be a bottleneck

crdrost 3y ago
It's also that PGN allows you to encode illegal moves, which is important if your dataset contains over-the-board games. That you only got to about 10-12 bits per move is actually kind of sad in a way, because it means you're not doing substantially better than the approach where you record a move as just (delete-piece-at ____, recreate-that-piece-at ____) 12-bit pairs, where castles are implicitly only recorded by moving the king further than usual and underpromotion has to be explicitly recorded with an extra 12-bit move that is otherwise semantically impossible.
- lifthrasiir 3y ago
  Such games should be infrequent enough that you don't need to optimize for them. A single unused code (or for arithmetic coding, a single symbol with a very low but non-zero frequency) can be used as an escape for a full non-optimized move format.
joshka 3y ago
I just added your blog to my RSS reader and noticed that your blog title in the RSS is a bit weird (in case you were unaware): <title>Posts on A blog</title> <link>https://mbuffett.com/posts/</link> <description>Recent content in Posts on A blog</description>
lifthrasiir 3y ago
You don't seem to have a public repository for the code described in your posts (presumably a part of Chessbook?), but you might be using a textbook arithmetic coding algorithm which maintains both lower and upper bounds and does a renormalization by comparing topmost bits. If it's the case rANS would be much simpler to write and more efficient [1]. If your AC code is already well-optimized, there is not much reason to switch though. [1] Fabian Giesen's sample implementation is already as good as is, and also contains a good alias table implementation if you want multi-symbol inputs: https://github.com/rygorous/ryg_rans/blob/master/rans_byte.h https://github.com/rygorous/ryg_rans/blob/master/rans_byte.h

VikingCoder 3y ago

> At game start, that will be an integer between 1 and 20 (16 different pawn moves, 4 different knight moves). And offer draw. And resign. Just to complete that thought.