A position reached eleven ways is one position

A 3×3 Domineering board has nine squares. Left places a vertical domino, Right a horizontal one, and a player who cannot place loses. Play it out on paper and the game is over in three or four moves.

An exhaustive solver, asked what the board is worth, evaluates 98 positions. A solver that has forgotten every position it has already seen evaluates 869.

Two objects, and only one of them is the game #

The picture in most people’s heads when they hear game tree is a tree: the opening position at the top, a branch for each move, growing downward until the game ends. It is the standard drawing and it is drawn in every textbook, including in the essay that introduces the recursion here.

It is also, taken literally, an enormous overcount, and the reason is a single sentence: the same position can be reached by more than one order of moves. On the 3×3 board, Left’s vertical domino in the left column and Right’s horizontal domino across the bottom do not interact. Playing them in either order arrives at the same nine squares with the same four covered. That is one position, and a tree contains it twice.

Once a move can be played early or late, the count of routes stops being the count of positions and starts being something much larger. The right object is not a tree at all. It is a directed graph whose vertices are positions and whose edges are moves, and every position in it appears exactly once however many ways there are to arrive.

It is worth being concrete about why two moves on that board commute. Left has three vertical placements in each of three columns and Right three horizontal ones in each of three rows — the two players see completely different games on the same squares, which is what makes Domineering partizan — and a placement in the left column and one across the bottom overlap in no square at all. Neither changes what the other may do, so the two orders are two routes and one destination.

The counts, and how far apart they get #

The number to hold onto is not the ratio on a small board. It is how the ratio behaves as the board grows.

On 2×3 there are 18 positions and 48 routes: a factor of under three, and forgetting costs almost nothing. On 3×3, 98 and 869. On 3×4, 550 and 31,752. On 4×4 — a board somebody could draw on a napkin — there are 5,700 positions and 6,257,129 routes, a factor of 1,098.

The factor is not a constant being exceeded. It is growing with the board, and it grows because every extra pair of independent moves doubles the number of orders they can be played in. A board with many non-interacting regions has factorially many orders and one position.

That is a claim about a rate rather than about a number, so it is worth checking as one: from each size to the next, does the route count multiply by more than the position count does?

Nim makes the point without any board at all. Three heaps of 7, 11 and 13 counters have 480 distinct positions — every triple of heap sizes no larger than the original, with the heaps unordered. The recursion tree over the same game has 75,707,699,717,937,900 nodes.

That number is not an estimate. It is a BigInt, computed bottom-up through the position graph: the size of the tree rooted at a position is one plus the sizes of the trees rooted at its options, and adding those up needs no walking of the tree itself. A count of 7.6 × 10¹⁶ overflows a double, so a figure printing it as a plain JavaScript number would have the last four digits wrong. This site’s habit is that a quoted number is a computed number, which means being careful about the arithmetic used to compute it.

What “the same position” is allowed to mean #

There is a decision hidden in the word distinct, and it is worth exposing before it does any damage.

For Nim, the 480 counts heaps 7, 11, 13 and heaps 13, 11, 7 as one position, because a Nim position is a multiset of heap sizes and nothing about the game can tell the two apart. For Domineering, the 5,700 counts a board and its mirror image as two, because this solver does not fold boards by symmetry.

Both are choices, and the figures here declare which one each family made. They matter because the second number in every row depends on them: identify more positions with each other and the table shrinks. There is a whole essay on how much that is worth, and the short answer — the saving is bounded by the size of the symmetry group, so it can divide by four and never by four thousand — is the reason it is a different essay rather than this one.

The first number, the count of routes, does not depend on the choice at all. A route is a sequence of moves, and there are as many of them as there are.

The mechanism: a table, and what goes in it #

The repair is one line of code and it is the same line in every solver ever written for a game like this. Before evaluating a position, look it up. If it has been seen, return the stored answer. If it has not, compute it and store it.

That is memoisation, and describing it as an optimisation undersells it badly. An optimisation makes a program that works work faster. This makes the difference between a program that answers and a program that does not: at 6.3 million nodes a solver spends seconds; at 7.6 × 10¹⁶ it spends longer than the subject has existed.

What goes into the table is worth being precise about, because it is not the outcome. It is the value — the game object obtained by recursion and reduced to canonical form — and storing the value rather than the winner is what lets the entry be reused in a position that contains this one as a component. The whole disjunctive sum theory is a claim about that reuse.

Why the ratio differs so much between games #

Clobber on 3×3 has nine stones and a ratio of 67. Toads and Frogs on nine squares has a ratio of 620 million. Both are nine-cell games. The difference is not size and it is not branching factor.

