Two measures bounded, and one not

The birthday of a sum established that a sum is born no later than its two parts’ birthdays together, measured it over every pair of day-two values, and named the measurement it had not made:

The rung above is the third measurement that essay named and this one has not made: birthdays under a bounded pool. Every count here is over forms whose options come from a fixed day. Bounding instead the number of options, or the size of the written form, gives a different census and a different diagonal — and it is the version that would say something about positions a player might actually meet.

There are three ways to ask how big a value is. The sum bounds two of them.

The birthday is subadditive, which is the rung below’s theorem. The number of options is too, on every pair, and nobody had checked. The length of the written form is not.

The bound that was there #

That a sum has no more options than its parts have between them is not obvious and it is not quite trivial either.

The unreduced sum has exactly that many: Left’s moves in a sum are Left’s moves in the first part and Left’s moves in the second, and nothing else. So before any reduction the count is exactly additive. What is not obvious is that the reduction cannot make it worse — and how wide a form can get is where this site established that it can, because bypassing a reversible option replaces it with the answer’s own options and can leave a form wider than it started.

So the width bound could have failed and it does not, on all 231 pairs.

And it is attained, on seven pairs. Three are nimbers: $\ast + \ast 2 = \ast 3$, where six options go in and six come out. Four are hot games where all four options survive. So the bound is tight and the reduction genuinely cannot do better in general.

Seven of 231 is a thin diagonal and that is worth comparing with the birthday’s. The birthday bound is attained on 163 of the 231 — nearly three quarters — so a sum is usually born exactly as late as it is allowed to be, and it usually has far fewer options than it is allowed to have. The two bounds are the same shape and describe quite different situations: the birthday bound is a near-equality with occasional slack, and the width bound is a genuine ceiling that almost nothing reaches.

That difference is the reduction working. The unreduced sum always attains the width bound exactly; every pair below it is a pair where domination deleted something. So the width column is a measurement of how much the reduction removes, and the answer is that it removes something on 224 of 231 sums.

And that the birthday bound holds is a different kind of fact, worth separating because the two proofs would look nothing alike. A sum’s birthday being at most the parts’ together is a statement about the construction: a value born on day $m$ has all its options born earlier, so a sum’s options are sums of things born earlier, and an induction runs. A sum’s option count being at most the parts’ together is a statement about the reduction: the count is exactly additive before reducing, and the claim is that reducing never adds. The first is about how values are built and the second about how forms are shrunk, and only the second could have gone the other way.

That is why the width bound is the interesting one of the two even though the birthday bound is the celebrated one. Nobody would expect a sum to be born late. Plenty of things in this subject get wider when they are reduced, and canonical form is where both reductions are set out, with the widening one drawn.

The measure that runs away #

Twenty-seven pairs of 231 give a sum that takes longer to write than its two parts together, and the worst takes nearly three times as long. $\{0 \mid -1\}$ plus $\{\ast \mid -1\}$ is sixteen characters in and forty-five out.

The parts are not large. Two options each, one move deep, the smallest hot games there are.

Measured by option count, nothing unusual happened at all: four options went in and four came out, exactly the bound. Measured by written length, the form nearly tripled. Both are true of the same sum.

That coincidence is not a coincidence, and the sweep makes it exact: every one of the seven pairs attaining the width bound breaks the written bound, and the four largest written excesses are all among them. A pair whose sum loses options to domination loses written length with them; the sums that stay longest are the ones the reduction cannot touch, and those are precisely the ones at the width ceiling.

So the two anomalies coincide rather than trading off. A reader scanning the two columns would expect the sums that grew most in length to be the ones that grew most in options, and there are none of those — the option count never grows. What there are instead are sums where the reduction removed nothing, and those are where the length runs away.

Why the count is bounded and the length is not #

The two facts have one explanation, and it is the sentence the whole anchor turns on.

An option of a sum is a sum. When Left moves in the first part, what remains is the rest of the first part plus the whole of the second — the second part has not been touched and is still there in full.

So the number of options adds, because it counts moves and the moves are the two parts’ moves. And the content of each option does not, because every option contains both parts written out, before the sum has any structure of its own.

That is why a form can have exactly the number of options its parts entitle it to and still be enormously longer. The width is a count of branches and the written length is a count of what is under them.

What this changes about the pool #

The rung below bounded its pool by day and asked what the sum did. Bounding by size instead gives three different pools and the three behave differently.

A pool bounded by day is a pool of values with a common depth: at day three, 1,452 of the 1,474 values are born on exactly that day, and their option counts run from nought to seven. A pool bounded by option count cuts across days — a value with two options may be born on day two or day ten. And a pool bounded by written length is a pool of values a program can afford to store.

The three are different questions and only the third is the one a solver asks. What a value costs to write down is where that measure was established as the one that matters and where the birthday was found not to bound it; this page is the same finding arriving through the sum rather than through the notation.

So a solver adding two values can promise itself two things and not the third. It knows how deep the recursion can go, because the birthday is bounded. It knows how many branches to expect, because the option count is bounded. It cannot bound what the answer will cost to store, and the sum is exactly where that goes wrong.

That is a fair description of what makes exact evaluation hard in this subject, and it is more precise than game trees explode. The tree does not explode: its depth and its branching are both controlled by the parts. What explodes is the written form of the answer.

What a bounded pool would look like #

