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

Question

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?

Answer 1

There certainly are more compact encodings, because the encoding scheme could be position dependent. For example, at the start and in the end game there are many fewer possible moves.

What you would save in space by using fewer bits you would pay back in time en- and decoding, which would require more processing.

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.

Answer 2

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.