How wide a form can get

The canonical form is the unique smallest form of its value, so the number of options it carries is not a fact about a drawing. It is the fewest options any way of writing the value can have — the minimum cost, in moves listed, of writing the position down at all.

Call that number the width: Left’s options and Right’s together.

Day one has four values with widths nought, one, one and two. Day two has twenty-two, the widest of them $\ast 2$ at four. Day three has 1,474, the widest at seven — and there are exactly two of those.

The question this rung is here for #

The reduction that puts options back established that one of the two reductions is not a contraction. Deleting a dominated option removes one option and can do nothing else. Bypassing a reversible one does something entirely different: it removes the option and puts in its place the whole Left option list of the position the move reverses through, which may have any number of members.

So a form can be wider after a step of its own reduction than it was before. That essay measured the growth step by step and closed on the question it could not reach: is the canonical form’s width bounded by anything at all in terms of the form it came from?

It is a real question. A reduction that shrinks is a reduction a reader can reason about; a reduction that can inflate is one where the intermediate object might be enormous even though the answer is small, which is exactly the situation that makes an algorithm unusable.

The sweep #

Every form whose Left options are up to two of the twenty-two day-two values and whose Right options are likewise: 64,515 forms in all. For each, the starting width against the width of its canonical form.

Sixty-three thousand four hundred and three forms come out narrower. One thousand one hundred and twelve come out the same width. None comes out wider.

That is a stronger answer than the question asked for. It does not say the growth is small; it says the growth never survives to the end. A bypass widens a form and then, without exception here, the widened form loses at least as many options again before it settles.

Why the growth is real anyway #

It would be easy to read the last section as saying the growth never happens, and that would be the wrong lesson entirely. It happens constantly. The census in the rung below counts the bypasses and finds a substantial fraction of them enlarging the form by one, two or more options at the moment they fire.

What the sweep adds is that the peak is not the answer. The reduction runs to a fixed point, and the fixed point is reached after the arriving options have themselves been compared with what was already there — at which point most of them are dominated by it, because they came from a position that was, by the definition of reversibility, no better for the player who was going to move there.

That is the mechanism, and it is a suggestive argument rather than a proof. What the census establishes is that on every one of 64,515 forms the mechanism finishes the job.

The widest value born by day three #

Two of the 1,474 values reach width seven. Here is one:

$$\{1,\; \{1 \mid 0\},\; \{1 \mid \ast\} \;\mid\; 0,\; \{1 \mid -1\},\; \ast,\; \ast 2\}$$

Three Left options, four Right options, and no two of either list comparable — every one of the seven is a move that cannot be ruled out by comparing it with a sibling. It is the exact opposite of the situation an option list that is a chain produces, where deleting alone reduces the list to a single option.

A reader who has met canonical forms as the tidy way to write a game should sit with that expression for a moment. It is the tidiest way to write that value. There is no shorter one.

Width against birthday #

Birthday and width are two measures of how complicated a value is — one counts days of construction, the other counts options — and the obvious guess is that the first bounds the second.

It does, and the census says so twice over: the widest value of a day never gets narrower as the days go on, and the day-three values run out at seven.

But the bound is enormously loose in the direction that matters. Within birthday three, the mean width is 3.82 and the maximum is seven, and the minimum is one — so the values born on a single day span almost the whole range the day offers, and knowing a value’s birthday tells a reader almost nothing about how many options it needs. And the two widest values of the day are not among the ones born last in any meaningful sense; they are ordinary members of a day whose other 1,450 members are narrower.

