Scale-Lifted Dominance for Solving Self-Similar Impartial Games

Many two-player counting games, such as Nim and its relatives where players take turns removing tokens from heaps, have positions whose win/loss pattern repeats at every scale. In three-heap Wythoff's game, the set of losing positions fills out a Sierpiński sponge. For families without a known formula, though, the only way to learn whether a large position is a win is to search. This proposal joins that repetition to dominance pruning, a planning technique that throws away a search state when another state is provably at least as good. We define a dominance relation that is sound for alternating play. We compute it once on a small box of positions. We then use the game's self-similarity to propose the same relation at the next scale up, and we keep only the proposed pairs that pass a cheap verification check. If this works, solving a position at a large scale costs about as much as computing dominance at a small scale plus a verification pass, instead of recomputing dominance from scratch.

The opportunity exists because each field is missing what the other has. Dominance pruning in planning is limited by precomputation. Fine abstractions make simulation relations exponentially expensive, and coarse ones find nothing (Simulation-Based Admissible Dominance Pruning). Self-similar game spaces offer a structured way to reuse a relation across scales. Going the other way, combinatorial game theory proves exact self-similarity only for narrow families. Examples are odd-dimensional Wythoff (Li and Wu) and $(2^m,2^m)$ Wythoff (Aggarwal et al.). It lacks search tools for the open cases next to them: even dimensions, base $(3,3)$, and restricted Wythoff with Grundy values $g\ge 4$ (Gu).

Core Claim

The relation needed here is a game version of a simulation relation, the matching condition that Torralba and Hoffmann carried over from model checking into planning. Write $s \preceq t$ to mean "$t$ is at least as good as $s$ for the player about to move." A relation $R$ is an alternating simulation if, for every pair $(s,t)\in R$, every move $s\to s'$ can be answered by a move $t\to t'$ with $(t',s')\in R$. The roles flip in the successor pair because the mover changes.

Induction on game length then gives soundness. If $s\preceq t$ and $s$ is a win for the mover, then $t$ is too. The argument runs as follows. Since $s$ is a win, it has a move to a losing position $s'$. The matching move from $t$ reaches some $t'\preceq s'$. If $t'$ were a win, then by induction $s'$ would be a win as well, which is a contradiction.

This licenses two kinds of pruning. The first is move pruning: when looking for a winning move, an option $s'$ can be skipped if some sibling $t'\preceq s'$ exists, because $t'$ is a loss for the opponent whenever $s'$ is. The second is a dominance transposition table: a solved win propagates upward along $\preceq$, and a solved loss propagates downward.

Any relation that satisfies the matching condition is sound, not only the largest one. That is what makes lifting safe. A relation guessed from self-similarity costs nothing to propose, and it only needs a single verification pass to be usable.

The concrete claim is this. In heap games whose losing sets are exactly or approximately self-similar under translation by $2^k v$, a relation $R_k$ computed on the box $[0,2^k)^d$ and translated by those offsets will mostly survive verification at scale $2^{k+1}$. When that happens, dominance-pruned search will solve larger single positions than both transposition-table search and dominance computed directly at full scale, within the same time and memory budget.

A constraint shapes the scope. Dominance does not survive disjunctive sums, the composition in which a player moves in exactly one of several independent games per turn. A minimal counterexample shows this. The empty game $0$ has a subset of the options of the one-token heap $*1$, so $0\preceq *1$. Yet $0+*1$ is a win for the mover and $*1+*1$ is a loss. Under sums, the only order-preserving comparison of impartial games is equality of nimbers, the single number that summarises an impartial game's value. This is the structure that Burke et al. treat algebraically and that Müller's decomposition search uses to combine independent local games. The research file's gap of "dominance across subgame tuples" therefore has a negative answer in the naive form. This proposal applies dominance inside single connected games and leaves sums to nimber arithmetic.

Research Program

The first component is the relation itself. Over a box of $M$ positions, the full set of pairs has size $M^2$, which is infeasible for four heaps. We therefore restrict candidates to pairs $(s, s+\delta)$ with offset patterns $\delta$ drawn from a small set $\Delta$. This set includes single-coordinate increments, diagonal increments, and coordinate swaps. It keeps the relation at size $M|\Delta|$, in the spirit of Torralba and Hoffmann's composition over small projections. We compute the largest alternating simulation inside this candidate set by repeated refinement, as a fixed point.

The second component is lifting. For families with proven self-similarity, the offsets come from the theorem: the binary vectors $T(n)$ of Li and Wu, and the cycle modulo $b^2$ of Aggarwal et al. For open families, we propose offsets by searching for translations under which the scale-$k$ losing set best matches the scale-$(k{+}1)$ losing set on a sample. Lifted pairs are then filtered by checking the matching condition and dropping failures until what remains is stable. Usually only a few rounds are needed, because most pairs are already consistent. We will measure the survival rate: the fraction of lifted pairs kept after verification, as a function of scale. This is the central diagnostic, because it measures how much of the game's self-similarity is actually usable for dominance.

