Hacker News new | ask | show | jobs
by c22 3094 days ago
Color is still binary and there are at most 32 pieces on the board, so why not 3 bits per cell and a 32 bit lookup for color? Only 224 bits!
1 comments

If you're going to go that far, you might as well use 64 bits to say whether each square contains a piece. There are a maximum of 32 pieces, and for each (potentially) occupied square there are 12 possibilities for what might be there (not counting "nothing" as a possibility in a square since that's already covered by the 64 bits indicating whether each square is occupied), which can be represented in 4 bits per square. So that's 64 bits to say which squares have pieces, plus 32 * 4 = 128 bits to say what is in each occupied square, for a total of 192 bits to store the chessboard.

You can take it even further, too. For the 32 possibly occupied spaces, you can encode what is in them as a 32 digit base 12 integer, then convert to binary, which is guaranteed to fit in 115 bits. So you can get away with 115 + 64 = 179 bits.