Hacker News new | ask | show | jobs
by c22 3095 days ago
I don't know why he wants to waste so much space with twelve unsigned longs when he can do it in eight (one for each piece and two more masks for color).
2 comments

I don’t know why would you both want to waste so much space?

A cell is either empty, or contains one of the 12 figures.

To store 13 values, you need 4 bits per cell i.e. 256 bits for the complete board. That’s 4 unsigned longs.

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!
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.

Why waste space representing illegal positions?
For that matter, why store the chess board at all when you can just implement checkers?