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

Interesting.

There are some limits in chess that limit the amount of data needed.

There can't be more than 16 pieces per color on a chess board.
Eight rows and eight columns can be encoded in 3 bit each.
There are 6 different pieces, that again needs 3 bits, leaving two unused values.
Color needs another bit.
There is always a single king per color, no more, no less.
There can't be more than eight pawns per color.
There can't be more than nine queens per color (one "native", eight promoted pawns).
There can't be more than ten bishops, knights, and rooks (two "natives", eight promoted pawns).

So, how can we pack the information?

Enumerated fields: Enumerating all 64 fields in a fixed order needs 1 bit for color and 3 bits to encode the piece type (including a "null piece" for an empty field). 4 bits per field for 64 fields = 32 Bytes.
List pieces: Listing all pieces on a board with their positions needs 1 bit color, 3 bit type, 3 bit row, 3 bit column = 10 bits per piece. Worst case (all 32 pieces on the board), this needs 320 bit = 40 bytes. Best case (only two kings left), this needs 20 bits = 3 Bytes.

Sorting by color and piece type might allow shaving off some bits, but you need either a counter or a separator for the piece types, except for the kings:

Counted bitstream: Imagine a bitstream encoding the positions of all white pieces, followed by all black pieces, starting with the king, then number of queens, queens, number of rooks, rooks, number of knights, knights, number of bishops, bishops, number of pawns, pawns. If there are no pieces of a type, all that's encoded is the number 0. Per color, that needs 5 numbers and 1 to 16 positions. Each number needs 4 bits, each position needs 6 bits. That's a total of 20 bits for numbers and 6 to 96 bits for positions per color, 40 bits for numbers and 12 to 192 bits for positions, 52 to 232 bits, 7 to 29 bytes.
Separated bitstream: When using a separator instead of a counter in the bitstream, the separator must be different from all valid positions, so positions need to grow to 7 bits. The bitstream is then white king, separator, white queens, separator, and so on up to white pawns, then an extra separator, and the same again for the black pieces. There are five separator between types, and one extra between colors, 11 in total. There are 2 to 32 pieces listed. Both positions and separators need 7 bits, so this bitstream needs 7 * (11 + 2) = 91 to 7 * (11 + 32) = 301 bits = 12 to 38 bytes. That's worse than the counted bitstream.
Clocked bitstream: The separator wastes a lot of bits. If there was always at least one piece of each type, all that would be needed was a single extra bit per position. The bit would change whenever the piece type changes, no counter and no extra seapator needed. But alas, chess does not work that way. But we could pretend. We add yet another extra bit per posiiton to indicate a padding position that does not encode a real piece, but is just used to toggle the clock bit. So each position now uses 8 bits, a singe byte. So now our byte stream looks like this: Position of white king (clock bit cleared), Positions of white queens or a single padding value (clock bit set), position of white rooks or a single padding value (clock bit cleared), and so on. That gives a minimum of 6 position/padding values (=bytes) per color, and a maximum of 16 position/padding values per color. In total, that's 12 to 32 bytes. Still not as good as the counted bitstream.
Flagged and clocked bitstream: We are still wasting a lot of bits for non-existing pieces. Let's start the bitstream with flag bits that indicate if piece types are present or not. We don't need that flag for the king, it is always there. So 5 bits per color. Then positions for each piece type per color, with the clock bit. 7 bits per piece. That gives 10 bits for the flags plus 2 * 7 bit to 32 * 7 bit for the positions = 24 bit to 234 bits = 3 to 30 bytes. In the best case, as good as the list, in the worst case, still worse than the counted bitstream.

Can we do better?

Variable-length encoded enumeration: At least half of the fields are empty. Let's encode that as a singe 0 bit. An empty board is just 64 cleared bits = 8 Bytes. All non-empty fields start with a 1 bit, and have a trailing color bit. The most common piece is the pawn, so we encode them as 10 followed by the color, i.e. 100 and 101. All other pieces will start with 11. As rook, bishop and knight they are almost equally common, there won't be an optimized length here. Rook = 1100, bishop = 1101, knight = 1110. King and queen are a little bir more rare, so queen = 11110, king = 11111. An empty board with two kings, best case, needs 62 cleared bits for empty fields, plus two kings, each needing five bits for the type and one bit for the color, 74 bits = 10 Bytes. The other extreme would have all pawns promoted to queens, and no piece removed from the board. 32 empty fields = 32 bits set to 0. Rooks, bishops and knights each need 5 bits including color, for four pieces each, 60 bits. 12 bits for the two kings, and 18 queens each needing 6 bits including colors = 108 bits. That's a total of 32 + 60 + 12 + 108 = 212 bits = 27 bytes. For a fresh board, there are only 2 queens, but 16 pawns. Pawns need 3 bits, so our total is 32 + 60 + 12 + 12 + 16 * 3 = 164 Bits = 21 bytes. As long as no pawns are promoted, this number will only decrease while playing. Better than the plain enumeration, but for thw two-kings-scenario, worse than the list. And without pawn promotion, this is always shorter than 23 bytes.

Next 1 byte = 1 bit representing black/white's turn, 4 bits representing what type of castling is still possible, 3 bits representing the column the last turn moved the pawn 2 places

That's not board data, that's game log.

Alexander

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

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

Replies are listed 'Best First'.
Re^2: [OT] Is It Possible To Serialize A Chess Board In Fewer Than 23 Bytes? by afoken (Chancellor) on Mar 11, 2026 at 10:17 UTC
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". ;-)	[reply]
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]