I remember asking myself this question years ago, and came to 162 bits. I was just a kid back then so the logic is probably wrong but I do wonder how simple the encoding could be under those constraints...
Edit: Here are the Notes
0 Empty
10 Pawn
1100 Knight
1101 Rook
1110 Bishop
1111 Queen
32 + 32 + 472
2 times 6 bits: position of the kings
30 bits: color mask
120 + 2*6 + 30 = 162 bits
We can store the rest using the methods from the blog post and add 18 bits for promotion, giving 180 bits.
I'm sure this isn't the most efficient way, and I think I had other methods and considered things like the bishops being able to occupy 32 squares, though special casing doesn't make sense because of promotions.
Technically if you got 8 bishops/queens/knights/rooks
You would occupy another 16 bits, giving 196 bits
I think the upper limit can be reduced at the cost of increasing the lower limit
EDIT2: I think I made the assumption at the time that to promote one piece you needed to capture at least one enemy pawn, giving the space for the two bits, which means the upper bound is actually 180 bits
Would love to see other people try in the comment section
Each pawn that wants to be promoted either takes:
(a) another 'special' piece (knight/rook/bishop/queen), in which case it has already bought enough bit budget to later be promoted; or
(b) another pawn, in which case this temporarily saves 1 bit (as the other pawn becomes a space), but then later we need 2 extra bits for the promotion, so we pay 1 bit extra per pawn in total
In the case of (b) there are now fewer pawns that can be promoted, and so worst case, we have to pay a budget of 1 bit per each of 8 promoted pawns.
So I think maximum required bits is only 162 + 8 = 170?
So for each 4 pawn cluster, 1 pawn takes another pawn, and the net result is +1 bit once the captor promotes. The remaining 2 pawns in the cluster each need 2 extra bits when promoted => 2 x 2 = 4 bits. So 5 bits per 4-pawn cluster, of which there are 4.
So maximum representation would be 162 + (5 * 4) = 182 bits?
Yep, that increase the total in 3*3-4=5 bits, and you can repeat it 4 times, so the maximum is at least 162+4*5=182.
I'm trying to prove that is the worst case, but there are just too many cases. I guess I'll try to use a program o brute force it or just forget about it.
Actually, given this, we believe that 4 pawns must have been captured to reach 182 bits. So at least 4 pieces no longer need colors. If we store the color mask at the end, I think we can make it variable length, and truncate when no further pieces need colors assigned.
So then we need maximum 182 - 4 = 178 bits
EDIT: Equivalently, we could suffix each non-empty piece in the sequence with an associated color bit
I thought the same but realized you can retrospectively 'insert' the king positions into the position sequence, shifting the remaining sequence one square along for each king, so no more bits required though the data structure is unwieldy!
Edit: Here are the Notes
0 Empty
10 Pawn
1100 Knight
1101 Rook
1110 Bishop
1111 Queen
32 + 32 + 472
2 times 6 bits: position of the kings
30 bits: color mask
120 + 2*6 + 30 = 162 bits
We can store the rest using the methods from the blog post and add 18 bits for promotion, giving 180 bits.
I'm sure this isn't the most efficient way, and I think I had other methods and considered things like the bishops being able to occupy 32 squares, though special casing doesn't make sense because of promotions.
Technically if you got 8 bishops/queens/knights/rooks You would occupy another 16 bits, giving 196 bits
I think the upper limit can be reduced at the cost of increasing the lower limit
EDIT2: I think I made the assumption at the time that to promote one piece you needed to capture at least one enemy pawn, giving the space for the two bits, which means the upper bound is actually 180 bits
Would love to see other people try in the comment section