Re^2: [OT] Is It Possible To Serialize A Chess Board In Fewer Than 23 Bytes?

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

--
Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)

Comment on Re^2: [OT] Is It Possible To Serialize A Chess Board In Fewer Than 23 Bytes?

Replies are listed 'Best First'.
Re^3: [OT] Is It Possible To Serialize A Chess Board In Fewer Than 23 Bytes? by hippo (Archbishop) on Mar 11, 2026 at 10:48 UTC
So for a pawn to be promoted, at least one other pawn has to be removed from the board Not quite. It is that at least one other piece has to be removed from the board. A white pawn could advance past its black neighbour in the next column then take a black non-pawn piece in that column thereby side-stepping the black pawn in its original column. So a piece has to be removed, just not necessarily a pawn, and therefore that piece does not necessarily have the option of promotion. So a single pawn could be promoted without the possibility of denying promotion to any of the remaining pawns. 🦛	[reply]
Re^4: [OT] Is It Possible To Serialize A Chess Board In Fewer Than 23 Bytes? by afoken (Chancellor) on Mar 11, 2026 at 22:58 UTC
Not quite. It is that at least one other piece has to be removed from the board. Yes, bad wording. "At least" should indicate pawn or higher rank. But then, I never considered removing non-pawns. Removing a pawn removes the least number of bits from the variable length bitstream (only 2 bits). So, allowing a pawn to remove a rook, knight, or bishop removes 4 bits from the bitstream, allowing it to remove a queen removes 5 bits. That (partially) opens the way for the pawn with the opposite color from the same column to be promoted. Repeating that for a total of four pawns of each color can get us into a situation where no pawn blocks any pawn of the opposite color. Half of the columns each have two white pawns and no black pawns, and the other half each have two black pawns and no white pawns. To get there, eight pieces had to be removed from the board, each a rook, knight or bishop. I won't remove the queens, because they shorten the bitstream by one more bit, and I want it as long as possible (worst case). Each of the eight pieces frees 4 bits, so we need 32 bits less than for the initial setup. Then, we allow all 16 pawns to be promoted to queens, which need the most bits (5 bits plus color). Pawns used 2 bits plus color, so this adds 48 bits to the bitstream. In total, we are at the initial 164 bis from the fresh board + 16 bits = 180 bits = 23 bytes. Castling adds 4 bits, 184 bits total, still 23 bytes. Alexander -- Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)	[reply]