What it costs to notice a repetition

What counts as the same position ends on a number and a bound. Fold a 4 × 4 Domineering board by its four symmetries and the table drops from 5,700 entries to 1,522 — a saving of 3.75 — and it can never be more than 4, because an orbit is no larger than the group acting on it. That is a clean result and it is only half a ledger. It prices what the identification is worth and says nothing whatever about what it costs to take.

The cost is easy to overlook because of where it falls. The saving is in a table, which is a thing that can be looked at afterwards and counted. The price is spread over the search that built the table, one small payment at a time, and it never appears anywhere as a total. So it is worth totalling.

Seventeen and a half. The folded search is not a slightly more expensive way to build a smaller table; on this accounting it is an order of magnitude more expensive, and the order of magnitude is not an artefact of a badly written canonicaliser. It is where the work has to go.

Why the price is per move and the saving is per entry #

The asymmetry is structural and it is the whole of the essay in one paragraph.

A canonical form is not computed once for each entry in the table. It is computed once for each position the search takes off its stack, which is once for every move it has ever walked down — and a search walks down enormously more moves than it stores positions. On the 4 × 4 board the unfolded walk takes 32,465 positions off the stack to store 5,700, because most of what it pops it has seen before. The folded walk pops 8,741 to store 1,522. Both ratios are close to six.

So the fold reduces the pops, by exactly the factor it reduces the table. And then it charges four mapped boards for every single one of the 8,741 that remain. Four mappings of a sixteen-square board is 64 square-moves; times 8,741 is 559,424, against a bare search whose entire cost was 32,465 lookups. The saving is real, it is 3.75×, and it is applied to the smaller of the two numbers being compared.

That is not an argument against folding. It is an argument that the two quantities are not commensurable and that calling the fold a “saving” without saying of what is how the price stays invisible. The price of asking what the parts are makes the same move for decomposition; this is the same accounting applied to the other of the two standard reductions.

It is worth being explicit about the cost model, because a reader who has written this code will object that nobody canonicalises by mapping squares one at a time. They are right, and it does not matter. A real implementation precomputes each symmetry as a permutation of the sixteen bit positions and applies it with a table lookup or a handful of shifts and masks, which is far cheaper than sixteen conditional bit sets. What it cannot do is get below four applications, because there are four group elements and the canonical form is the least of the four images. So the honest floor is |G| applications of something, and the something is at best a few instructions and at worst a loop over the board. The measurement here uses the worst case, states that it does, and is interesting only for the ratio — which is bounded below by four lookups against one, and is four rather than eighteen if the permutation is free. Four is still four times the cost of not folding.

A cleverer canonicaliser can also stop early. Comparing the four images pairwise, most positions differ from their mirror in the first few squares, so a lexicographic comparison that short-circuits rarely reads the whole board. That is a genuine constant-factor win and it does not change the shape of anything: the number of calls is unchanged, the group order is unchanged, and the growth with board area is unchanged, because the positions that do not short-circuit are exactly the symmetric ones, and those are the positions the fold does not help with anyway.

The two numbers do not have the same shape #

One board is an anecdote. The reason to measure several is that the saving and the price change differently as the board grows, and that difference is the thing worth knowing.

The saving column is the rung below’s result seen from the side: 2.00 on a 2 × 3 board, 3.16 on a 3 × 3, 3.75 on a 4 × 4, 3.92 on a 4 × 5, and it will keep creeping towards 4 without arriving, because the empty board is fixed by every symmetry on every board there is and so at least one orbit is always a singleton. That column is bounded by a fact about groups, and no amount of engineering moves it.

The price column is bounded by nothing. Canonicalising is four applications of a permutation of the squares, and a permutation of the squares costs a step per square. Twenty-seven and a half operations per position not visited on a 4 × 5 board, against twenty and a half on a 3 × 4. The growth is close to linear in the area, which is exactly what the construction says it should be, and the figure asserts the direction rather than describing it: the sweep refuses to draw if a larger board ever comes out cheaper per position saved.

The three smallest boards sit above that trend rather than below it, and the reason is worth a sentence because it looks like an exception and is not. On a 2 × 3 board the fold saves a factor of two, so there is very little being bought and the fixed cost of buying it dominates. The dip at 3 × 3 and the rise afterwards is the fixed cost falling away and the area cost taking over. Two effects, crossing, with the minimum where they meet.

The last column is also the one to read if the question is when does this stop being worth it, and the answer there is: on this accounting, never, because the other side of the comparison grows faster. But the arithmetic that gives that answer is set out at the end of this essay rather than assumed here, because it is the step everybody skips. A price column that grows and a saving column that is capped is a shape that looks like an eventual crossover, and it is not one — what it is is a shape that makes the conclusion depend on a third quantity nobody has measured.

