A product against a sum

Equality in a restricted company licenses a rewriting, and which rewriting depends on which closure the company has. The closure that picks the nimbers established the pair: a company closed under addition licenses rewriting a component of a sum, one closed under taking options licenses rewriting a subposition, and among the finite companies exactly the groups of nimbers have both — four of the seven tested.

It closed on the price nobody had put on that:

A company with both permits a full recursive re-evaluation with substitution at every step, which is exactly what a solver wants … Measuring what that shortcut is worth on a real search, against the cost of computing without it, is a piece of work the site’s cost machinery could do and has not.

It is the difference between a product and a sum.

What a solver does without it #

A board of several components is one game, and a solver that treats it as one game searches the product: a state is a tuple of the components’ positions, and there are as many states as the product of the components’ position counts.

Two Cram boards of nine and eight squares have 98 and 54 positions between them; their product search walks 3,839 states, which is not 98 × 54 = 5,292 only because many tuples are unreachable once both boards have been played in. The two searches the licence replaces it with walk 152 between them, and the answers agree: the exclusive-or of the two Grundy values names the same winner.

Add a third component and the product multiplies while the sum adds. A 3 × 3 beside two 2 × 3 boards is 21,535 states against 134 positions — 161 times — and the four triples measured run from 24 to 161 against the pairs’ 4 to 25.

The growth is worth stating as arithmetic. With $k$ components of $n$ positions each, the product search is bounded by $n^k$ and the parts by $kn$ — so the ratio is about $n^{k-1}/k$, which is exponential in the number of components. The measured ratios are smaller than that bound because many tuples are unreachable, and they grow the same way.

That is the shape of the saving and it is why it matters. A fixed factor would be an optimisation; a factor that grows with every component is the difference between solving a board and not.

It is worth noticing what the product search is doing that the parts are not. A tuple state records which position each component is in, and the vast majority of those combinations never arise in any single line of play — they are reachable only because the players may interleave their moves between components in any order. The product is therefore mostly bookkeeping about interleavings, and the licence’s whole content is that the interleavings do not matter: each component’s contribution is a number, and numbers combine without regard to order.

That is the disjunctive sum theorem doing the work, and the ratios above are what it is worth in positions rather than in prose.

Why only the nimbers can collect it #

The licence has two halves and a solver needs both.

Rewriting a component of a sum needs the company closed under addition, so that a substitution made inside one component is still legitimate when the rest of the board is added back.

Rewriting a subposition needs the company closed under taking options, so that the substitution can be made again one move down, and again below that. Without it a solver may simplify the board it holds and not the boards it reaches.

The distinction is not academic: a solver that could only rewrite at the top level would have to run its search on unsimplified boards one move down, which is where the states are. Three of the seven finite companies lose an option and have no licence for the second; the four that keep every option are precisely the groups of nimbers. So a full recursive substitution is available for impartial games and for nothing else — which is Sprague–Grundy stated in the vocabulary of companies rather than of theorems.

The representative has to be smaller #

There is a step in the argument that is easy to skip and is the whole reason the saving is large.

A substitution replaces a position by another member of its class. It saves a search only when the replacement is smaller than what it replaces, and for an impartial component it is dramatically smaller: a nine-square Cram board with 98 positions becomes a Nim heap with one. The board leaves the search entirely.

A partizan component’s class representative is its canonical form, and a canonical form is not a position of Domineering. Substituting it rewrites the form — which is worth doing, and is what the reduced canonical form does more of — but the board is still on the table and the search over its positions is still there to be run.

So the nimber groups are not merely the companies with both closures; they are the companies whose members are positions of the games they describe. That coincidence is what turns a licence into a saving, and it is why the impartial theory is computationally a different animal from the partizan one rather than a special case of it.

What the numbers do not include #

The comparison above is generous to the product search in one way and harsh in another, and both are worth stating.

Generous: the product search here is memoised on the tuple, so it never revisits a state. An unmemoised search would be far worse, and the ratios would be meaningless rather than merely large. This is the tree and the graph’s saving already applied to both sides.

Harsh: the parts’ side counts every position of each component, which is what computing a Grundy value from scratch costs. A solver with a catalogue of small components pays nothing at all, and the ratio then becomes infinite — which is the situation any real impartial solver is in, since the Grundy values of small heaps are tabulated once and used for ever.

There is a third asymmetry worth naming. The product search answers only who wins this board; the parts’ searches answer what each component is worth, which is reusable in every board those components ever appear in. So the licence buys a better answer as well as a cheaper one, and the comparison above understates it again.

So the honest reading of 161 is this is what the licence saves a solver computing everything from scratch, and the practical saving is larger.

What a licence is, as a piece of bookkeeping #

It is worth being concrete about what “rewriting a subposition” means to a program, because the phrase sounds abstract and the operation is not.

A solver evaluating a board holds a data structure: a list of components, each a position of some game. Substituting means replacing one of those entries by something else with the same behaviour. For an impartial component the something else is an integer — the Grundy value — and the entry stops being a board at all.

Once every entry is an integer the board is an integer, and the solver has stopped searching. That is why the impartial saving is not a constant factor: the search does not get smaller, it ends.

For a partizan component the something else is a canonical form, which is a tree. The board is then a list of trees, and evaluating it means adding trees — cheaper than searching boards, and not free, and not the end of anything.

What it means for a partizan solver #

Three consequences, and the third is the one that explains a practice.

A partizan board cannot be collapsed to a number. There is no company in which a Domineering region is equal to a smaller Domineering region, except by accident, so the analogous shortcut does not exist. What exists instead is the value: not a smaller position but a smaller description, which composes by addition and is the reason values are computed at all.

The saving is bought in a different currency. Adding two canonical forms is cheaper than searching the product of two boards, so a partizan solver still avoids the product — it just pays for the forms first, which pricing the two questions measures.

