First I found a clever way to minimize the amount of bits necessary to describe a board position. I think I hit 34 bytes per position or so, and I guess further optimization was possible.
Indeed, using a very straightforward Huffman encoding (1 bit for an for empty cell, 3 bits for pawns) you can get it down to 24 bytes for the board alone. Was an interesting puzzle.
Looking up “prior art” on the subject, you also need 2 bytes for things like “may castle”, and other more obscure rules.
There’s further optimizations you can do, but they are mostly for the average case, not the worst case.
Indeed, using a very straightforward Huffman encoding (1 bit for an for empty cell, 3 bits for pawns) you can get it down to 24 bytes for the board alone. Was an interesting puzzle.
Looking up “prior art” on the subject, you also need 2 bytes for things like “may castle”, and other more obscure rules.
There’s further optimizations you can do, but they are mostly for the average case, not the worst case.
I didn’t consider using 3 bits for pawns! Thanks for that :) I did account for such variables as may castle and whose turn it is.