Hacker News Reader

Comment by thrw21 | Hacker News Reader

But probably there can be a middle grounds.

1 bit for each square represent there is a piece on that pos so 64 bits

then for each side, 4 bits to represent number of pieces and 3 bits for each piece to represent their type

At max 64 + 2x(4 + 3 x 16)=168 bits for 16 pieces each side.

edit: nvm this wouldn't work since you wouldn't know the colors of the pieces on board. You need to store 4 bits for each piece, 1 color + 3 type so it is 64 + 2 * 4 * 16 = 196. I am not sure if this is better anymore

View on HN

Actually it's 192 bits, not 196.

To beat it you must encode each piece with a different number of bits. E.g.

  Q c00
  N c01
  P c10
  B c110
  R c1110
  K c1111

where c is 0 for white or 1 for black. Since there are 2xK, 2xQ, 4xB, 4xN, 4xR, 16xP, you will need 2x5 + 2x3 + 4x4 + 4x3 + 4x5 + 16x3 = 112 bits. Adding the 64 bits for the bitmap, the grand total would be 176 bits.

The issue is that each time a P is promoted to R or B (a stupid thing to do, since a Q would be better) you need one or two bits more. On the other hand, you spare 3 to 5 bits for each captured piece. In normal play, captures outnumber promotions, and promotions are either to Q or N, never R or B, but theoretically...

https://news.ycombinator.com/item?id=37525348

As far as max size goes, 64 bits plus data per piece seems to be the right path. Especially if you huffman the pawns to be 3 bits each while other pieces are 4 bits.

The grandparent method gets pretty bloated when you start promoting.

Reply on news.ycombinator.com