Remix.run Logo
jcranmer 3 hours ago

The king can reach any of 64 tiles. Rooks, queens, and knights can also do so, but they can also be captured, so 65 states for those 5 pieces. Bishops can only reach half of those tiles, so those two pieces get 33 states each. Pawns are interesting: they can promote into 4 pieces that each can move 64 tiles, they can be captured, or they can move into a somewhat variable number but 20-30ish positions as a pawn, or about 290 states per pawn. This means it takes 111.something bits to represent the board position of a color, or rounding up, 224 bits to represent the board positions of both black and white. En passant and castling restrictions don't add to the bit representations once you round up, since that's just 1 extra state for several pieces. That's probably the most compact representation for a fixed-size direct board representation.

For a sparse representation, note that both kings have to exist, so you can represent the live pieces with a base-10 number of n digits with n + 2 64-bit numbers representing piece position, and a little bit extra information for castling and en passant legality. If half the pieces are gone (a guesstimate for average number of pieces on the board), that amounts to about 180 bits for a board representation.

Move history requires about 10 bits per move (pair of white/black turns, with a ply of around 32 = 5 bits), which means you get to 18 moves, which appears to be somewhat shorter than the halfway point of an average chess game.

To be honest, it looks to me like getting more compact than the upper hundreds will require building impossibly large dictionaries.