How to store a chess position in 26 bytes (2022)

I think didn't mention the bit for whose move it is? Luckily, he has a few spare bits.

He starts out by using 4 bits for castling rights.

Then he introduces the other method (signify that castling is allowed by saying the rook on that side is on the same square as the king) and with that method he doesn't need any extra bits for castling rights.

Edit: it would be better on average to keep the castling bits, and omit the positions of kings and rooks if castling is possible. But that's variable length and it's simply 4 extra bits in the worst case.

"The 'bit-level magic' here is misleading. They're using integer representations and calling them bits. A true bit-level approach would encode positions as pure binary streams. For example, their promotion string '00000034' is 8 bytes (64 bits), not the claimed 9 bits. Has anyone implemented this with actual bitwise operations instead of integer packing?

TLDR: You stupi...lovely folks, need learn what a bit is. What is a byte, and why integers are NOT BITS.

And no one called this post out from years ago? Crazy.

Someone ask, and I will show you how to do it in 24 BYTES IN BINARY ENCODING FOR REAL - no fake "integers are bits". And can we use compression techniques? We can get this to 10-12 bytes maybe.

So it beats the fake "26 bytes" and my version is actually real binary bits.

Ask.

I know of two distinct methods of encoding any legal chess position into 24 bytes worst case. In both cases, you get the full position, plus who to move, plus full information on future castling and en-passant possibilities. This is the FEN state of the board, minus the two counts. It's more than the information you get from a published chess diagram in a book or magazine. Although in a book or magazine inevitably "who to move" is represented somehow, castling and en-passant possibilities are not usually.

Method 1: Lichess method; 64 bit header, 1 bit per square indicating occupied squares, then (up to) 32 4 bit codes for the 32 occupied squares. So 24 bytes worst case!

Method 2: My own method a list of 2 bit codes, one of the 4 codes indicates empty square, the other three codes are prefixes for a second 2 bit code. Three prefixes applied to one of 4 code values gives a total of 12 possibilities corresponding to any possible chess piece. Worst case 32x2 bits plus 32x4 bits = 24 bytes.

In each case there is sufficient entropy to create tricks to add the supplementary information (who to move etc.), similar tricks are in the original article.

I mention my own method from my Tarrasch Chess GUI https://github.com/billforsternz/tarrasch-chess-gui only for completeness. If I had known about method 1 I would have used that, it is simpler and better and there is much more entropy available making the tricks easier.

I would urge commentators to keep clear the difference between compressing a chess position (this challenge), a chess move and a chess game. A chess move needs far less bits of course. A complete chess game is always encoded as a list of moves, not positions, for this reason.

Edit: I should have mentioned that the chief advantage of method 1 over method 2 is average bits required. An empty board is 64x1 bits = 8 bytes for method 1 and 64x2 bits = 16 bytes for method 2.

Edit 2: I am going to describe my tricks, just because they are fun. Two kings the same colour means Black to move. Two White kings means the first king is white, two black kings means the first king is black. Otherwise White to move. A friendly pawn on the first rank means an enpassant vulnerable pawn. Swap it with the 4th rank square to get the actual contents of both squares. A hostile pawn on the first rank is an unmoved rook or king, establishing all castling rights. The castling and en-passant tricks can be combined in a pleasant and harmonious way.

Each side has 16 pieces, so you need 32 elements.