5
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 5 at 2:04
  • $\begingroup$ 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. $\endgroup$
    – Vasili
    Apr 5 at 2:22
  • $\begingroup$ @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. $\endgroup$ Apr 5 at 3:37
  • $\begingroup$ 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. $\endgroup$ Apr 5 at 4:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Stef
    Apr 5 at 10:13

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.