[vnorilo]

Using 3 bits for piece type (including empty) and 1 bit for color makes a simple matrix enconding of the board just 8x8x4=256 bits. Add run length encoding for empty squares and it will be much smaller.

4 bits per square has room in it for RLE flags and even counts, without increasing the worst case size.

[thrw21]

248 is max in my case (actually later I noticed I could shave another 4 bits), if there are less pieces, there will be less data

But probably with encoding your solution would be better

[thrw21]

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

[teo_zero]

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

[Dylan16807]

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.