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

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". ;-)

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.

---

🦛

I know some chess, but I can't clearly see why you need 8 bytes to represent the positions of white or black pieces, and what additional information there is for white pawn, rook, knight, bishop, king, and queen to fit into 6 bytes. Can you give more details?

Also, there might be a way to serialise the board that is very efficient but not really usable (with each piece positioned, you have one less possible position, which might lead to some bit savings in the early stages of the game, for example).

choroba,
I have tried to respond to your post multiple times but apparently the Monastery isn't what it used to be.

See Chess StackExchange for a similar question.

Thanks. Apparently prior art is 24 bytes and doesn't include as much information as my 23 bytes BUT my 23 bytes is inadequate as explained by ikegami elsewhere in this thread.

I can't clearly see why you need 8 bytes to represent the positions of white or black pieces

You have 64 squares and a maximum of 32 pieces. I am trying to compress that in the smallest possible space possible. I use 8 bytes to tell you which of the 64 squares are occupied by white pieces. This is done using a bitstring where the value is either 0 or 1 (piece there or not). I do the same for the black pieces. Once I have told you which spaces are occupied by white pieces, I no longer need to distinguish between white and black - I can simply tell you what piece is at each position. There are 6 different possibilities (pawn/rook/knight/bishop/queen/king). I can do that using 3 bits since 2^3 = 8. Hopefully that now makes sense.

Cheers - L~R

The 24-byte prior art does include all the information you did.

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.

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.

Cheers - L~R

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.

64pos=2**6bits x 32 pieces = 24 bytes

Plus extra bits for special info, I'll ignore (I think you forgot promotion of pawns at the last rank °)

==== Anyway...

the naive approach is not optimal, since 2 pieces can't be on the same field.

So probably run length encoding of empty fields or Huffman coding are better on average.

You can tell what the optimal limit is by enumerating all possible scenarios.

The the ceiling of log₂ count tells you the lower bound of needed bits.

°) in theory you can have 9 queens or 10 bishops.

Update

The chess exchange discussion choroba linked to is quite good.

I have a hunch that a 23 bytes maximum is possible (on average even less), but it would require advanced encoding techniques.

For instance are bishops restricted to 32 positions each.

And castleing is only possible if a rook is in the corner.

Pawns can't reach all fields.

I think you forgot promotion of pawns at the last rank

Maybe, maybe not. Either way, his approach correctly handles promotions.

As for you, it's not just promotions you don't handle. You don't support capturing either! You'd need a length prefix or more bits to encode that a piece is off the board.

I thought about capturing but the "naive (sic) approach" got already long.

> You'd need a length prefix or more bits to encode that a piece is off the board.

Nope. Two pieces can't be on the same field and at least one king must be left. Just position a piece on the (remaining) king to encode capturing.

This discussion is getting useless anyway, BC if the complexity of the task and fuzzy edge cases.

I'd like to see a count of possible board combinations first.

update

IIRC you have also to encode if a match stops because of resignation or a draw or a stalemate...

So many details.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

My answer would be YES. First, of all an 8 x 8 chess board has 64 spaces, so we will use 64 bits to indicate whether a space is occupied or not. We have used 8 bytes so far. We have 15 bytes remaining to encode the type of chess pieces in each slot.

Let's assume that our chess board only has the usual number of pieces: a white king, black king, white queen, black queen, two white horses, two black horses, 8 black pawns, 8 white pawns, 2 white rooks, 2 black rooks, 2 white knights, 2 black knights, and that's it. That's 32 pieces altogether. And if we look at any single occupied space on the chess board, it can only be one of the following:

1. white king
2. black king
3. white queen
4. black queen
5. white rook
6. black rook
7. white pawn
8. black pawn
9. white horse
10. black horse
11. white knight
12. black knight

So, there are twelve kinds of possible choices. We can represent that with a number in base 12 in which digits run from 0 to 11. We will represent 10 with A and 11 with B. So, our range is 0 1 2 3 4 5 6 7 8 9 A B. And let's just say that there are 32 occupied spots on the board at most. When the game begins, each side has 16 pieces. So, we will represent the pieces with 32 base 12 numbers. For example, let's say that our board has the following setup:

White side: 48A20A84 and the white pawns: 66666666

Black side ready for war: 59B13B95 77777777

Notice that the white pieces are represented by even numbers, while the black pieces are represented by odd numbers. The 6s are the white pawns, while the 7s are the black pawns.

So, if we were going to encode this beginning setup, we would write "48A20A84666666667777777759B13B95" and this 32-digit number is in base 12. If we convert that into base 2, we get the following 114-digit number: "101001100101010010000110000000010011110010001010110011101000001011111001010000010111100100110111001111111111100001" I did this conversion using the calculator at https://www.rapidtables.com/convert/number/base-converter.html

If we tried to represent the largest 32-digit number in base 12, it would require 115 binary digits. Now, remember we used 64 bits initially to encode white spaces were occupied and we used 115 bits to encode the type of figures that occupy those spots. That's 179 bits total, which is 23 bytes. We have 5 bits remaining, which can be used to store other information such as have the white side performed a castle already? Has the black side performed castle already? Castle is a special move which can only be done ONCE. But this is irrelevant to the board setup, because it doesn't change the position of the pieces. It's just something extra that needs to be recorded along with other state data to run a chess program. A chess program must keep track of time, whether each side has moved their kings already, performed castle move, and a few other things... But this doesn't affect the board setup.

Great question. I love it!

EDIT: I have thought about this a little bit more, and I realize that my solution would allow a scenario where you have 5 white kings and 0 black kings. LOL That is an impossible scenario, so I would tweak my idea a little bit: Store the position of the white king in 6 bits, the position of the black king in 6 bits. So, now we have 10 types of pieces remaining, which means we can represent the pieces as base 10 numbers instead of base 12. Representing 30 numbers in base 10 means we have a 30-digit number in base 10. And that could be converted to a 100-digit binary number. Also, instead of 64 bits used to represent which spaces are occupied, we can use 62 bits instead, because two are already occupied by the kings. So, a smart decoder would just skip the kings' location. So, first we have 12 bits to store the position of the two kings, followed by 62 bits indicating which spots are occupied, and then 100 bits at most to represent 30 pieces on the board. That's 174 bits which is less than 22 bytes! :D