Storing game traces (e.g. Chess, Othello) in a minimal number of bits

Question

I am thinking about the problem of storing traces of games like Chess and Othello in an information-theoretic minimal number of bits. My idea was to think of a game as an ordered tree of possible moves that could be taken.

Let's say in one game there are 20 moves available initially, then 8 on the second turn, then 5 on the third move, then 10 on the fourth turn. In this game, the moves 4/20, 1/8, 3/5 and 3/10 are played.

The idea would be to store the entire game as a single number that is calculated as follows:

4     +   (1 * 20) + (3 * 20 * 8) + (3 * 20 * 8 * 5)
^          ^          ^              ^
turn 1     turn 2     turn 3         turn 4

This sums to 2904 so you could store it in 12 bits.

To recover the game from this number, you'd initially look at the start position and see that 20 moves are available on the first turn. To calculate the move for the first turn, you'd do (2904 % 20) which is 4.

After simulating move 4 in your model of the game, you'd then realise that 8 moves are available for the second turn. To calculate the move for the second turn you'd (integer) divide 2904 by 20 which is 145 and then do (145 % 8) which is 1.

After simulating move 1 in your model of the game, you'd then realise that 5 moves are available for the third turn. To calculate the move for the third turn you'd (integer) divide 145 by 8 which is 18 and then do (18 % 5) which is 3.

... and so on to recover the rest of the moves.

Is this an information-theoretic minimal way to store game traces? It seems like it should be because every number can be mapped to a unique game trace and vice-versa. Is this already known? Is there literature on this approach?

We're essentially using the branching factor of the game tree as the base of a number system. This creates a Gödel numbering system for all possible game traces.

The downside of this approach is that we don't know in advance how many bits are needed to store any possible game unless we exhaust the entire search space of possible games.

Answer 1

If the number of possible moves does not depend on the game history (say, at the third move there are always 5 possibilities), then the "mixed-radix" scheme you describe is optimal, as it encodes all integers in the range of the number of possible games.

But it is difficult to encode/decode because you need to trace the game history, and on every move simulate the possibilities in a predefined order to find the Nth one.

If the number of possibilities does depend on the game history (which is the case for chess and Othello), then your encoding has variable length, so that it isn't the shortest possible in the worst case.

To truly achieve the shortest codes, you may enumerate all games in a canonical order and assign them a sequence number, but this makes encoding and decoding much harder, if not impossible.