The third component is the solver. It is a depth-first win/loss solver with a dominance-aware table. To avoid scanning every stored position, which is the cost Gnad identified (Revisiting Dominance Pruning in Decoupled Search), lookups follow the restricted offsets in $\Delta$, so each check costs $O(|\Delta|)$ hash probes.

Move ordering matters for the same reason Torralba found for A: pruning combined with a misaligned ordering can expand more* nodes. We will therefore compare ordering options by dominance-minimal moves first against ordering by a heuristic.

Baselines

The naive reference point is a depth-first solver with an exact-match transposition table and canonical heap sorting. Sorting heaps is the exact-symmetry reduction that orbit-space search performs in general (K* Search Over Orbit Space, IBM/kstar). Every method gets heap sorting, so that gains cannot be credited to symmetry. Beating this baseline means solving positions with strictly larger maximum heap size within the same 30-minute, 8 GB budget. These limits match the per-instance limits used for the planning-competition evaluations in the file.

The strongest exact competitor is retrograde dynamic programming, which fills the whole box from the bottom up. When the box fits in memory, it answers every position, and it will win for two-heap games and small boxes. The proposal does not try to beat it there. It counts as beaten only on single-position queries where the box is infeasible to tabulate, which happens beyond about $2^{10}$ per heap at four heaps. For Maximum Nim with regular rules, Levine's $O(n)$ generator (Fractal Sequences and Restricted Nim) is the baseline. Our evaluation uses irregular rules, where that algorithm does not apply.

The strongest dominance competitor, and the ablation that isolates the key ingredient, is the same alternating simulation computed directly at full scale over the same candidate set $\Delta$, with no lifting. All other parts of the solver, the table, the ordering, and the budget stay the same. Lifting must reduce total time including precomputation, not only node counts. A second ablation uses lifted pairs without verification. It is unsound and is used only offline, to count wrong answers against an oracle and so show that verification is necessary.

No reported result on Lacuna exists for any solver on these game families. The closest reported effects of dominance pruning come from planning. Torralba and Hoffmann report that blind-search state evaluations in Gripper "dropped by a factor of over 50,000." Torralba reports that action-selection pruning solved "128 more instances than the blind search baseline and 61 more with the LM-cut heuristic" (From Qualitative to Quantitative Dominance Pruning). These figures calibrate what size of gain is plausible but are not directly comparable.

Why not just…?

Why not just tabulate every position with retrograde dynamic programming? For small boxes this is the right answer, and we will say so. The cost grows as $N^d$ times the branching factor, and the Wythoff diagonal move makes branching grow with heap size. Dynamic programming cannot answer a single four-heap position with heaps near $2^{16}$. The experiments locate the crossover point explicitly. If dynamic programming stays competitive across the whole tested range, the proposal fails on its own terms.

Why not just use the closed-form formulas? They exist only for odd-dimensional Wythoff with one specific move set, and for $(2^m,2^m)$ diagonals. Aggarwal et al. report that the structure breaks down at $(3,3)$, and Gu verifies restricted-Wythoff conjectures only empirically up to $g=20$. We use the closed forms as correctness oracles and as a sanity test that lifting recovers known self-similarity. The open families are the targets.

Why not just compute dominance at full scale, without self-similarity? This is the real threat. Within the restricted candidate set, refinement at full scale may be fast enough that lifting adds nothing. The no-lifting ablation decides this directly. If survival rates are high but end-to-end time does not improve, the honest conclusion is that self-similarity explains the dominance structure without making it cheaper to compute.

Why not just apply decomposition search? Decomposition search is the right tool for sums of independent games, as Müller's Go endgame result of "over 28 hours" for alpha-beta versus "0.3 seconds" shows. The counterexample above shows that dominance cannot replace nimber arithmetic across a sum. Our method instead speeds up solving inside each connected component, and the two combine without conflict.

Decisive Checks

The test suite has four parts. The first is odd-dimensional Wythoff at $d=3$ and $5$, with the Nim-sum oracle. The second is even-dimensional Wythoff at $d=4$ and $6$, where geometry is open. The third is $(3,3)$ and $(2,2)$ Wythoff. The fourth is restricted Wythoff and Maximum Nim with irregular rules. Correctness is checked against oracles or dynamic programming wherever these are feasible.

We report four measurements. The first is the survival rate of lifted pairs per scale. The second is nodes expanded and wall-clock time including precomputation. The third is the maximum heap size solved within budget. The fourth is the fraction of move options pruned.

Three outcomes are decisive. On odd Wythoff, survival should be near complete at every scale. Failure there would mean the lifting construction itself is flawed. On even-dimensional Wythoff and $(3,3)$ Wythoff, a survival rate that stays high across scales would be new evidence of usable approximate self-similarity in exactly the families where theory is silent. A collapsing rate would say the opposite, and that is also informative. Finally, the method succeeds only if it beats both the transposition-table baseline and the full-scale dominance ablation on maximum solvable size.