3 ms·

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

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

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