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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.