Author's note: This post was adapted from a presentation at the Recurse Center.

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

We need to track if castling is available on the king’s side, on the queen’s side, or both. In particular, castling is not permitted if the king or the rook has previously moved.

En passant target

The en passant capture is permitted on the turn immediately after the opposing pawn makes the double move. The capturing pawn moves to the square behind the opposing pawn; this square is called the en passant target.

Promotions

A promotion takes place when a pawn makes it to the final rank, and is then replaced with a knight, bishop, rook or queen.

We can track captures with a bitmap of 32 bits, each bit representing a piece. We can similarly use bitmaps for castling availability and en passant targets with 4 and 16 bits respectively (1 bit for each rook and 1 bit for each pawn) [2].

Promotions take a bit more space. For each pawn we need 3 bits: 1 bit for whether or not its been promoted, plus 2 bits for what piece its been promoted to. That’s 48 bits altogether.

In summary:

Can we do better?

No two pieces occupy the same square

The first observation is that no two pieces can occupy the same square on the board.

We can apply this to captures by using the opposing king’s position to represent the capture of that piece.

Adam Kelly noted how we can take this further by using our own king’s position. For castling, we simply replace the rook’s position. Since castling is available only if the rook has not moved, we know that the rook would be at its original position.

For en passant, we know that the pawn that just made the double move is at its home file and at a specific rank (4 for white or 5 for black). We similarly replace the pawn’s position with our own king’s position.

By using this trick, we can store captures, castling availability and the en passant target for free!

Let’s take a closer look at promotions.

Ordering of promotions can be unique

The second observation is that the ordering of promoted pawns can be made unique.

In this illustrative example, one pawn is promoted to a queen and another to a rook. The top line on the right represents white pawn positions, while the bottom lines represent the promotion encoding (3 bits for each white pawn) [3].

Now let’s do the following:

1. Represent non-promoted pawns by 0 and the promoted pawns by 1 to 4.

2. Sort the representation in ascending order and reorder the positions accordingly [4].

This gives us the string 00000034 to uniquely represent this specific set of promotions, without information loss.

How many possible strings are there? Generating this by brute force, we end up with 495 distinct strings [5].

len(
    set(
        [
            tuple(sorted((a, b, c, d, e, f, g, h)))
            for a in [0, 1, 2, 3, 4]
            for b in [0, 1, 2, 3, 4]
            for c in [0, 1, 2, 3, 4]
            for d in [0, 1, 2, 3, 4]
            for e in [0, 1, 2, 3, 4]
            for f in [0, 1, 2, 3, 4]
            for g in [0, 1, 2, 3, 4]
            for h in [0, 1, 2, 3, 4]
        ]
    )
)

This can be stored in 9 bits for each side [6].

We add this to the 24 bytes for positions and end up with a total of ~26 bytes!

Next steps

Feel free to try this out on Replit here! The code can be found on Github here.

Chess encoding (and compression in general!) is a deep and fascinating topic. This post discusses the use of Huffman coding to efficiently store chess games.

If this sounds like fun, you should apply to Recurse Center! The next batch starts on Jan 3 2023, with an information session on Dec 9 2022.

If you’re curious about my take, I’m reachable here. Other RC posts can be found here and here.

[1] The Forsyth-Edwards Notation stores the positions, active color, castling availability, target square, the half-move clock and full-move number.

[2] Since at most 1 pawn is available for en passant capture, we can actually make this more compact. We need 1 bit for whether or not it’s available, plus 4 bits to represent 16 pawns, for a total of 5 bits.

[3] We use n, b, r and q to represent the promotions to knight, bishop, rook and queen respectively. This is purposely chosen, as a contrast to the 0 - 4 representation that follows.

[4] For en passant we need the pawn to remain on its home file. Hence we exclude the pawn from this step if it can be captured en passant. Captures can appear on any file.

[5] Ben Zinberg uses a balls-and-urns argument to come up with 495.

For each string of 0s, 1s and 2s having length 3 in weakly ascending order as you describe, you can imagine writing the string on 5 blank spaces, where there is a ‘divider’ space any time the digit changes. For example, the string 012 would be written 0 _ 1 _ 2 where the _s are divider spaces. The string 000 would be written 0 0 0 _ _ with a string of zero 1s after the first divider and a string of zero 2s after the second divider. The digits to write on the non-divider spaces are uniquely determined by where you place the dividers. Thus, the strings you describe are in one-to-one correspondence with choices of how to place the 2 dividers, and the number of ways to do that is the binomial coefficient $\binom{5}{2}(25)$. This argument generalizes to say, the number of weakly-ascending sequences of integers in $\{ 0, \ldots, k - 1 \}$ having length $n$ is equal to the number of ways to place $k - 1$ divider spaces among $n + k - 1$ blank spaces, which is equal to $\binom{n + k - 1}{k - 1}$.

[6] With a limit of 8 bits for each side, we can fully track at most 4 promoted pawns. Alternatively we note that promotions always involve a capture; we can potentially reclaim 1 bit by convention of denoting captures either left-most or right-most.