How to store a chess position in 26 bytes using bit-level magic (2022)
I played with this in the past (<a href="https://news.ycombinator.com/item?id=34461113#34462521">https://news.ycombinator.com/item?id=34461113#34462521</a>), but am willing to take another stab at it.<p>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.<p><pre><code>  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
</code></pre>
I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly.<p>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<p>Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly<p>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 <a href="https://news.ycombinator.com/item?id=37526484">https://news.ycombinator.com/item?id=37526484</a>