Where the symmetry actually lives #

A saving of 3.75 averaged over a search says nothing about whether the saving arrives where the search is spending its time. It could all be arriving at the top of the tree, which would make it nearly worthless.

It does not. The fold is worst at exactly the two levels that hold one position apiece: the empty board, which is its own image under everything, and the full board, likewise. Both fold 1.00×, both are unavoidable, and both are irrelevant, because between them they are two positions out of 5,700.

Where the positions are, the fold is at its best. Depth four holds 1,911 positions and folds 3.78×; depth five holds 1,868 and folds 3.83×; together they are two thirds of the board’s whole position set and both are above the board’s own 3.745 average. The generator asserts precisely that — that the busiest level folds better than the board as a whole — and refuses to draw if it does not, because “the fold is worst where the work is” would be a different essay and it should not be possible to write this one by accident.

Two thirds is a strong enough concentration that the average is nearly the number that matters, and it is worth saying why the distribution has that shape at all. A Domineering position at depth d is a placement of d dominoes, and the number of ways to place d dominoes on a sixteen-square board rises and then falls: at first because there are more of them to arrange, and at the end because there is nowhere left to put them. The peak is a little past halfway. The symmetry rate follows the same curve for the same reason — a position with a middling number of dominoes has enough freedom to be asymmetric and enough room to be reached, and the two conditions coincide.

There is a small parity fact in the last column, and it is the sort of thing that is easy to state one board too widely. A position fixed by every symmetry is symmetric about both midlines at once. On a 4 × 4 board neither midline passes through any square, so no domino can lie across one, so no odd number of dominoes can be arranged symmetrically — and every entry in the last column at an odd depth is nought. On a 4 × 5 board the middle column exists, a vertical domino can sit in it, and the odd depths stop being empty. The check in the figure is conditioned on the board’s parity for that reason rather than asserted flatly, which is the difference between a claim and a coincidence that has not yet been contradicted.

Fourteen positions that pay and do not benefit #

The shortfall from 4 to 3.745 has a location as well as a size.

Fourteen positions out of 5,700 are their own entire orbit. Each of them is canonicalised exactly as any other position is — four mappings, a minimum, a lookup — and each removes precisely nothing from the table, because there was nothing to remove. Another 173 sit in orbits of two, each saving one entry for the same price. The 1,335 orbits of full size do 96 per cent of the work.

This is the shape what counts as the same position derived from Burnside’s lemma without saying what it looked like on the ground. The lemma says the orbit count is the average number of positions the group elements fix, so the entire shortfall from a perfect four-fold saving is the positions fixed by something other than the identity. Here they are, counted: a small, symmetric, cheap-to-reach set of boards that pays full price and receives nothing.

That set does not grow. It cannot grow much, because being symmetric about two axes is a stringent condition and the number of positions satisfying it is roughly the square root of the number that do not. Which is why the saving creeps towards its ceiling instead of stalling: the freeloaders are a shrinking fraction, and 3.917 on a 4 × 5 board is already 98 per cent of everything available.

The middle row deserves a moment too, because it is the one that is easy to misread. An orbit of two is a position fixed by exactly one of the three non-identity symmetries — its own left-right mirror but not its own upside-down one, or the reverse, or its own half turn and neither reflection. There are 173 of them on a 4 × 4 board and each removes one entry rather than three. They are not a rounding error in the argument; they are four per cent of the saving and about eleven per cent of the orbits. What makes them worth naming is that they are the reason the shortfall is not simply “the fourteen fully symmetric boards”: the sum in Burnside’s lemma runs over group elements, not over orbits, and a board fixed by one element contributes to that sum exactly as much as a board fixed by three contributes three times.

Put the three rows together and the sentence they make is the useful one. Of the 4,178 entries the fold removes, 4,005 come from positions with no symmetry at all. The saving is produced almost entirely by the asymmetric positions, and the symmetric ones — the only positions anybody thinks about when they think about symmetry reduction — are where it fails.

The currency the fold is actually paid in #

Everything so far says the fold is expensive. It is also, in every solver anybody has written, unambiguously correct to do. Both are true, and reconciling them is the point of the rung.

The seventeen-and-a-half figure counts elementary steps in a search whose only job is to enumerate positions. Nobody wants an enumeration. What a solver wants is the value of each position, computed from the values of its options, and that computation is not one lookup — it is a recursive construction of a game, a simplification to canonical form, and a comparison against the values already known. Comparison is a search is the essay about how expensive the last of those is on its own.

