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

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.

• For this you have to choose a way of ordering the options in any given state. For many games that should not be difficult, but I wonder if that is always so. As long as a game state can be represented by a map from one finite (or well-ordered) set to another you can use the lexical order. Oct 2, 2022 at 7:11
• So you have a practical application in mind? If so, it may be more productive to ask about that. Oct 2, 2022 at 7:17