It is how much of the board a move destroys. A Clobber move removes a stone: the position after it has strictly fewer stones, and the number of distinct move sequences reaching a given board is limited by how few ways there are to arrive at exactly that arrangement. A Toads and Frogs move slides a piece one square, or hops it over one other piece, and the strip stays the same length with the same pieces on it for a very long time. Many sequences reach the same strip, and the ones that do not are still walking around a small set of arrangements.

Put crudely: a game whose moves commute has a small graph and a huge tree. A game whose moves interfere has a graph closer in size to its tree. Domineering sits between the two, and moves from one end to the other as the board grows — which is exactly what the rising factor in the first figure shows.

What the ratio measures, and what it does not #

The last section says the ratio is a property of how independent the moves are, and the word independent is doing two jobs on this site. Separating them matters, because the ratio measures one of them and a reader will assume it measures the other.

Commuting is what the ratio measures. Two moves commute when playing them in either order reaches the same position, and $k$ pairwise-commuting moves give $k!$ routes to one destination. That factorial is the whole of why the tree outruns the graph, and it is why the numbers are as violent as they are.

Decomposing is something stronger. Two parts of a position are independent when a move in one changes nothing about what is available in the other — not merely that two particular moves can be swapped, but that neither part’s option list ever consults the other. That is the hypothesis the disjunctive sum needs, and it is what makes a value reusable.

The two are not the same, and the essay’s own table contains the witness.

Toads and Frogs, which commutes and does not decompose #

A nine-square Toads and Frogs strip has a ratio of 620 million — the largest in the survey, and by a wide margin. So its moves commute about as thoroughly as moves can: sliding a toad at one end and a frog at the other reaches the same strip in either order, and a strip of nine squares supports a great many such swaps.

And the game does not decompose at all. A strip has no independent regions: any two animals are separated by squares that either of them may eventually occupy, and a hop can reorder pieces, so there is no cut that a move cannot reach across. The essay on the family says so and it is the reason no formula for it exists.

So the two properties come apart completely, in the essay’s own second figure. A huge tree-to-graph ratio is not evidence that a game decomposes, and a reader who takes the first figure’s rising factor as a sign that Domineering is becoming more decomposable has read the wrong quantity.

Which is why the two savings are separate essays #

That distinction explains something about the shape of this field’s toolkit that is otherwise a coincidence.

Memoisation exploits commuting. It needs only that two routes arrive at the same position, and it works on any game where they do, with no theory required — a hash table and a key.

Decomposition exploits independence. It needs a theorem, it produces a value rather than a stored answer, and what it buys is reuse across different positions rather than within one search.

A game can have either without the other. Toads and Frogs has the first and not the second: memoisation turns 874 billion routes into 1,400 positions, and no decomposition is available afterwards. A board split by a wall into two solved regions has the second and, if the regions are small, little of the first.

And a game with both is where the whole apparatus pays. Domineering commutes heavily and falls apart into regions, so memoisation makes a single board affordable and decomposition makes the answer reusable in every larger board containing that region. Two savings, two mechanisms, and the essays are separate because the properties are.

What is kept, once the search is over #

The search is expensive; the thing it produces is not.

The counts in that figure are smaller than the position counts above and the difference is a third identification, not an error. A form node is a game object, and two different boards that turn out to be the same game are one node in it — so 4×4 Domineering’s 5,700 distinct boards expand to 562 distinct forms, and Clobber’s 1,921 boards to 91. The position key folds together the routes that reach one board; the form folds together the boards that are one game. Toads and Frogs folds least, from 1,400 boards to 1,129 forms, which is the same fact its enormous route ratio reports from the other side: a strip is nearly all commuting moves and nearly no coincidences of value.

A nine-square Toads and Frogs strip, with three toads and three frogs and three gaps, is worth 0. Not approximately zero, and not zero on the evidence of a few lines — the second player wins with correct play, and the object recording that fact is a single symbol. Getting it required expanding 1,129 nodes.

That trade is the economics of the whole subject. An expensive search once, and afterwards a small object that can be added to any other small object. A component whose value is known can be dropped into any sum without being searched again, which is the reason decomposing a board is worth so much and the reason values are the thing worth storing.

It also explains why the canonical form matters computationally and not only aesthetically. Two positions with the same value are interchangeable in every sum, so the table can be keyed by value rather than by position — and the number of distinct values is far smaller than the number of distinct positions, since 256 forms carry only 22 values even at day two.

The key is not free #

A table is only as good as the thing positions are looked up by, and choosing that key is where most of the practical difficulty of a solver lives.

