in reply to [OT] Is It Possible To Serialize A Chess Board In Fewer Than 23 Bytes?
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
|
|---|