What counts as the same position, and what that is worth

A 4×4 Domineering board with one domino on it, and the same board reflected left to right. Two positions, or one?

Nothing in the rules can tell them apart. Every line of play from the first has a mirror image from the second, the two are worth exactly the same, and a solver that stores them separately is storing the same answer twice. So a solver may store them once — and the table drops from 5,700 entries to 2,932.

Three questions that sound like one #

Is this the same position? is doing three different jobs in a solver, and separating them is most of this essay.

Are these the same object? Two Nim positions written 7, 11, 13 and 13, 7, 11 are not two positions at all. A Nim position is a multiset of heap sizes; the ordering was never part of it, and writing it down in a particular order is an artefact of writing.

Are these related by a symmetry? A Domineering board and its mirror image are genuinely two arrangements of dominoes. They are different objects that happen to have equal values, because the game’s rules are unchanged by the reflection.

Do these have the same value? Two positions with nothing structural in common may still be worth the same, and if they are, they are interchangeable in every sum for ever.

Each of the three licenses folding entries in a table together, and their ceilings are wildly different: the first costs a sort, the second divides by a group, and the third is bounded by nothing at all.

The fold that is really a spelling #

Nim’s sorting is not a saving in the sense the other two are. There is no theorem behind it and nothing was proved: heaps have no order, and a solver that treated 3, 5 and 5, 3 as different positions would simply be modelling the game wrong.

Nothing about a Nim position mentions an order. The rule says take from a heap, the value is the nim-sum of the sizes, and exclusive or does not care in which order it is handed its arguments. So 5, 3 and 3, 5 are one position written twice, and a table that holds both has invented a distinction the game does not make. Sorting the heaps before looking a position up is not a fold; it is spelling the position correctly in the first place, and the factor it saves — a factorial in the number of heaps, which is not small — is a fact about the writing rather than about the game.

Where this becomes interesting is that the same question has a non-obvious answer for other games. Is a Domineering board the same position as its transpose? No — transposing swaps rows for columns and therefore swaps vertical for horizontal, so it carries Left’s moves to Right’s. That is not the same position. It is something else, and something useful, and the next section is about it.

The symmetry that changes sides #

A square has eight symmetries. Domineering may fold by four of them.

The two reflections and the half turn all preserve the distinction between vertical and horizontal, so they carry a position to another position of the same game with the same value. The quarter turns do not: a vertical domino becomes a horizontal one, and Left’s placements become Right’s.

A quarter turn therefore carries a position $G$ to $-G$ — the same game with the players exchanged, which is exactly what negation means. Negation exchanges the two players’ options all the way down, and a quarter turn does precisely that on a board, because it exchanges the two directions a domino can lie in. A position and its negative are worth the same only when both are zero, so the two cannot share a table entry.

Not being allowed to fold by it is not the same as not being allowed to use it. A solver that has computed the value of a board gets its quarter turn’s value for free by negating, which is one pass over a small object rather than a search. So the eight symmetries split into four that shrink the table and four that populate it cheaply, and both are worth taking.

The measurement, and the ceiling it runs into #

Fold by the left–right reflection alone and the 4×4 table goes from 5,700 to 2,932: a saving of 1.94 under a group of order 2. Fold by all four and it goes to 1,522: a saving of 3.75 under a group of order 4.

Neither reaches its ceiling and neither can exceed it. The reason is a one-line argument that decides the whole question:

A position’s orbit under a group of size $k$ has at most $k$ members. Folding the orbit into one entry therefore removes at most $k - 1$ of them, so the table shrinks by a factor of at most $k$.

The shortfall is the positions that are their own mirror image — a symmetric board sits alone in its orbit and saves nothing — and as boards grow the proportion of symmetric positions falls, so the saving creeps toward the ceiling and stops. Measured here: 3.16 on 3×3, 3.35 on 3×4, 3.75 on 4×4.

The generator asserts this rather than reporting it. If a fold ever claimed a saving larger than its group, the figure would refuse to draw, because the claim would be arithmetically impossible and something else would have gone wrong.

The orbit, counted by hand #

The gap between 3.75 and 4 is worth opening up, because it is the whole reason the saving is a measurement rather than a division.

Take the empty 3×3 board. It is unchanged by all four symmetries, so its orbit has one member and folding saves nothing on it. Now place a vertical domino in the top of the middle column. Reflecting left to right leaves it exactly where it was; the half turn and the vertical reflection both send it to the bottom of the middle column. So this position’s orbit has two members, not four, and folding removes one entry rather than three.

