A factor, and not an overhead

Two hundred and fifty-six ways to write twenty-two things built every form out of the day-one games, found 22 values among the 256 forms, and showed the two reductions reaching the same answer whatever order they run in. It closed by naming the question its own last section had dodged:

What does the canonical form cost to compute? Both reductions call comparison, comparison is subtraction followed by a search, and the search is over the sum of two game trees.

Over the same 256 forms the reduction expands 5.46 times as many positions as deciding the outcome does — and the factor is not a factor. It runs from 0.58 to 9.80 across the census.

Two costs in one unit #

The comparison is only worth making if both costs are counted the same way, so both are counted as positions expanded.

Deciding who wins a form expands the positions of that form’s own tree — 1,135 across the census. Reducing expands 6,194, and they are positions of quite different games.

The 1,135 is worth pausing on, because it is small. Two hundred and fifty-six forms share 1,135 distinct positions between them, which is fewer than five apiece — the forms are built from four fixed games, so their trees overlap almost entirely, and a solver deciding all 256 outcomes with one memo would expand far fewer than 1,135. The comparison here does not give it that memo, because the point is to price one form’s two questions against each other rather than to price a batch.

The 1,490 distinct difference games is the number that says why the reduction is different. Those are 1,490 objects that do not appear anywhere in any form’s tree — they are sums, built for the purpose, searched once and discarded. A program computing outcomes never constructs any of them.

What a comparison searches #

Asking whether Left’s option $A$ is dominated by $B$ is asking whether $B \geq A$, which is asking whether Left, moving second, wins $B - A$. That difference is a sum — the sum is the object is where this site establishes what a sum is — and its tree is built from both trees rather than from either.

So the reduction is not a heavier pass over the same object. It is a search over a different and larger object, repeated once per comparison. Comparison is a search is where that was established for a single comparison; this page is the same fact multiplied by how many a reduction makes.

And it makes a great many. Domination compares every ordered pair of options on a side, which is quadratic in the width; reversibility compares every answer of every option against the whole position. Over the census that is 1,920 comparisons for 256 forms.

And the difference is larger than either part. That is the point a reader should hold on to, because it is easy to imagine a difference game as a small object — after all, $B - A$ is a subtraction, and subtraction usually makes things smaller. It does not here. $B - A$ is $B + (-A)$, a position with both games standing side by side, and a move in it is a move in either. Its tree carries the pairs of positions the two trees reach, not the positions of one.

So a comparison between two options of a form is a search over an object built from two of the form’s subpositions — and there are quadratically many such pairs. The reduction’s expense is not one large search but a great many searches over objects that are individually larger than the thing being reduced.

Why the width is the variable #

The ratio rising from 0.58 to 9.80 is the finding, and the reason is in the counting above.

At one option there is no ordered pair to compare, so domination costs nothing and only reversibility can fire; reducing is cheaper than deciding, at 0.58. At eight options — four a side — domination alone makes twenty-four comparisons, each a search over a sum, and reducing costs 9.80 times what deciding does.

So the cost is quadratic in the width where the outcome’s cost is not. Deciding an outcome visits each position of the tree once, however wide the form is; the number of comparisons grows as the square of the option count, and each comparison’s own search grows with the depth. Neither growth is present in the outcome question.

Twelve of the 256 forms need no comparison at all. They are the forms with at most one option a side and no answer worth reversing through — nothing to compare, so nothing to search. Deciding them still costs whatever their trees cost, so on those twelve the ratio is nought and the reduction is genuinely free rather than merely cheap.

Those twelve are also the only forms in the census on which a program could safely skip the reduction without checking, and it could tell by counting options rather than by comparing anything. That is the one cheap test available, it applies to a twentieth of the census, and everything above one option a side has to be searched.

It is worth being clear that the twelve free forms and the 0.58 ratio at width one are not a loophole. They are the bottom of the curve, and the curve is what the page is about.

A form with one option a side is a form with nothing to reduce, and the reduction correctly notices that after almost no work. That is the reduction behaving well; it is not evidence that reducing is ever cheap in general, because a form with one option a side is a form nobody needed reduced. The interesting forms are the wide ones, and those are the ones where the ratio is worst.

The distribution of widths across the census makes that concrete. Of the 256 forms, 70 have four options and only 8 have one; the mass of the census is in the middle, at three, four and five options, where the ratio runs 3.51, 5.34 and 7.06. So the overall 5.46 is not an average dragged up by a rare bad case — it is roughly what the typical form costs.

The dearest form, and what it buys #

Nine forms in ten therefore pay something, and most pay a multiple. The dearest form in the census expands five positions to decide and forty-nine to reduce — and it is already in canonical form. The reduction’s entire expense buys the answer no step applies.

That is not a curiosity, it is the ordinary case. A reduction cannot know that nothing applies without checking that nothing applies, and checking is exactly the comparisons. So a form that needs no work still pays for the search that establishes it, and a program cannot skip the cost by noticing the form is already reduced — noticing is the cost.

That asymmetry is worth setting beside the outcome question, where nothing like it happens. A search for the outcome does work proportional to what there is to find: a position with few moves is decided quickly because there is little to look at. A reduction does work proportional to what there might have been — every pair of options has to be ruled out, and ruling out is as expensive as ruling in. So the two costs respond to a form differently, and the reduction’s is the one that does not fall when the answer is simple.

What this settles #

The rung below’s sentence — the complexity of that is not the complexity of deciding who wins, and the difference between the two is a rung of its own — is now measured rather than asserted, and it is the stronger of the two readings available.

