# Can a chess game be represented by less than 10N bits, where N is the number of moves (ply) in the game?

I started wondering how much information is required to encode a Chess game. Since there are 64 squares on the board, it seemed that 12 bits would be required to encode a move, 6 for the starting square and 6 for the ending square.

However, we start with some additional information. There are 32 pieces on the chessboard, and each one can be labeled 0-31, requiring 5 bits of information. A queen at the center of an open board has 27 possible moves. No other piece can have more legal moves than that. Therefore we can come up with a scheme to encode the moves of each piece in 5 bits or less. Therefore, we should be able to encode an entire Chess game in 10N bits, where N is the number of moves (ply)? Does a more efficient encoding exist, and is there a general method to approach such problems?

• Usually in subjects like this a move is one by both players, while a ply is a move by one player. If you accept that, it should be $10N$ where $N$ is the number of ply. Apr 5 at 2:04
• Since the starting position is always known, you only need to record/encode the ending square. Also, all pawns of one color can be represented by the same label (ditto for rooks & knights) so you can get by with 14 distinct labels. Apr 5 at 2:22
• @RossMillikan That is a fair point, but I wasn't sure if that terminology would be familiar to non-Chess players. I'll edit my post to clarify. Apr 5 at 3:37
• When you say encode an entire chess game, I assume you mean encode all of the moves from start to finish by both players. It's not possible to encode every possible chess game in a finite number of bits because theoretically a chess game can go on forever. Apr 5 at 4:03
• Note: there are 32 pieces on the board, but only 16 pieces that belong to the player on turn. So you only need 4 bits, not 5 bits, to encode the moving piece.
– Stef
Apr 5 at 10:13

You have proven that $$10N$$ bits suffice for a game of $$N$$ ply. This thread challenges people to find the chess position that has the most legal moves. The answers were barely over $$100$$. Assuming this does not go above $$128$$ we are down to $$7N$$. Those positions had many white pieces and a single black king, so black's moves could be encoded in $$3$$ bits. It would be interesting to find the position with the maximum product of white's moves times black's responses. This answer says the canonical number is $$35$$ moves for one side and claims there is no solid justification. Another in the thread shows a graph of average moves available in a large sample of games. It peaks close to $$40$$ for white's $$15^{th}$$ move but is below $$32$$ almost all the time. This would get you close to $$5N$$. You would just have a way to list all the possible moves for a position in order, then use the minimum number of bits to pick a move out of the order. You could improve this by computing all the two ply continuations and picking one out of the list. That could save you fractions of a bit per ply, but it will be hard to quantify.
I think trying to do much better than this requires careful though about the rules of chess. The opening position has $$20$$ moves available, which needs about $$4.322$$ bits. After a little while a number of the moves are captures. Those will often reduce the future options, so we could assign extra bits to encode a capture and save some fractions of a bit for noncaptures.
You could even apply standard compression algorithms to the normal algebraic notation for a game. That would probably not reduce to just $$10$$ bits per ply. It might be interesting to experiment.