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?