A fixed overhead would have been the weaker one. If reducing cost some constant multiple of deciding, the two problems would be the same problem with a worse constant, and a solver could budget for canonical forms by budgeting for outcomes. It cannot: the multiple depends on the form, and it depends on it in a way that grows.

And the two questions are over different objects. That is the honest statement of the difference. Deciding an outcome searches the position; reducing it searches sums of pairs of its options. How hard is it prices the first for the family of games this site works on, and nothing there transfers to the second, because the second is not a question about the position at all.

What a solver should take from this #

Three consequences, and they point the same way.

Canonical forms are for storing, not for computing with. A solver that reduces every position it meets pays a growing multiple of what it would pay to decide them, and buys a form it can compare cheaply later. That trade is worth making when the form will be looked up many times — which is exactly the catalogue case when the catalogue starts paying prices — and not worth making once.

And the reduction cannot be short-circuited by noticing it is unnecessary. The dearest form in the census is already canonical, and there is no cheaper test for already canonical than running the comparisons. So a program cannot filter for forms worth reducing; it can only decide, per position, whether the form will be reused.

The width is the thing to watch, and it is under a solver’s control. A position’s option list is what the ruleset gives, but a solver that has already discarded plainly bad moves is a solver reducing a narrower form — and the saving is quadratic rather than linear. That is an unusual shape of saving and it argues for cheap heuristics before the reduction rather than after: the margin a count needs is where such a heuristic is priced on this site, and its output is exactly a shorter option list.

Why this is a different question from the outcome’s #

The rung below’s sentence said the two complexities are different, and it is worth saying exactly how, because different could mean several things.

It is not that one is harder in the usual sense. Both are decided by search over finite trees, both are settled by the same recursion, and neither is a different complexity class from the other on the strength of anything here. This page measures work on small forms, not asymptotics.

It is that they are questions about different objects. Deciding an outcome is a question about a position: it asks what happens when the game is played. Reducing is a question about a form and its relationship to other forms — whether one of its options could stand in for another, which is a claim about every sum they could both appear in. Equal in every company is where that quantifier is established, and it is the reason a comparison cannot be answered by looking at the two options alone.

So the cost is the quantifier’s. The reduction is expensive because each of its steps asks a universally quantified question, and this subject answers such questions by playing a difference game. A cheaper reduction would need a cheaper way to answer is this option ever worth taking — and there is not one, which is what knowing who wins and knowing what it is worth measures from the other side.

What the solver computed, and how #

Every form built from the four day-one games as options — 256 of them, being every pair of subsets, which is the rung below’s census exactly.

For each form two quantities are taken. Deciding is the number of distinct positions reachable from the form, counted by walking its option tree with a set of keys, which is what a memoised outcome computation expands and no more. Reducing is the number of distinct positions across every difference game the reduction searches: for each comparison the difference is formed, and if it has not been seen for this form its whole tree is counted.

The comparisons counted are the ones the reduction makes: every ordered pair of options on each side for domination, and every answer of every option against the whole position for reversibility. Differences repeated within one form are counted once, which is generous to the reduction — a real implementation memoises across forms too and would do better still.

Two things are asserted rather than reported. Reducing must cost more than deciding over the census, since the page is written about it being dearer. And the ratio must be larger at the widest forms than at the narrowest, since a fixed overhead would make the central claim false and three of these figures wrong.

Where the model stops #

Forms of depth two. Every form here has day-one games as options, so its tree is at most three deep and every difference game is small. The ratio is what this page reports and the ratio is what depth would move: a deeper form has deeper options, so each comparison’s search grows while the number of comparisons stays quadratic in the width. So 5.46 is a figure for this census and the direction is that deeper forms are worse.

And the counting is generous to the reduction in two ways. Differences repeated within a form are counted once, and the memo that real implementations keep across the whole run is not modelled at all — a position reached eleven ways is one position measures what that saving is worth on a search, and it would be worth something here. So the true ratio for a program that caches well is lower than 5.46 and the growth with width is unaffected, since caching does not reduce how many distinct pairs must be compared.

The unit is a position expanded, which weighs a comparison’s search and an outcome’s search the same. That is the right unit for comparing two searches and it is not a wall-clock measurement; nothing here is timed.

Normal play throughout, and both reductions are normal-play reductions — they preserve the value under the disjunctive sum, which is what makes the canonical form well defined at all.

And the figures cannot show a difference game. Six tables of counts describe searches over sums, and the object — a form’s two options side by side with their difference drawn beneath — is a picture of three game trees. Canonical form draws one reduction on one position, and what this page would want is the search that reduction had to run to know it applied.

Where the ladder goes next #

The canonical-form anchor has three rungs: the two reductions on one position, what they do to a whole population of forms, and now what they cost.

The rung above is the depth. This census holds forms two deep and the ratio is 5.46; the same measurement on forms built from day-two games gives forms three deep, with the same quadratic count of comparisons over larger difference games, and it would say whether the ratio grows with depth as well as with width. The prediction is that it does and that the two growths multiply — a form four options wide and three deep should be far worse than either alone suggests — and the census is one line of code away, since the only change is which pool the subsets are taken from.

Two neighbours are worth the trip. Comparison is a search is where a single comparison was priced, and this page is that price multiplied by how many a reduction makes. And how wide a form can get is where bypassing was shown to widen a form, which is the one way the reduction can make its own remaining work harder — a reduction that widens a form has given itself more ordered pairs to compare.