The rung below’s phrase was birthdays under a bounded pool, and it is worth saying what the three pools actually contain, because the sizes are not alike.

Bounded by day, at day three, the pool is 1,474 values — and 1,452 of them are born on exactly that day. So a day-bounded pool is almost entirely one day’s worth, and the pool grows by roughly a factor of sixty-seven per day. It is the pool this anchor has always used and it is the one that runs out of memory first.

Bounded by option count, the same 1,474 values spread across widths nought to seven, with the mass at three, four and five: 400, 527 and 304. A width-bounded pool cuts across days and is far more evenly filled, which is what makes it a usable axis — a pool of values with at most four options is a substantial and well-spread population rather than a truncated day.

Bounded by written length, the same values run from five characters to over forty-eight, with the mass between thirteen and forty-eight. That is the pool a program can afford, and it is the one whose behaviour under the sum is unbounded.

So the three bounds cut the same collection three ways, and the rung below’s suggestion that they would give different censuses is right. What it did not anticipate is that they would also give different theorems: two of the three axes are respected by the sum and the third is not, and the third is the one the phrase a bounded pool was reaching for.

Why this is the honest form of “game trees explode” #

The phrase every account of this subject reaches for is that game trees explode, and the three measures say it is not quite what happens.

The depth does not explode. A sum of two day-two values is born by day four, and the bound is attained on 163 of the 231 pairs — so the depth grows, it grows exactly as fast as the parts allow, and a solver can plan for it. How old a value is is where the birthday was established as a measure and shown not to bound the width; here it is shown to bound the depth of what a sum can produce, which is the thing it is actually good for.

The branching does not explode. Six options in, six out, at the worst. A search over a sum has exactly the branching factor its parts have between them and never more.

The stored answer explodes, and it does so on the smallest examples available — two-option, one-move-deep hot games. That is a fact about writing a value down rather than about searching it, and it is why the recursion this site cannot run prices the evaluation in table entries rather than in nodes.

So the difficulty is not that the search is large. It is that the answers are, and that the answer to a sum contains both its parts in every branch. A solver that keeps only outcomes gets away with it; one that keeps values does not, and this anchor exists because the second is what a theory of games needs.

What the solver computed, and how #

Every unordered pair of the 22 values born by day two, less the pairs involving nought — 231 pairs. The pool is the rung below’s, so the birthday column reproduces its measurement exactly and the two pages are about one population.

Each pair is added and the sum reduced to canonical form. Three measures are then taken of each of the three games — the two parts and the sum. The birthday is the depth of the canonical form, which for a canonical form is the value’s birthday. The option count is the number of Left options plus the number of Right options. The written length is the number of characters in the full brace expression, written out rather than abbreviated, so that $\ast 3$ counts as the form it is rather than as two characters.

Each measure is then tested for subadditivity: is the sum’s value at most the two parts’ added? The pairs attaining equality are recorded separately, because a bound never attained is a statement about the reduction rather than about the sum.

Two things are asserted rather than reported. Exactly two of the three measures must be subadditive, since the page is written about that contrast. And the worst written-size failure must be a pair on which the width bound is attained, because that coincidence is the mechanism the page offers — a failure on a pair whose option count also grew would show nothing.

Where the model stops #

Day two, 231 pairs. Small, and deliberately the rung below’s population so the two measurements are comparable. The width bound holding on all 231 is a sweep rather than a proof, and a proof looks available — the unreduced sum has exactly the additive count and the question is only whether bypassing can widen a sum — but nothing here is it.

And the written length depends on the notation. Counting characters of a brace expression is one choice among several; counting nodes of the game tree is another, and counting distinct subpositions after sharing is a third and is what a real program stores. The same position, written once measures that third quantity, and the fact that the shared form is much smaller is exactly why a character count overstates the problem. What survives the change of measure is the direction: no notation makes the sum’s storage a function of its parts’, because the parts both appear inside every option.

Nought is excluded, as it was on the rung below, because adding nought changes nothing and every measure is trivially attained.

Normal play throughout, and the birthday is a normal-play notion: it counts days of the construction that this convention makes well-founded.

And the figures cannot show the growth. Six tables of counts describe a form nearly tripling in length, and the object — the forty-five-character sum written out beside its two eight-character parts — is a line of text rather than a picture. It is in the second figure’s first column and a reader can count it, which is as close as a table gets.

Where the ladder goes next #

The numbers anchor has eight rungs: the simplicity rule, the number tree, numbers avoiding numbers, where the numbers came from, how old a value is, what a recursion costs, the birthday of a sum, and now the two measures the sum bounds.

The rung above is the width bound’s proof, and it is the best-posed thing here. A sum has no more options than its parts have between them has 231 confirmations, is attained on seven of them, and has an argument nearly written: the unreduced sum has exactly the additive count, domination only removes, and the whole question is whether bypassing a reversible option of a sum can leave it wider. Since the answer a bypass inserts is the options of a Right option of an option of the sum, and every game in that chain is itself a sum of the two parts’ followers, there is a structural reason to expect it cannot — and this site has a counterexample-hunting apparatus that has never been pointed at it.

Two neighbours are worth the trip. How wide a form can get is where bypassing was shown to widen a form, and it is the reason the width bound is a finding rather than an assumption. And what a value costs to write down is where the written length was established as the measure that matters and the birthday found not to bound it, which is this page’s result reached from the other direction.