Variable-length encoded enumeration

[...] The other extreme would have all pawns promoted to queens, and no piece removed from the board. [...] That's a total of [...] 212 bits = 27 bytes. For a fresh board, [...] 21 bytes. As long as no pawns are promoted, this number will only decrease while playing. [...] And without pawn promotion, this is always shorter than 23 bytes.

having all 16 pawns promoted to queens does not look very likely, even less if no pieces may be removed from the board. Is it even possible? In other words, is there a set of legal moves that promotes all 16 pawns to queens without removing a single piece from the board?

I don't think so. The pawns block each other in their columns, and there is no way for the pawns to leave their columns except by capturing another piece.

So for a pawn to be promoted, at least one other pawn has to be removed from the board, immediately saving two bits (100 or 101 becomes 0). But in the long run, that removed pawn can't be promoted to queen, saving not two, but five bits for the queen encoding. And that reduces the worst case from 212 bits to 207 bits.

What about the other seven pairs of pawns? They still block each other, so one in each row has to leave the board, seven more pawns removed, seven more pawns that can't be promoted to queen, 7 * 5 = 35 more bits saved from the worst case, for a total of 172 bits = 22 bytes.

So now even my worst case scenario needs less than 23 Bytes.

Am I missing something?

A short look at castling. Wikipedia lists three conditions:

• Neither the king nor the rook has previously moved during the game.
• There are no pieces between the king and the rook.
• The king is not in check and does not pass through or finish on a square controlled by an enemy piece.

The second and third conditions can be checked from the positions of the pieces without any other information, no extra bits needed.

For the first condition, we need to know if king and rooks have moved at all. Because both can return to their initial positions, that can't be derived from the positions. For "list pieces", we use 3 bits for the byte, but need only 6 types. So we could use two values for the king, one moved, one not moved; and the same for the rooks. Then, all information needed is encoded in the position data. No extra bits needed.

For the bitstreams, we could use six extra bits to store if rooks and kings have moved or not. But we can shorten that to four bits, as we really only want to know if short and long castlings are allowed or not. Initially, all four bits are set. Moving the king clears both bits for the respective color, moving a rook just clears the respective long or short castling allowed bit for the color.

The "variable-length encoded enumeration" would become 4 bits longer. That makes the empty board 68 bits = 9 bytes long, a board with just two kings grows from 74 bits to 78 bits, still 10 bytes; initial board grows from 164 bits to 168 bits, still 21 bytes; worst case with eight promoted pawns grows from 172 to 176 bits, still 22 bytes.

So it seems we can even get the castling information into less than 23 bytes.

Alexander