Place the same domino at the top of the left column instead. Now all four images differ — top-left, top-right, bottom-left, bottom-right — the orbit has four members, and folding removes three.

So the same board carries orbits of one, of two and of four, and the saving on it is whatever those happen to average to. That is a number to measure rather than a fraction to write down, and it is the smallest board the essay measures.

Across the whole 4×4 game the average works out at 3.75 entries removed per four, because most positions are asymmetric and a few are not. The 3×3 board manages only 3.16, because on a small board a much larger fraction of the positions are symmetric: there is simply less room to be lopsided in.

That direction of travel is worth noting, since it is the opposite of the usual reassurance. The saving improves as the board grows — toward four, and never past it. On a board large enough for the table to be the binding constraint, folding by symmetry is worth almost exactly the group order, and almost exactly the group order is still four.

The shortfall is not a tendency, it is a count #

“Most positions are asymmetric and a few are not” is the right explanation and it is vaguer than it needs to be. The gap between 3.75 and 4 is an exact quantity with an exact formula, and the formula is Burnside’s lemma:

$$\text{orbits} \;=\; \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g)|$$

— the number of orbits is the average number of positions each group element leaves alone. The identity leaves all of them alone, so everything below a saving of $|G|$ is contributed by the other three elements, and each contribution is a count of boards that are literally their own mirror image or their own half turn.

On the 4×4 board: 164 positions are unchanged by the left–right reflection, 164 by the top–bottom one, and 60 by the half turn. Add those to the 5,700 the identity fixes, divide by four, and the answer is 1,522 — which is the number the folding search returns, to the entry. The 388 symmetric boards are the whole of the shortfall, and there is nothing else in it.

The 3×4 board is the more revealing case, because its two reflections do not fix the same number. Forty-four positions are their own left–right mirror and twenty-eight are their own top–bottom mirror, on a board where the two reflections are geometrically interchangeable. The asymmetry is the game’s, not the board’s: Left’s dominoes are vertical and Right’s horizontal, so a vertical domino in a three-row board has fewer places to sit symmetrically than a horizontal one in four columns, and the two counts come apart.

That is worth having because it turns the ceiling argument from an inequality into an identity. The saving is at most the group order is a bound; the saving is the group order times $N/(N + s)$, where $s$ counts the symmetric positions says how far below the bound a particular board sits and why. And $s$ is measured rather than guessed at: 26 of 98 on the 3×3 board, 106 of 550 on the 3×4, 388 of 5,700 on the 4×4 — a share falling from a quarter to a fifth to a fifteenth. That fall is why the saving climbs toward four, and it is a reason a reader can count rather than a tendency they have to take on trust.

The whole of that arithmetic fits in one table, and it is worth setting the four columns out because the first of them swamps the other three and that is the entire content of the lemma.

Notice that the identity’s column is the unfolded table, so the lemma is saying that the folded table is a quarter of the unfolded one plus a quarter of the symmetric positions. That is the whole of the constant factor, written as an equation rather than a bound.

A fold that would be wrong, and what it would cost #

It is worth seeing the failure, because the argument that a fold is legal is short enough to skip and expensive enough to skip badly.

Suppose a solver folded Domineering boards by all eight symmetries of the square, on the reasonable-sounding grounds that the mirror image of a position is obviously the same position. The table would shrink by up to eight, and the values would be wrong.

The 2×3 board is worth $2 \mid -\frac{1}{2}$: Left to move gets a strong position, Right to move gets a weak one. Its quarter turn is the 3×2 board, which is worth $\frac{1}{2} \mid -2$ — the negative, exactly. Store them in one entry and whichever was computed second gets whichever value was computed first, and every sum containing either is now wrong by up to four moves.

Nothing about the drawing announces this. The two boards look like the same board rotated, the fold looks obviously safe, and the wrongness surfaces later as a sum whose value does not match its play. The test is not whether the picture is unchanged; it is whether the rules are unchanged, and here they are not, because the two players do not have the same moves.

The same question, one universe over #

Identification is not a property of two positions on their own. It is a property of two positions relative to everything they might be added to, and moving to a different set of games changes the answer.

Under normal play, two positions are interchangeable when their difference is a second-player win, and that is a global statement: it holds in every sum with every other game there is. Under misère play it fails, and the repair is to fix a restricted universe of games first and ask about interchangeability only inside it. Two positions can be equal in one universe and different in another, which means the fold a solver is entitled to make depends on which games it will ever add together.

