7 ms·

Not sure the author's use case the naive solution seems like just using 6 bits for the piece's original position, 6 bits for the destination, and 2 bits to desi

by nmilo 3y ago

Not sure the author's use case the naive solution seems like just using 6 bits for the piece's original position, 6 bits for the destination, and 2 bits to designate promotion type, for 14 total bits. Everything else can be found from the board state, and I can't imagine a scenario where you have a move, want to convert to algebraic notation, and also don't know what the board is.

andruby 3y ago
I was thinking the same thing. Often both squares will be close to each other, so I'm sure that a generic compression (eg zstd) can even reduce it even further by taking advantage of that proximity.
jprete 3y ago
I had very similar thoughts but I think one can do much better, even. Each move only needs four bits to identify the piece because each side only has 16 pieces at maximum. The game replayer would need to keep track of each pawn's starting file though (including after promotions). Variable-length encodings of the move options help a lot. Pawns only need two bits because there are never more than four legal moves for a pawn - except for promotions, but just handle those specially for those exact cases (if a pawn moves to the last rank then encode the promotion with two bits, otherwise encode the next move). Knights and kings each need three bits for the move - encode each king-castling option as a move to the appropriate rear diagonal (normally off the board so not otherwise legal). Bishops and rooks need four bits (rank and direction). Queens only need five (three bits for rank, two for direction). This way you can get down to between six and nine bits per move.
- amluto 3y ago
  > The game replayer would need to keep track of each pawn's starting file though (including after promotions). That seems unnecessary. Don’t index the pieces based on their type and where they started — index them based on their current location. So the piece the lexicographically first (rank, file) is piece 0, and 4 bits trivially identifies a piece once you know the color.
  - jprete 3y ago
    True, I hadn't thought of that.
groby_b 3y ago
The problem is that the board state requirement makes searching for specific moves hard. But if you allow board state, you can do less than 14. 3 bits for the type of piece, 6 for the destination, 2 extra bits. (Promotion if destination is last/first line, disambiguation for pawns in en passant) You're still at about twice the theoretical minimum, I think. I vaguely recall an upper bound of 6 bits?

by nmilo 3y ago

andruby 3y ago

I was thinking the same thing. Often both squares will be close to each other, so I'm sure that a generic compression (eg zstd) can even reduce it even further by taking advantage of that proximity.

jprete 3y ago

I had very similar thoughts but I think one can do much better, even. Each move only needs four bits to identify the piece because each side only has 16 pieces at maximum. The game replayer would need to keep track of each pawn's starting file though (including after promotions). Variable-length encodings of the move options help a lot. Pawns only need two bits because there are never more than four legal moves for a pawn - except for promotions, but just handle those specially for those exact cases (if a pawn moves to the last rank then encode the promotion with two bits, otherwise encode the next move). Knights and kings each need three bits for the move - encode each king-castling option as a move to the appropriate rear diagonal (normally off the board so not otherwise legal). Bishops and rooks need four bits (rank and direction). Queens only need five (three bits for rank, two for direction). This way you can get down to between six and nine bits per move.

amluto 3y ago
> The game replayer would need to keep track of each pawn's starting file though (including after promotions). That seems unnecessary. Don’t index the pieces based on their type and where they started — index them based on their current location. So the piece the lexicographically first (rank, file) is piece 0, and 4 bits trivially identifies a piece once you know the color.
- jprete 3y ago
  True, I hadn't thought of that.

groby_b 3y ago

The problem is that the board state requirement makes searching for specific moves hard. But if you allow board state, you can do less than 14. 3 bits for the type of piece, 6 for the destination, 2 extra bits. (Promotion if destination is last/first line, disambiguation for pawns in en passant) You're still at about twice the theoretical minimum, I think. I vaguely recall an upper bound of 6 bits?