How to store a chess position in 26 bytes

Summary

Author's note: This post was adapted from a presentation at the Recurse Center. Hacker News comments here. This excursion started with Nicole Tietz-Sokolskaya’s blog post. I couldn’t help but wonder - is this really the case? Easy mode There are 32 pieces on a chess board. Here we line them up side-by-side. Each piece can occupy one of 64 squares. Let’s denote each piece by a number between 0 and 63 to represent the respective square. Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits). Not so fast Of course, it’s rarely that simple [1]. Captures In addition to positions, we need to keep track of captured pieces as these pieces do not appear on the board. Castling availability