# Efficient game traversal of a DAG of 3-colorings

Let $$X$$ be a set of size $$n$$. Consider a game played on board $$X$$ by two players black and white. Starting with the empty board, each player chooses an empty spot to place a stone. Black moves first. There is some rule determining the winner at each end state, but this rule does not matter for the question. I am interested in memory efficient traversals of the graph of positions in this game.

Formally, $$C = \{e, w, b\}$$ the set of colors each $$x \in X$$ can have (empty, white, or black). Let $$S_k = \{f : X \to C | f^{-1}(w) = \lfloor k/2 \rfloor, f^{-1}(b) = \lceil k/2 \rceil\}$$ be the set of possible states after $$k$$ moves, and $$S = S_0 \cup \cdots \cup S_n$$. We define a leveled directed graph on $$S$$ by connecting each state to all ways of adding one more stone of the appropriate color.

We are given the result of the game at each $$S_n$$, and want to back this up to the result at $$S_0$$. The result at a state depends only on the state and the result of its immediate successors.

The simplest way of doing the traversal is to compute all results for each layer $$S_k$$ in backwards order of $$k$$. The largest layer is at $$k \approx 2n/3$$, and we need to store one input layer and one output layer at a time, so the peak memory is roughly $$2\left|S_{2n/3}\right| \approx \frac{2(n!)}{(n/3)!^3}$$

Question: Is there a way of traversing this graph of positions using significantly less memory, while still computing the result of each state only once? Is there an available time-space tradeoff?

Motivation: A better algorithm here would reduce the memory usage for midgame solving at https://perfect-pentago.net. In this case, $$n = 18$$.