Comment by fallingfrog | Hacker News Reader

Comment by fallingfrog | Hacker News Reader

Parent Full thread

Sorry I was in the car and read the headline and tried to see how I would do it as an exercise. I actually think I undercounted because for the king and rooks you have to store whether they have been moved yet, and for the pawns whether they just jumped two spaces (so you know if en passant is a valid move).

So I wasn't saying the article is wrong, just engaging in a bit of intellectual exercise.

My count was: there are 16 pawns, each could be in one of 64 places or not on the board, so 6+1 bits per pawn for that, and each could be promoted to a knight a bishop a rook or a queen, so 4+1 bits per pawn for that, and one of them might have just moved two spaces, so 3+1 bits for that. And the other 16 pieces don't change their nature so we only need to know where they are, so 6+1 bits for each of those, plus 3 bits for each of the rooks and the king to tell if they have already been moved. That's.. 40 bytes actually. Im really curious how they got it in 26.

Update: I see! They used illegal positions to store all the special statuses. Very clever!

You 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.)

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

From the previous HN discussion, 00c for pawn and xxxc for other pieces is probably the optimal way to encode pieces into whole bits. Because you can sacrifice 1 pawn to enable 3 promotions, so you need to handle up to 28 non-pawns. With 2/5 you start at 14 bytes but can need up to 17.5. With 3/4 you start at 14 bytes and never need more than 14.

With 6 xxx states instead of 8, you can merge "king not moved", "rook not moved", and "en passant pawn" into a single state since those can never overlap. (Though if you're encoding one pawn the long way that means you need 14.125 bytes, oh well.)

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.

Thats a lovely observation! Very clever.

Reply on news.ycombinator.com