3 ms·
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
by jonsoft 9mo ago
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?
- tromp 9mo agoAmong 4 pawns like white and black a&b pawns, you only need 1 pawn capture to allow the other 3 pawns to promote.
- gus_massa 9mo agoYep, 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.
- jonsoft 9mo agoActually, 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
- jonsoft 9mo agoGreat point. 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?
- deleted 9mo ago[deleted]