logoalt Hacker News

untechlast Friday at 9:01 PM0 repliesview on HN

This nerd-sniped me. I think we should separate "chess board" and "chess game state" as two different problems. For "chess board", we don't consider any castling, en-passant or similar. We might store a bit for "who goes next". This is useful for chess puzzles where state shenanigans are rare (I think).

But if we store castling state, I think we are already trying to store the whole game state, and this is representable only by full history because of move repeating rules.

So, I think storing board state as a sequence of moves is more interesting. I would estimate that a number of possible actions on average is closer to 8 than to 16, so it would give as 3 bits for half-move and 6 bits for full move. 24-move game could be represented with 18 bytes, which is considerably lower than 26 bytes!

You can get close to average bit per move, if you reuse "spare" places for the next move. So, for instance, first move have 20 possibilities, which is representable by 5 bits, but you can reuse "spare" 32-20=12 possibilities as a bit for the next move.

This is a representation assuming you use only "move validator" thing that returns a list of possible moves. I think that if you use a chess engine that would output you a probability distribution of possible moves, you can compress noticeably better on average, but decoding would be slow.