jonsoft

The vastness of this app is only slightly less than the universe it depicts. I'm only just beginning to explore it all, with 118 objects in the atlas, 9 different tours to choose from, and a fictitious spaceship you can ride as you explore. There's even a badge/award system. The electronic music genres make the experience really atmospheric. In the Settings you can choose the detail level from bold (authentic ASCII art feel) to ultra (almost like pixels). It's like a cross between Elite and The Hitchhiker's Guide to the Galaxy.

An absolute must for space fans that helps grasp the scale of the universe.

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

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

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?

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!