It seems that there is a missed optimization where the order of moves after. Assuming that X always goes first for every board state you know who goes next and the path that you took to get there doesn't matter. So you don't have to store the full sequence of moves that lead to the state, just the state itself.