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