That is a strange property for an equality to have, and it is exactly what makes misère play expensive: the identification that costs nothing under normal play — same value, same entry — has to be recomputed for each universe, and the number of classes grows with the universe rather than staying put.

Why a constant factor is the wrong shape #

Set the three savings side by side and the difference in kind is stark.

A table removes routes: on the 4×4 board that is a factor of 1,098, and it grows with the board. Decomposition replaces a product by a sum: on a split 4×5 board that is 2,916 against 108, and it grows with the number of regions. Symmetry divides by four, on this board and on a board of a hundred squares and on a board of a million.

A constant factor never moves a boundary. If a family of positions takes time growing like $2^n$, then folding by symmetry takes it to $2^n / 4$, which is $2^{n-2}$ — two squares of extra board, bought once and for ever. That is a genuinely useful two squares to a person waiting for a result, and it is nothing at all to a statement about how the family scales.

The claim to check is that the four never becomes anything else, and it is checkable over every board the solver can reach.

Read the last two columns together and the shape of the whole saving is there: the shortfall is falling and has nowhere to fall to but zero, so a large board’s saving is four, and four is a number that a growth rate does not notice.

This is the shape of most engineering savings and it is why hardness results are stated the way they are. PSPACE-completeness is a claim that survives every constant factor anybody will ever find, which is what makes it worth proving and what makes it useless as advice about a particular board.

The identification with no ceiling #

There is a fourth fold, and it is the one the subject is actually built on.

Two positions with the same value are interchangeable in every sum, whatever they look like. That is not a symmetry of the board — the positions need have nothing in common — and it is not bounded by any group. It is bounded by how many distinct values there are, which is far fewer than how many positions there are.

At day two that is 256 forms to 22 values, a factor of 11.6, and the factor grows with depth rather than sitting still. Reaching that identification is what canonical form is for: reduce, and two positions that are worth the same become the same object, at which point a table keyed by value collapses them without ever comparing the boards.

The price is that the key is expensive. A board’s occupancy mask is one integer and costs nothing; a value must be computed by the very recursion the table exists to avoid, and then reduced. So keying by value is worth it only when the values are being computed anyway — which, in this subject, they always are.

Where it stops #

Three limits, stated plainly.

Folding costs time per node. Computing a canonical representative of a board under four symmetries means constructing four boards and taking the smallest, which is four times the key work at every node. On the boards measured here that is a poor trade — this site’s own solver does not fold Domineering by symmetry, and the table sizes reported everywhere else are the unfolded ones — and on boards large enough for memory to be the binding constraint it becomes a good one. The crossover is an engineering question about a particular machine, not a fact about the game.

Symmetries of the position are not symmetries of the game. A board that happens to look symmetric in a game whose rules are not — Toads and Frogs on a strip, where the two players move in opposite directions — cannot be folded at all, and the temptation to do it anyway is strong because the picture looks so obliging.

Nothing here identifies positions across different games. A Clobber board worth ∗ and a Nim heap of one are the same value and are not the same position; a solver may share the value entry and cannot share the board entry. A 2×2 Clobber board and a 3×3 one can both be worth ∗ without either being a symmetry of the other, and no fold on the board would ever have found the coincidence — only a fold on the value does, which is the fourth identification again and the reason it is the one with no ceiling.

Who noticed, and where the idea came from #

Folding search states by symmetry is old and general: it appears wherever a state space has a group acting on it, and the observation that the saving is bounded by the group order is immediate once the orbit is the object being counted.

What the subject here adds is the fourth identification, and it is genuinely a different animal. Equality of games is defined by play — $G = H$ exactly when $G - H$ is a second-player win — and it is a claim about behaviour in every sum rather than about resemblance. That is why it has to be decided by a search of its own rather than read off, and why the canonical form is worth the trouble: it turns a question about behaviour into a comparison of two written objects.

There is one more reason the fourth identification is the interesting one, and it is not about speed. A solver that folds by symmetry ends up with a smaller table of the same objects. A solver that folds by value ends up with a table of values, which is a table about the subject rather than about the board — every entry in it is reusable by a completely different game that happens to be worth the same. The first is bookkeeping and the second is the theory.

Three savings measured, and one of them turns out to be capped by a group. The next rung goes after the thing that is not capped, and asks what it costs to answer a question when the two players are choosing alternately — because alternation, and not size, is what separates a puzzle from a game.