And that is why impartial games are solved to sizes partizan games are not. Kayles is tabulated into the thousands of counters and Domineering is not solved past a handful of squares; the gap is usually explained by saying impartial games are simpler, and the sharper statement is that one theory’s class representatives are positions of the game and the other’s are not. A Kayles heap of two hundred is a number in a table; a Domineering board of two hundred squares is a board.

Who noticed the coincidence #

Sprague and Grundy’s theorem is usually stated as every impartial position is equivalent to a Nim heap, and the emphasis falls on equivalent. The computational content is in the other word: a heap, which is the smallest position anybody could name.

The restricted-universe reading makes that visible. Take the theorem as a statement about companies — the nimbers form a company closed under addition and under options, and every impartial position is equal to one of its members in that company — and the shortcut it licenses is a rewriting. That the rewriting also shrinks the board is a separate fact, and it is the one every impartial solver lives on.

The misère side is where the two come apart, and this site has the contrast to hand: misère quotients compute a company for one game, its members are equivalence classes rather than heaps, and a solver working in one gets the licence without the shrinking. That is a good deal less useful, and it is why misère solving is hard in a way normal play is not.

The cost of asking #

The measurement is a hundred lines and two seconds, and the reason it had not been made is worth a sentence: it needs a solver that refuses to use the theorem.

Every impartial solver anybody writes computes Grundy values, because that is what the theory says to do — so the expensive side of this comparison is a program nobody would otherwise write. Building it is the whole of the work here, and it is the only way to price a theorem: run the thing the theorem replaces.

That is a general habit worth naming. A shortcut’s value cannot be read off the shortcut; it is the difference between two programs, one of which is deliberately naive. This site has now done it twice — once for the transposition table and once here — and both times the naive program was a dozen lines and the number it produced was the point.

Why the saving is exponential and the licence is a constant #

The numbers here are large and it is worth separating the two quantities they are made of, because only one of them grows.

The licence is a constant. Every position of this game may be replaced by its class representative is one sentence, checked once, true for every position of every size. It costs nothing to hold and nothing to apply.

What it buys grows with the board. A solver without the licence walks a state space that is the product of the components’ position sets; with it, the components collapse to representatives and the walk is over their sum. The gap between a product and a sum of the same factors is the whole of the saving, and it is exponential in the number of components by construction.

That asymmetry is why a restricted universe is worth the trouble of establishing. The establishing is a finite piece of work — find the company, check the closure, verify the classes — and the return is unbounded in the size of the boards it is applied to. Nothing else on this site has that shape: a table’s saving grows and has to be paid for as it grows; decomposition’s saving grows and costs a flood fill at every node; a substitution licence is paid for once.

It also says where the licence is worth nothing, which is on a board with one component. There is no product to collapse, so a class representative replaces one position with another and the walk is the same length. The licence is worth exactly the decomposition it can be applied across, which is why this ladder measures it on sums and why a game that never falls apart gets nothing from it.

What this does not say #

Four limits.

Cram, and small boards. The largest product measured is 21,535 states, because the product search has to finish for the comparison to exist. The ratio grows with size, so these are lower bounds on what the licence is worth at any size worth solving.

One game on the impartial side. Cram is the only game measured, chosen because its positions are a bitmask and its components are boards. Nothing about the argument is specific to it, and nothing here checks that.

Positions, not seconds. Both sides are counted in positions expanded, which is the currency this site prices searches in. A Grundy value costs a little more per position than an outcome does, so the ratios overstate the wall-clock saving slightly.

Four companies, seven candidates. The closure result is the rung below’s and is measured over the finite companies it could enumerate. Only the nimber groups is a statement about those, and it agrees with what the theory says about all of them.

And the licence is not needed to add values. Nothing here says a solver without both closures is helpless: it says the recursive substitution is unavailable. Adding values of components is licensed by ordinary equality and is what every partizan solver does.

The convention, named #

Normal play. A company is a set of games, and two positions are equal in it when adding any member leaves their outcomes the same.

Closed under addition means the sum of two members is a member; closed under options means every option of a member is a member. A solver rewriting a component needs the first and one rewriting a subposition needs both.

The product search treats a board of components as one game whose state is the tuple of the components’ positions, memoised on the tuple. The parts’ count is the number of distinct positions each component has, summed — what it costs to evaluate each alone.

Cram is impartial: both players place dominoes in either orientation, so a position’s value is a nimber and the sum’s is the exclusive-or.

One line is worth keeping from all of this. A substitution is worth what the substitute saves, and the nimber groups are the only companies whose members are positions of the games they describe — which is why Sprague–Grundy ends a search and the partizan theory only shortens one.

Where the ladder goes next #

The universes anchor has four rungs to here, and the two above split the licence this page prices into its two halves and find them behaving completely differently.

Half a licence is nearly all of it separates the right to rewrite a component from the right to rewrite a subposition, and the first does almost everything. Rewriting components takes a million and a half states to three thousand six hundred; rewriting subpositions takes those three thousand six hundred to eight hundred and eighty-four; splitting the pieces takes it to fourteen. So the expensive licence — the one that needs closure under forming options and picks out the nimbers — is the one contributing least.

One half multiplies the other adds then gives both halves closed forms, and the forms explain the split rather than merely recording it. The component licence saves $s^{k-1}/k$ and the subposition licence saves $k \cdot s$, over a shape count that does not move. One is exponential in the number of components and the other is linear in it, so the gap widens with every extra piece on the board — which is exactly the situation a restricted universe is invoked for.

That is the reading to carry away from this anchor. A licence to substitute is not one privilege with one price: it is two, they compose, and the cheap half is worth more than the dear one on any board that has broken into several pieces.