update: article says there are approximately 8.7x10^45 reachable chess positions and https://github.com/lechmazur/ChessCounter says this is an upper bound.
(this would correspond to about 153 bits)
update: article says there are approximately 8.7x10^45 reachable chess positions and https://github.com/lechmazur/ChessCounter says this is an upper bound.
(this would correspond to about 153 bits)
For a sparse representation, note that both kings have to exist, so you can represent the live pieces with a base-10 number of n digits with n + 2 64-bit numbers representing piece position, and a little bit extra information for castling and en passant legality. If half the pieces are gone (a guesstimate for average number of pieces on the board), that amounts to about 180 bits for a board representation.
Move history requires about 10 bits per move (pair of white/black turns, with a ply of around 32 = 5 bits), which means you get to 18 moves, which appears to be somewhat shorter than the halfway point of an average chess game.
To be honest, it looks to me like getting more compact than the upper hundreds will require building impossibly large dictionaries.
So, either a fixed-length encoding of the whole board, 64 * (4 bits) = 256 bits = 32 bytes.
Or, sparse variable length encoding of pieces only, 6 bits to index each of 64 squares, = 10 bits * piece count. E.g. initial position takes 32*10 = 320 bits or 40 bytes.