Measured against that, the fold’s price is 23.6 square-mappings for each position it prevents being evaluated, and a position evaluation is many thousands of operations. The fold pays by three or four orders of magnitude, and it pays because the two quantities scale apart in the direction that happens to favour it.

The measurement behind that claim also checks the thing that makes the whole reduction legal, which is not automatic and is worth stating as a condition rather than a background fact. Folding two positions together asserts they are worth the same. That is true here because each of the four symmetries maps vertical dominoes to vertical dominoes and horizontal to horizontal, so Left’s move set goes to Left’s and Right’s to Right’s, and the two positions are literally the same game with the squares renamed. It is checked directly rather than argued: every position of a 3 × 4 board is evaluated, and every member of every orbit is required to carry the same value as its representative.

The check has a companion that fails on purpose. A quarter turn is also a symmetry of a square board, and folding by the full group of eight would save twice as much — except that a quarter turn takes a vertical domino to a horizontal one, which swaps the players and negates the value. So the generator, on a square board, looks for a position that disagrees with its own quarter turn and refuses to draw if it cannot find one. Finding one is the evidence that the group was correctly cut down to four; not finding one would mean the group could have been eight and half the available saving had been left on the table.

But it is a ratio, not a law, and the ratio narrows. The price per position saved grows linearly with the board’s area. The cost of evaluating a position grows too, and faster — so the margin widens, on Domineering. On a game whose positions are cheap to evaluate and expensive to canonicalise, the same arithmetic would come out the other way, and there is nothing in the literature of symmetry reduction that would say so, because the price is never quoted.

The identification worth having #

There is a last measurement, and it is the one that puts the ceiling of four in its place.

Five hundred and fifty positions. One hundred and sixty-four orbits. Thirty-nine distinct values.

Symmetry is not the identification a Domineering search would choose if it could choose. Identifying positions by what they are worth would collapse the same board fourteen-fold rather than three-and-a-third-fold, and unlike symmetry it has no ceiling — the number of distinct values grows far more slowly than the number of positions, so the factor improves without limit as the board grows. It is strictly the better relation.

It is also unavailable. Folding two positions together by value needs both values, and knowing the values is the entire content of the search. The reduction is perfect and it is circular, which is why every practical solver uses the worse one.

That is the real economics of identification and it generalises past this board. An identification is characterised by two numbers: how much it collapses, and how much has to be known already to apply it. Symmetry collapses a little and requires nothing — a position can be canonicalised without ever having been evaluated, on the way in. Value equality collapses a great deal and requires everything. In between sit the reductions that make real solvers fast, and they are all in between: decomposition needs only the board’s shape and buys a product against a sum; a check in front of a search is a cheap test that settles some positions outright and leaves the rest; the bound instead of an answer is the same trade with the collapse made partial rather than the knowledge made cheap.

Set that bar chart beside the sweep and the whole argument is visible at once. The bar is what the identification buys and it is genuinely bought — the table is smaller, memoisation has less to hold, and the search that fills it visits 3.75 times fewer positions. Nothing here retracts any of that.

What changes is what the bar and the ceiling are understood to be. They are not the result of the optimisation. They are the credit side of it, and the debit side is 559,424 square-mappings that nothing in the rung below counted. Both halves are needed to say whether a reduction is worth taking, and a subject that reports only savings will eventually recommend one that is not.

What to carry to the next reduction #

Three things, and none of them is about Domineering.

Price a reduction in the unit the search actually spends. Table entries are a convenient unit because they are visible at the end; operations are the unit that gets paid, and the two can differ by a factor of eighteen in the direction nobody checks.

Ask what bounds each side. A saving bounded by a group order is bounded for a reason that no engineering will move, and it is worth knowing that early — a bound instead of an answer is worth having when the bound is the interesting part. A price bounded by nothing will eventually meet the saving, and where they meet is a board size that can be computed rather than discovered.

Notice that the two reductions on this site compose rather than compete, and that composing them is where the accounting gets genuinely hard. A decomposed board’s regions can each be folded by their own symmetries; a folded position can then be decomposed. The savings multiply, and so do the prices — but not independently, because canonicalising a board about to be split is work that could have been done on the pieces instead, at a lower cost per square and on a smaller group. Which order to do them in is a real question with a measurable answer, and it is not the question either rung has asked. A product against a sum is the arithmetic for one of the two; there is no corresponding arithmetic for the pair.

And be suspicious of a reduction whose price is invisible because it is spread thinly. The fourteen fixed positions on a 4 × 4 board are the miniature of the whole problem: each one pays a cost small enough that nobody would object to it, receives nothing, and is only visible when somebody adds them up. The fold survives that audit comfortably, on this game, at these sizes. The audit is the part worth keeping.