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

[ikegami]

I can see how that would tell you where the white queen is located, but how can you tell where the black queen is located with that? Aren't you missing the 6 bytes for black? That totals 8+8+6+6+1 = 29 bytes

---

3 bits is not enough to represent the column of a pawn that just "lept" (moved 2 places) because it doesn't leave space to indicate that no pawns just lept. You could address this by distinguishing a "leaping" pawn from a "normal" pawn in the 16 strings of 3 bits.

---

You didn't mention it, but your approach does handle promotions. (e.g. A player can end up with two Queens.)

Solutions that encode the position of each piece (as opposed to those that encode the type of each piece) don't support promotions (without extreme overhead).

---

You can save a byte by using a variable-base number.

• 6 types for 32 pieces.
• 9 possible columns for leaping pawns. (8 columns, plus one value to indicate "no pawn just moved two".)
• 4 castling available flags.
• 1 turn flag.

8 + 8 + ceil( log256( 6^32 * 9 * 2^4 * 2^1 ) ) = 28 bytes

Effectively, this uses the space wasted by using 3 bits to store 6 possible values to store the extra states.

---

But what if we store one grid instead of two, and encode the colour in the 16 strings?

• Black/White Normal/Leaping Pawn
• Black/White R
• Black/White N
• Black/White B
• Black/White Q
• Black/White K

That's 14 different values, which fits in 4 bits each, or 16 bytes for all the pieces.

This reduces the size to 8 + 16 + 1 = 25 bytes.

With a lot of creativity, it's possible to encode all of the extra state in those four bits.

• 0: White pawn that didn't just leap
• 1: Black pawn that didn't just leap
• 2: A pawn that just lept
• 3: White knight
• 4: Black knight
• 5: White bishop
• 6: Black bishop
• 7: White rook that can't be castled with
• 8: Black rook that can't be castled with
• 9: White rook that can be castled with
• A: Black rook that can be castled with
• B: White queen
• C: Black queen
• D: White king if it's white's turn
• E: Black king if it's black's turn.
• F: The other king

[Credit: Anonymous user 27050's post on Chess StackExchange.]

(Presence of D vs E indicates the player to move. If a King moves, both rooks of the appropriate colour are marked as can't-be-castled. We know the colour of the pawn that just lept based on the player that has the move.)

This reduces the size to 8 + 16 = 24 bytes.

That's as far as the post on Chess StackExchange went. But we can squeeze a bit more using a variable-base number:

8 + ceil( log256( 6^32 * 2^32 * 9 * 2^4 * 2^1 ) ) = 20 bytes

However, a VBN approach is poorly suited for use as variable-length encoding than the preceding approach.

---

Many updates. I was afraid the site would stop working again.

[Limbic~Region]

ikegami,

I can see how that would tell you where the white queen is located, but how can you tell where the black queen is located with that? Aren't you missing the 6 bytes for black?

Indeed. It was 4 in the morning and I was thinking there were only 8 pieces on each side - 16 * 3 = 48, 48 / 8 = 6.

You can save a byte by using a variable base number.

I actually had more efficient storage solutions (more than 23 bytes but less than 29) that were probably correct but I have given up at this point - sleep comes for us all eventually.

[ikegami]

The final state (white win, black win or draw) can be calculated from the last state, or an extra state that uses special values for the first 8 bytes can be used.