The numbers make the divergence stark. A number’s canonical form is $\{x' \mid x''\}$ with one option each way, so every number has width at most two, whatever its birthday. The value $\tfrac{1}{1024}$ is born on day eleven and is written with two options. Width measures something the birthday does not.

What width is measuring #

It is measuring incomparability, and the connection is exact.

A form of width nought is the empty game, and there is exactly one of those. A form of width one has a move for one player and none for the other, so it is an integer of absolute value one or something built to look like one. Everything above that is a statement about how many mutually incomparable options a player holds.

A canonical form’s Left options are pairwise incomparable — that is what surviving domination means — so the width of a form is the size of two antichains in the order of games. A wide form is one whose value has many genuinely different best moves for a player, none of which can be preferred to another without knowing what else is on the board.

It also explains why width cannot be read off the value’s name. Comparing two positions means playing a third, so whether two of a form’s options are comparable is a search, and nothing in the printed expression announces the answer. The two width-seven values look, at a glance, no more complicated than several width-four ones.

That reading explains the shape of the distribution. Numbers are narrow because a number’s options are ordered by the number line. Nimbers are wide for their birthday because everything confused with everything is what a nimber’s option list is. And the general case sits between, at a mean of 3.79 on day three.

Reading the table the other way #

The sweep is really a table of starting width against final width, and its shape says more than the three totals do.

Of the 64,515 forms, 32,019 start at four and end at two. That single cell is half the sweep. Another 11,025 start at four and end at nought — the value is zero, and the form saying so had four options.

Width two is where forms go. It is the width of every number, of every switch, and of the overwhelming majority of everything else, and the reason is that two is the smallest width a form can have without being a number or being empty. A form arriving at width two has usually lost two options on the way, and the count of forms ending wider than two falls off a cliff: 7,308 at three and 459 at four.

Those 459 are the whole of the top row, and every one of them is a form the reduction cannot touch at all — both option lists already antichains, no reversible option anywhere. Four hundred and fifty-nine out of sixty-four thousand.

The other diagonal cells are worth a sentence each, because together they are the 1,112 that hold their width and the essay has so far reported them only as a total. Fourteen forms start at width one and stay there, 199 start at two and stay, 440 start at three and stay. The counts rise and the shares fall, which is the only place a table of raw counts and a table of proportions point in opposite directions on this page.

Two ways to be wide, and only one of them is common #

The distribution of widths across day three has a definite shape: one value at nought, six at one, 167 at two, 400 at three, 527 at four, 304 at five, 67 at six and two at seven. It peaks at four and falls off symmetrically enough to look almost like a bell.

There are two quite different ways for a value to sit in the right-hand tail.

The first is to be nimber-like: a value confused with a great many things, whose option list is wide because nothing in it can be preferred to anything else. $\ast 2$ is the day-two example, with two options a side and every one of them incomparable with its siblings.

The second is to be a fight with several distinct follow-ups: a hot position in which Left has genuinely different ways of pressing and Right genuinely different ways of answering, and the choice between them depends on what else is on the board. The width-seven value above is of that kind — its Left options include an integer, a switch and a fight with a star in it, and no two of them can be ordered.

The second is much the commoner. Nimbers are rare because there are few of them; hot positions with several follow-ups are what a day of construction mostly produces once there is a previous day to build from.

Which is what makes the distribution single-peaked rather than two-humped, and the single peak is a claim rather than an impression. Two mechanisms producing width, one of them rare and one of them ordinary, could easily have left a small bump out in the tail where the nimber-like values sit; instead the counts fall away smoothly from four to seven — 527, 304, 67, 2 — with nothing that looks like a second population. So the nimber-like values are not a separate family in the width statistics. They are the far end of one family, and the value at the very end of it is not a nimber at all.

The mean, and what it is doing #

Day one has mean width one, day two has two, and day three has 3.79. The differences are one and 1.79, which is a slower climb than the value counts — four, twenty-two, 1,474 — by an enormous margin.

Restricting to the values actually born on each day rather than inherited from the previous one sharpens it: birthday two has mean width 2.22 over its eighteen values, and birthday three has 3.82 over its 1,452. So the values arriving on a day are wider than the values already present, and the gap between the two means is about a option and a half.

If that pattern continued, day four would have a mean somewhere near five and a half and a maximum in the low teens. Whether it does is a question one more day of enumeration would settle, and one more day of enumeration is not affordable here — day three already needs the 1,474 values to be built out of every subset of the twenty-two, and day four asks the same of 1,474.

The cost this puts on writing a value down #

There is a practical consequence and it is the reason the width was worth counting.

An essay, a program or a textbook that writes out a canonical form pays for its options. A form of width seven, each of whose options is itself a form of some width, is a nested expression running to dozens of symbols — and the notation is compact and completely opaque at that size, which is why this site’s rule is to draw the position beside the braces rather than trusting the braces alone.

The mean width of 3.79 on day three is therefore a mean branching factor for that nesting. Three days out, an expression is around four options wide at each of three levels, which is where the size of a printed canonical form comes from, and it is why the two widest values of the day take a full line each.

The width also bounds something a solver cares about: the number of comparisons the last round of the reduction has to make. A form of width $w$ needs $w(w-1)$ comparisons to confirm that nothing dominates anything, and each comparison is a search. That is the floor on the cost of checking a canonical form, quite apart from finding it.

What the sweep cannot say #

The pool is forms built from at most two day-two options a side, which caps the starting width at four and the answer at four. A form built from day-three options can be wider, its bypasses can bring in wider option lists, and nothing here rules out a case where the widening survives.

Saying so is not a formality. The reversal census in the rung below found that the growth is invisible one day earlier — every bypass among the 256 day-two forms shrinks the form by exactly one, because no answer on that day has two Left options to donate — so this exact phenomenon has already appeared and disappeared once as the pool grew. The honest statement is that the growth is transient on every form this machine can enumerate, and that a day further out is a day this machine cannot enumerate.

One thing can be said about them from the table itself, and it points the same way as everything else on this page. The share of forms that keep their width falls steeply as the starting width rises: fourteen of the 44 forms starting at width one hold it, 199 of 946 at width two, 440 of 10,164 at width three, and 459 of 53,361 at width four — from a third down to under one in a hundred. A wide form is not merely likely to shrink; it is more likely to shrink than a narrow one, which is the opposite of what a reduction whose only worrying step adds options would suggest.

The other thing the sweep cannot say is anything about which forms stay level. One thousand one hundred and twelve come out exactly as wide as they went in — 63,403 narrower and none wider, which is the whole of the 64,515 — and those 1,112 are not characterised here.

Where the ladder goes next #

reversibility has two rungs to here: that bypassing is not a contraction, and that the growth it produces does not survive. The rung this page names as its own next step — a pool a day wider, where a bypass can donate an option list of four or five — is still open, and it is open for the reason the last section gives: day four cannot be enumerated.

The two rungs above go the other way, at the second direction this page names and could not measure. The canonical form is smallest in options and in nothing else, and what a value costs to write down prices it in the currency a reader actually pays. Counted in symbols the width-seven value of this page is not the longest of its day; the longest has six options. And every canonical form born on day three, bar the seven integers, writes some subposition out twice — so the expression a reader reads is longer than the object it names, and the reduction was never trying to make it shorter.

The same position written once then measures how much of that repetition there is, and the answer is the tidiest number this anchor produces. Writing out day three’s canonical forms as trees takes 24,940 nodes. Naming each distinct subposition once inside each form takes 10,102. Naming each distinct subposition once across the whole day takes exactly 1,474 — one node per value of the day, because nothing appears inside a canonical form that is not itself a value of the day, and the day is closed under taking options.

That last equality is the sharpest thing the anchor has. It says the printed expression’s whole cost is repetition: the day’s values are the day’s subpositions, so the object being written is a graph on 1,474 nodes and the notation is a tree unrolled from it. Width, which this page measures, is the branching factor of that unrolling.

Two neighbours are worth the trip. How much a list of options can lose is the same question asked of the other reduction, where the count comes out of the shape of an order and there is nothing transient about it. And how old a value is is the birthday measure taken seriously, where the quantity that fails to bound the width here is shown doing the work it can do.