alt Hacker NewsI would do it like this. There are 32 pieces, any of which may be missing. So let's use four bytes (32 bits) as a mask of what pieces are present. Then, coordinates can be given for each piece that is present. The board is 8x8, so coordinates can be encoded as pairs of 3 bits, e.g. A3 is 000:011. The worst case is that we need 32 of these pairs, which requires 24 bytes. That brings us to a worst case of 28.
How can we eliminate two bytes?
We can more cleverly encode the mask so that two bytes are used to express the all-pieces-present, and certain other cases. A fully decoded mask is only used for boards that have too few pieces to break over 26 bytes.
For instance suppose we have a two-bit header encoding several cases:
00 - no piece are missing (32 six-bit coordinates follow)
01 - one piece is missing, followed by 5 bit ID of that piece
10 - two pieces are missing, followed by two 5 bit IDs of the two pieces
11 - three or more pieces missing, full mask follows.
In case 11, we need a 32 bit mask, followed by as many as 29 coordinate pairs.
So 2 + 32 + 6 * 29 = 208 bits.
And hey look, by dumb luck, 208 / 8 = 26.
I will check the article later.
Right we need some additional state for ampassan and whether counseling is available and such, not just the raw position.
However, am I mistaken? The article appears to be neglecting to record one bit of information: whose turn is it for this board position, black or white? If you're going to care about whether castling is available and other such game state, that is not complete without knowing whose turn it is for that position.