The key has to be cheap to compute, because it is computed once per node visited, and at six million nodes a key costing a microsecond costs six seconds on its own. It has to be complete, in that two positions with the same key really are the same position — a key that collides silently returns the wrong value and nothing announces it. And it should be canonical, in that two positions that are the same get the same key however they were arrived at.

Nim shows all three at once. Its key is the sorted list of non-empty heaps, which costs a sort, cannot collide, and folds every ordering of the same heaps together. Domineering’s key here is the raw occupancy mask, a single integer: cheaper still, and deliberately not canonical, since folding by symmetry costs more per node than it saves at these sizes.

The third property is the one worth noticing, because it is the same idea as reducing a position to canonical form transplanted from values to positions. In both cases the work is to find a representative that many different objects share, and in both cases the payoff is that everything downstream stops seeing the difference.

Counting routes without walking them #

There is a small joke in the numbers above, and it is worth spelling out because it is the whole essay in miniature.

The count 6,257,129 is the number of nodes a solver without a table would visit. Counting them by visiting them would take exactly as long as the search being criticised — and for 7.6 × 10¹⁶ it would never finish at all.

So the count is not taken that way. The size of the tree rooted at a position is one plus the sizes of the trees rooted at each of its options; that recurrence is computed once per distinct position, bottom-up, in a table. Measuring the cost of forgetting takes 5,700 additions rather than six million visits, and the measurement of the wasteful method is made by the efficient one.

It is the same manoeuvre as working backwards from the positions where somebody has already lost: fix an order in which every position’s answer depends only on answers already computed, then sweep. Whether the quantity being propagated is an outcome, a value, or the size of a subtree changes nothing about the method.

Where the shortcuts sit relative to all this #

Memoisation is a saving that applies to every game whatever. It costs memory, it changes no answers, and it needs no theorem. It is also, on its own, nowhere near enough.

The contrast that makes the point is Nim beside Domineering. Nim’s cost under a closed form is flat — three exclusive-ors, whatever the heaps — while its search cost is the 480 positions and 7.6 × 10¹⁶ routes counted above. Domineering has no closed form at all after fifty years, so its only column is the search one, and that column grows by a factor of roughly ten every board.

Nim’s 480 positions are 480 positions that never need to be visited, because the nim-sum answers the question in three exclusive-ors. That is a theorem doing the work, and what the theorem buys is not a constant factor — it removes the search entirely.

The ordering is worth stating plainly, because these three are constantly conflated:

• A theorem removes the search. Nim, green Hackenbush, Cutcake.
• Decomposition replaces one search by several smaller ones, turning a product into a sum.
• A table removes the redundancy inside whatever search is left.

Only the first changes the problem. The other two make the problem affordable, and they are the two that apply when no theorem is known — which for Domineering is still the situation after fifty years.

What the picture cannot show #

The graphs drawn here are all small enough to walk, and that is precisely the population this figure can report on. The interesting boards are the ones where the table does not fit in memory, and nothing here says what happens then.

The honest limit: the counts above stop at 4×4 Domineering because 5×5 has enough positions to make the figure take longer to draw than it is worth, not because anything changes. And a solver whose table does not fit has a genuinely different problem — it must choose what to forget, and every choice reintroduces some of the routes this essay just spent itself removing. That is a question about space rather than about time, and it is where the whole subject’s complexity class comes from.

There is a third column in the first figure that the essay has not read, and it is the one that question turns on.

That asymmetry is the whole reason the subject’s hard problems are PSPACE-complete rather than something worse. A solver that keeps no table needs time proportional to the routes and space proportional only to the deepest line, because it can throw away each branch as it finishes with it. Memoisation trades the second for the first — it buys back the routes at the price of storing the positions — and the choice between them is what a solver whose table will not fit has to make, one position at a time.

Who noticed #

Memoising a game search is old enough to have no single inventor; the idea that the object being searched is a graph rather than a tree arrives with dynamic programming in the 1950s, and in game programming it acquired the name transposition table — a transposition being exactly the move-order swap that makes two routes meet.

What combinatorial game theory adds is the reason the table entries are worth so much more here than in a chess engine. A chess transposition table stores an evaluation that is only valid for that position. A table here stores a value, an algebraic object, and the theorem that makes values add means the entry stays valid inside every position that contains this one as a part. The table is not a cache of answers. It is a library of components.

The next rung takes the second saving in the list. A table removes duplicate work inside one search; decomposition removes the search, by noticing that a board in pieces is not one problem but several, and that the arithmetic connecting them is addition rather than multiplication.