9 ms·

I played with this in the past (https://news.ycombinator.com/item?id=34461113#34462521 https://news.ycombinator.com/item?id=34461113#34462521), but am willing t

I played with this in the past (https://news.ycombinator.com/item?id=34461113#34462521 https://news.ycombinator.com/item?id=34461113#34462521), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If there are less than 16 bits set in the bitboard, ignore the last items in the list. 0000 - 0x0 - black pawn 0001 - 0x1 - black pawn (can be en-passant'd) 0010 - 0x2 - black knight 0011 - 0x3 - black bishop 0100 - 0x4 - black rook (castling unavailable) 0101 - 0x5 - black rook (castling available) 0110 - 0x6 - black king 0111 - 0x7 - black queen 1000 - 0x8 - white pawn 1001 - 0x9 - white pawn (can be en-passant'd) 1010 - 0xA - white knight 1011 - 0xB - white bishop 1100 - 0xC - white rook (castling unavailable) 1101 - 0xD - white rook (castling available) 1110 - 0xE - white king 1111 - 0xF - white queen I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly. The starting position would be represented with a bitboard of 0xFFFF00000000FFFF, with a list of [0xD, 0xA, 0xB, 0xF, 0xE, 0xB, 0xA, 0xD, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x5, 0x2, 0x3, 0x7, 0x6, 0x3, 0x2, 0x5], using the same position-to-number scheme in the blog post Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly Edit2: To store which player is next: do nothing for white. For black, if there are 32 pieces, flip the bitboard upside down. (To check if it's black's turn, verify that black pawns are "below" white pawns, which is illegal before captures are made.) If there are less than 32 pieces and it's black's turn, invert the bitboard. (To check, count the number of set bits.) This is entirely taken from https://news.ycombinator.com/item?id=37526484 https://news.ycombinator.com/item?id=37526484

antsou 3y ago
I believe you can also do it in a slightly different way. For each square on the board: 0 - encodes no piece in the square; at least 32 of them, so 32 bits (4 bytes) 1xxxx - xxxx being your encoding: encodes remaining pieces; at most 32 of them, so max 32 x 5 bits (20 bytes)
kurinikku 3y ago
OP here. I'm not sure how I overlooked this comment earlier, but this is elegant and it works! It's amazing how you need exactly 4 bits for each bit. Thank you for sharing!
elteto 3y ago
Maybe a silly question, how do you know which side of the board is white vs black?
- timerol 3y ago
  Convention - use the same bit-to-number scheme in the blog post. Bit 0 is a1, bit 7 is h1, bit 8 is a2, bit 56 is a8, bit 63 is h8.
penteract 3y ago
There are at most 32 pieces on a chessboard (16 of each color), so I think you need 24 bytes.
- timerol 3y ago
  ... right. I thought 16 felt a little small. Thanks for the catch, updated
deleted 3y ago
[deleted]
k1t 3y ago
What if there are 32 pieces on the board?
tromp 3y ago
A position, as stored in FEN notation, also includes side-to-move.
- devit 3y ago
  There's a simple trick to encode it: if there are less than 32 pieces, invert the bitboard (easily decoded since boards can't have more than 32), while if there are 32 pieces flip the board vertically (easily decoded because white pawns can't be after black pawns with no captures).
bhelkey 3y ago
A nitpic, to castle, the king AND the rook must not have moved from their starting squares. Using this approach, you would need to store castling available/unavailable for the kings as well.
- ianferrel 3y ago
  No you don't. If the king moves, you update both rooks to be unavailable for castling.
- penteract 3y ago
  If the king has moved, you can just mark both rooks as castling unavailable.
- deleted 3y ago
  [deleted]
sufianrhazi 3y ago
Nice! Though there are max 32 pieces on a board, not 16; so this scheme is 64 + 32 * 4 = 192 bits, or 24 bytes. The bit to indicate whose turn it is isn't accounted for here. But it probably could probably represented by the binary negation of the bitboard -- if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied. Taking things further, it probably can be compressed even more with (much) more complex logic, as the castling available bit must only be present on the corner positions, and the pawn en-passant capabilities are only available on the middle rows, so those bits are meaningless in other positions.
- 6510 3y ago
  There is never a pawn at the 8th row, one might "insert" an en-passant row into the board.
- timerol 3y ago
  I like the bitboard inversion idea. (Requires flipping logic as well from https://news.ycombinator.com/item?id=37526484 https://news.ycombinator.com/item?id=37526484, since 32 is a special case.) Note that the en-passantable pawns and castle-able rooks came from options that were unused in my first pass (linked comment). I could use 0x1 as "castleable rook or en-passantable pawn, determined from where it is" and then store 32 integers with 13 options in 119 bits[1], saving 9 bits. But I'm kinda attached to the simplicity here. (The 16->32 was edited as you wrote this comment.) [1] log(13^32)/log(2) = 118.4
- penteract 3y ago
  > if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied. This doesn't quite work because if there are exactly 32 bits set, inverting it leaves 32 bits set. You could fix this by marking all pawns belonging to the player who's turn it is as capturable via en-passant (if a player has no pawns left, at least 1 piece has been captured, so inverting the bitboard works).
skupig 3y ago
You can use duplicate king identifiers to represent castling available, and replace the extra rook identifiers with "black king (my turn)" and "white king (my turn)" to store the turn in the same amount of space. edit: You can then use the inverted/flipped board trick to store one bit of your piece list, down to 191 bits. edit2: You only need one "king (my turn)" ID, which represents the whichever color you didn't use for the other king. You can use the extra value for another "my turn" piece that also sets a bit. 190 bits!
- xpe 3y ago
  It is necessary to store the ability-to-castle state with each rook; attempting to keep it only attached to each king is insufficient.
  - skupig 3y ago
    That's not what I wrote, you duplicate the king ID in the position of each castle-able rook.
    - xpe 3y ago
      Seems like I’m not following your specific id mapping.
      - teo_zero 3y ago
        I rhink the concept is: in the initial position you have three kings: in a1, e1 and h1. Once the left rook is moved, it will be encoded as rook and not as a king anymore. Same for the right one. If you move the king, both rooks will be encoded as rooks and not as king anymore. Decoding is easy: if there's more than one king, one must be in e1: that's the real one, the others are actually rooks.
6510 3y ago
My thought was to have additional schemes depending on the length of the byte array. For example, if the position is an empty array it is the beginning position, if it is 1 byte it represents the most common positions. "" is the beginning position "0" is E4 "1" is D4 "2" is C4 "3" is E4 E5 "4" is D4 D5 "5" is G3 One could do a multi byte version where the order of popular positions is replaced with a crappy chess computer. If there is no en-passant, no promoted pawn and castling is allowed you can use representations slightly shorter than 24.
penteract 3y ago
To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pawn with the piece in the 1st or last rank as mentioned https://news.ycombinator.com/item?id=37526523 https://news.ycombinator.com/item?id=37526523 ). 2 rook representations aren't needed (encode a king with castling opportunities as a knight, bishop or rook, and when decoding, if there are no kings of a given color, look at the piece in the king's starting position) so another 4 bits could be saved by making rook, bishop or knight representations shorter.
- alexb_ 3y ago
  > To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. Can you explain this in more detail? Curious as to how you could save space with this.
  - Dylan16807 3y ago
    You read the piece data bit by bit. If you see 100 or 000 then you stop right there. You have a pawn, and the next piece starts with the next bit. There's no ambiguity. Here's a good example image for huffman coding: https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg So before any captures are made, you have 32 pieces, half of which use 3 bits and half of which use 4 bits. 14 bytes, plus the 8 bytes storing the bitboard. When you promote a piece it goes up in size from 3 to 4 bits, but you can guarantee there have been enough captures to offset that, so you never need more space than you started with.
    - alexb_ 3y ago
      I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. I like the "no kings" idea for castleable kings - though I think with smaller pawn sizes, that gives another opportunity for compression: - king that can't castle: king - king that can castle queenside: any other piece in king's position, no king of that color on board - king that can castle kingside: black pawn on 1st or 8th rank - king that can castle: white pawn on 1st or 8th rank Because you are often going to have positions where the king can castle kingside and positions where the king can castle either way, this should maximize how often you manage to save space w/ the pawns. Another thought I had (which might contain other problems, not sure yet) is to use pawns on the 1st or 8th rank to denote pieces which are in their starting position - the decompression algorithm can then derive what piece it is based on the known starting position. Once we start having data saving because of pawns taking less bits, we want to be able to use them as much as possible to save space.
seanhunter 3y ago
As the article discusses, there's a bit more than that to store in a position. Specifically you have to store whether or not castling is available for the two sides and also whether any pawns are en passant targets, since both of those moves are available (or not) conditionally in a given position based on previous moves in the game.
- timerol 3y ago
  There are specific types mentioned to denote rooks that the king is allowed to castle towards, and pawns that can be en passanted
- hinkley 3y ago
  I don’t think that’s true. Or rather, it’s only true for storing board position not for storing the move history. If you have the entire move history you know that status of each piece.
  - kpozin 3y ago
    If you have the entire move history, then you probably don't need to store partial board positions.
    - hinkley 3y ago
      Of course it depends on what you're doing with the information. If you're compressing it in order to sort 100 million board positions for a minmax algorithm, it might make sense to use a representation that makes queries cheaper at the cost of size. If instead you're trying to store every competition chess game in history, then it depends on what you're trying to do with them. Look for similar board positions? If you're trying to allow inmates in a Dumas-inspired prison secretly play chess against each other over a covert channel, then detection is the problem. Which might mean compression (fewer signals to hear) or masking the signal as random noise.
jenscow 3y ago
small shavings: * If there are less than 32 bits set in the bitboard, the item list is shorter (rather than ignored). * Probably not worth it, but: When there are 32 bits set on the bitboard, stop processing the bit-board.. however, if you adjusted the ordering of the lines (0,7,1,2,...), it's optimised for the first 1 or 2 positions * Maybe this is cheating, but if the size of the game data will be known ahead of processing, then you could leave off the last item in the list if it's a king or a rook * Starting the item list with 2 white kings can be a special case for "starting position", and if the items are listed before the board then only 1 byte is needed :)

antsou 3y ago

I believe you can also do it in a slightly different way. For each square on the board: 0 - encodes no piece in the square; at least 32 of them, so 32 bits (4 bytes) 1xxxx - xxxx being your encoding: encodes remaining pieces; at most 32 of them, so max 32 x 5 bits (20 bytes)

kurinikku 3y ago

OP here. I'm not sure how I overlooked this comment earlier, but this is elegant and it works! It's amazing how you need exactly 4 bits for each bit. Thank you for sharing!

elteto 3y ago

Maybe a silly question, how do you know which side of the board is white vs black?

timerol 3y ago
Convention - use the same bit-to-number scheme in the blog post. Bit 0 is a1, bit 7 is h1, bit 8 is a2, bit 56 is a8, bit 63 is h8.

penteract 3y ago

There are at most 32 pieces on a chessboard (16 of each color), so I think you need 24 bytes.

timerol 3y ago
... right. I thought 16 felt a little small. Thanks for the catch, updated

deleted 3y ago

[deleted]

k1t 3y ago

What if there are 32 pieces on the board?

tromp 3y ago

A position, as stored in FEN notation, also includes side-to-move.

devit 3y ago
There's a simple trick to encode it: if there are less than 32 pieces, invert the bitboard (easily decoded since boards can't have more than 32), while if there are 32 pieces flip the board vertically (easily decoded because white pawns can't be after black pawns with no captures).

bhelkey 3y ago

A nitpic, to castle, the king AND the rook must not have moved from their starting squares. Using this approach, you would need to store castling available/unavailable for the kings as well.

ianferrel 3y ago
No you don't. If the king moves, you update both rooks to be unavailable for castling.
penteract 3y ago
If the king has moved, you can just mark both rooks as castling unavailable.
deleted 3y ago
[deleted]

sufianrhazi 3y ago

Nice! Though there are max 32 pieces on a board, not 16; so this scheme is 64 + 32 * 4 = 192 bits, or 24 bytes. The bit to indicate whose turn it is isn't accounted for here. But it probably could probably represented by the binary negation of the bitboard -- if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied. Taking things further, it probably can be compressed even more with (much) more complex logic, as the castling available bit must only be present on the corner positions, and the pawn en-passant capabilities are only available on the middle rows, so those bits are meaningless in other positions.

6510 3y ago
There is never a pawn at the 8th row, one might "insert" an en-passant row into the board.
timerol 3y ago
I like the bitboard inversion idea. (Requires flipping logic as well from https://news.ycombinator.com/item?id=37526484 https://news.ycombinator.com/item?id=37526484, since 32 is a special case.) Note that the en-passantable pawns and castle-able rooks came from options that were unused in my first pass (linked comment). I could use 0x1 as "castleable rook or en-passantable pawn, determined from where it is" and then store 32 integers with 13 options in 119 bits[1], saving 9 bits. But I'm kinda attached to the simplicity here. (The 16->32 was edited as you wrote this comment.) [1] log(13^32)/log(2) = 118.4
penteract 3y ago
> if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied. This doesn't quite work because if there are exactly 32 bits set, inverting it leaves 32 bits set. You could fix this by marking all pawns belonging to the player who's turn it is as capturable via en-passant (if a player has no pawns left, at least 1 piece has been captured, so inverting the bitboard works).

skupig 3y ago

You can use duplicate king identifiers to represent castling available, and replace the extra rook identifiers with "black king (my turn)" and "white king (my turn)" to store the turn in the same amount of space. edit: You can then use the inverted/flipped board trick to store one bit of your piece list, down to 191 bits. edit2: You only need one "king (my turn)" ID, which represents the whichever color you didn't use for the other king. You can use the extra value for another "my turn" piece that also sets a bit. 190 bits!

xpe 3y ago
It is necessary to store the ability-to-castle state with each rook; attempting to keep it only attached to each king is insufficient.
- skupig 3y ago
  That's not what I wrote, you duplicate the king ID in the position of each castle-able rook.
  - xpe 3y ago
    Seems like I’m not following your specific id mapping.
    - teo_zero 3y ago
      I rhink the concept is: in the initial position you have three kings: in a1, e1 and h1. Once the left rook is moved, it will be encoded as rook and not as a king anymore. Same for the right one. If you move the king, both rooks will be encoded as rooks and not as king anymore. Decoding is easy: if there's more than one king, one must be in e1: that's the real one, the others are actually rooks.

6510 3y ago

My thought was to have additional schemes depending on the length of the byte array. For example, if the position is an empty array it is the beginning position, if it is 1 byte it represents the most common positions. "" is the beginning position "0" is E4 "1" is D4 "2" is C4 "3" is E4 E5 "4" is D4 D5 "5" is G3 One could do a multi byte version where the order of popular positions is replaced with a crappy chess computer. If there is no en-passant, no promoted pawn and castling is allowed you can use representations slightly shorter than 24.

penteract 3y ago

To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pawn with the piece in the 1st or last rank as mentioned https://news.ycombinator.com/item?id=37526523 https://news.ycombinator.com/item?id=37526523 ). 2 rook representations aren't needed (encode a king with castling opportunities as a knight, bishop or rook, and when decoding, if there are no kings of a given color, look at the piece in the king's starting position) so another 4 bits could be saved by making rook, bishop or knight representations shorter.

alexb_ 3y ago
> To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. Can you explain this in more detail? Curious as to how you could save space with this.
- Dylan16807 3y ago
  You read the piece data bit by bit. If you see 100 or 000 then you stop right there. You have a pawn, and the next piece starts with the next bit. There's no ambiguity. Here's a good example image for huffman coding: https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg So before any captures are made, you have 32 pieces, half of which use 3 bits and half of which use 4 bits. 14 bytes, plus the 8 bytes storing the bitboard. When you promote a piece it goes up in size from 3 to 4 bits, but you can guarantee there have been enough captures to offset that, so you never need more space than you started with.
  - alexb_ 3y ago
    I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. I like the "no kings" idea for castleable kings - though I think with smaller pawn sizes, that gives another opportunity for compression: - king that can't castle: king - king that can castle queenside: any other piece in king's position, no king of that color on board - king that can castle kingside: black pawn on 1st or 8th rank - king that can castle: white pawn on 1st or 8th rank Because you are often going to have positions where the king can castle kingside and positions where the king can castle either way, this should maximize how often you manage to save space w/ the pawns. Another thought I had (which might contain other problems, not sure yet) is to use pawns on the 1st or 8th rank to denote pieces which are in their starting position - the decompression algorithm can then derive what piece it is based on the known starting position. Once we start having data saving because of pawns taking less bits, we want to be able to use them as much as possible to save space.

seanhunter 3y ago

As the article discusses, there's a bit more than that to store in a position. Specifically you have to store whether or not castling is available for the two sides and also whether any pawns are en passant targets, since both of those moves are available (or not) conditionally in a given position based on previous moves in the game.

timerol 3y ago
There are specific types mentioned to denote rooks that the king is allowed to castle towards, and pawns that can be en passanted
hinkley 3y ago
I don’t think that’s true. Or rather, it’s only true for storing board position not for storing the move history. If you have the entire move history you know that status of each piece.
- kpozin 3y ago
  If you have the entire move history, then you probably don't need to store partial board positions.
  - hinkley 3y ago
    Of course it depends on what you're doing with the information. If you're compressing it in order to sort 100 million board positions for a minmax algorithm, it might make sense to use a representation that makes queries cheaper at the cost of size. If instead you're trying to store every competition chess game in history, then it depends on what you're trying to do with them. Look for similar board positions? If you're trying to allow inmates in a Dumas-inspired prison secretly play chess against each other over a covert channel, then detection is the problem. Which might mean compression (fewer signals to hear) or masking the signal as random noise.

jenscow 3y ago

small shavings: * If there are less than 32 bits set in the bitboard, the item list is shorter (rather than ignored). * Probably not worth it, but: When there are 32 bits set on the bitboard, stop processing the bit-board.. however, if you adjusted the ordering of the lines (0,7,1,2,...), it's optimised for the first 1 or 2 positions * Maybe this is cheating, but if the size of the game data will be known ahead of processing, then you could leave off the last item in the list if it's a king or a rook * Starting the item list with 2 white kings can be a special case for "starting position", and if the items are listed before the board then only 1 byte is needed :)