A list of actions/moves should be more compact. You'd replay from the initial state. There are at most 9 moves in a game; after that the board is full. The fir

A list of actions/moves should be more compact. You'd replay from the initial state. There are at most 9 moves in a game; after that the board is full. The first move has 9 options, the next 8, the next 7, etc. That's 9! sequences of moves. And this is an upper bound, because some prefixes lead to shorter games. Computing ceil(log2(9!)), we get 19 bits -- not for a game-state, but for an entire play-history. One could do better using an exact game-tree. You could think of it as a simple version of arithmetic coding. Or you could just think of it as assigning an index (0, 1, 2, ...) to each leaf visited in some specified tree-traversal order.