alt Hacker NewsYou have a good starting point, but using 6+1 bits is a bad way to encode 65 possibilities. If you use base 65, you'll see that 65^32 possibilities only require one more bit to store than 64^32.
And four promotion possibilities wouldn't be 4 bits, it would be 2. But even better is 5^16 squeezing into 38 bits.
Combining those cuts your strategy down to 192.7+37.2+4+6 bits which is 30 bytes.
The main savings the article has is being smarter about how to store promotions. And then it uses some tricks by swapping pieces to encode extra bits.
(But it turns out that storing which tiles are occupied, then listing each piece in order, works better than encoding locations.)
Replies
Yes, I made a few mistakes and I did realize I didn't need the whole extra bit to store 65 possible locations- I just was being a bit lazy. Ba dum tiss.
Hmm as a bit field followed by piece order- that would be 8 bytes followed by a variable number of pieces, perhaps you could do a sort of compression where 0c means pawn and 1xxxc is any other piece. (c stands for a color bit). So thats another 14 bytes. Thats 22 bytes!
The xxx by the way is one of 8 things: k, k not moved, r, r not moved, n, b, q, en passant pawn
Heuristic: (65/64)^64 is extremely close to e. This comes from a classic formula for e as the limit of (1+1/n)^n.
Therefore (65/64)^32 is roughly sqrt(e). Since 1 < e < 4, 1 < sqrt(e) < 2. So 65^32 < 2 * 64^32.