How old a value is

A position written down and the value it carries are two different objects, and each of them has a size. The written thing has a depth: how many levels of braces it takes to write out, counted down to the position with no moves in it at all. The value has a birthday: the first day of the construction on which something equal to it appears.

Those measure different things. Depth is a property of a drawing, and a value is a class of drawings rather than any one of them. So the question is what a form’s depth reveals about the value inside it, and the answer has three parts: depth is an upper bound on birthday, the bound is attained inside every class, and a substantial minority of forms miss it.

Two measurements of one position #

Depth is defined on the writing and is a two-line recursion. A form with no options has depth 0; any other has depth one greater than the deepest of its options. So $0$ is depth 0, $\{0 \mid 0\} = \ast$ is depth 1, $\{\ast \mid \ast\}$ is depth 2, and a reader with a pencil can do it from the braces alone.

Birthday is defined on the value and is not mechanical. It is the least depth among all forms carrying that value, so it quantifies over a class, and the class is generally large. That is why the two come apart: depth is read off one drawing, birthday is a minimum over every drawing there is.

Three of those four are older than what they are worth, and the excess is not a defect in how they were written. $\{-1 \mid 1\}$ is an honest position: Left may move to a game worth $-1$, Right to one worth $1$, and each move hands the opponent something better than nothing. Both moves are bad, neither player wants to go first, and the position is a second-player win worth exactly zero — written in a way that takes two levels to say so.

The bound, and the reason it cannot fail #

The three empty cells in the hero figure are the interesting part, and they are empty for a reason that fits in a sentence. A form of depth $d$ has every option of depth less than $d$. By induction each of those options carries a value born by day $d-1$. A game all of whose options were born by day $d-1$ is one of the games the construction builds on day $d$ — that is what day $d$ is — so the whole form carries a value born by day $d$ at the latest.

Birthday is at most depth, always. That holds for every form in the subject and not merely for the 256 counted here, and the figure draws the consequence: the cells above the diagonal have nothing in them, and the generator throws rather than draws if any of them ever fills. An assertion that has never had the chance to reject anything proves nothing, so the check is built to be able to fail.

One cell below the diagonal is also empty, and the figure prints “none” there rather than a count, because empty and impossible are different claims. The cell is written one level deep and worth a value born on day zero, and the bound permits it. There is nothing in it for a reason that takes four cases: a form of depth 1 has every option of depth 0, the only game of depth 0 is the empty one, so the depth-1 forms are exactly $\{0 \mid\ \}$, $\{\ \mid 0\}$ and $\{0 \mid 0\}$ — worth $1$, $-1$ and $\ast$, all born on day one, which is the 3 on the diagonal one row down. So every form in this census that is older than its value is written two levels deep, and the gap is one day or two.

Canonicalising attains the bound #

A bound is only useful if something reaches it, and the thing that reaches it is the reduction this site already runs everywhere. The canonical form is what remains after two rules are applied until neither applies again. A dominated option is deleted: if one of Left’s options is at least as good for Left as another, the worse one is doing nothing and goes. A reversible option is bypassed: if Left’s move to $G^L$ has a Right answer $G^{LR}$ with $G^{LR} \leq G$, that option is replaced by the Left options of $G^{LR}$.

Both rules are decided by comparison rather than by inspection: a dominated option is one that loses a comparison against a sibling, and a reversible option is one whose answer loses a comparison against the whole position.

Neither rule can make a form deeper. Deletion obviously cannot, and the bypass replaces an option by the options of one of its options, which are shallower than the thing removed. So reduction moves down the hero figure’s depth axis or stays put, never up.

One position moved from depth 2 to depth 0 is a demonstration and not a measurement, and the measurement is the point. For each of the 22 values born by day two, the depth of its canonical form is compared against the least depth found anywhere in its class of forms — a class that may hold sixty-four members or four.

That is what turns an existence claim into an algorithm. The canonical form is the shallowest way of writing its value, and its depth is the value’s birthday — so a minimum over a class nobody can enumerate becomes something computed from one position by a procedure that terminates.

Twenty-four forms older than what they are worth #

The census counts the forms that miss the bound, and the count is not small: 24 of the 256, a little under a tenth.

Fifteen are written two levels deep and worth zero — a gap of two whole days. Nine more are two levels deep and worth a value born on day one, a gap of one day. Since the count is small the list can be the whole of it rather than a sample, which is the only honest way to say what a set of twenty-four has in common.

Reading down the second column is what makes the point. Every one of the twenty-four is written two levels deep, and none is written one, which is not an accident of the sample: a form of depth 1 has only the empty position for options, so the three of them are $\{0 \mid\ \}$, $\{\ \mid 0\}$ and $\{0 \mid 0\}$, worth $1$, $-1$ and $\ast$, all born on day one. There is nothing at that depth for a form to waste.

The other 228 forms of depth 2 sit on the diagonal, and so do the 3 of depth 1 and the one of depth 0 — a depth distribution of 1, 3 and 252. Nearly every form is written as deep as this pool allows, and nearly every one of those needs the depth.

Reading that figure against the list above it gives the shape of the thing. A value is a class of forms; the class has a size, which the sorted census shows; and it has a shallowest member, the canonical form, whose depth is the birthday. The twenty-four are simply the members that are not the shallowest one, and every one of them sits inside a class whose shallowest member is elsewhere.

What the solver computed, and how #

The census is a double loop. The four games born by day one are $0$, $1$, $-1$ and $\ast$; Left is given each of the 16 subsets of them and so is Right, giving $16 \times 16 = 256$ pairs. Each pair is built with game(L, R), reduced with canonical, and named. Two depths are then measured on every form — the depth as written and the depth of its canonical form — and that pair is one cell of the hero figure. The five occupied cells hold 1, 3, 15, 9 and 228 forms, summing to 256.

Out of that fall the counts this essay quotes. 22 distinct values, of which 1 is born exactly on day zero, 3 exactly on day one and 18 exactly on day two. 48 of the 256 forms are worth a number, and among the 22 values exactly 7 are numbers — and not merely seven of them: the seven were checked to be the same set as the numbers the simplicity rule produces by day two, which are $-2$, $-1$, $-1/2$, $0$, $1/2$, $1$ and $2$. Equal in count would have been a coincidence worth distrusting; equal as sets is the statement that the two constructions agree.

The fifteen non-numbers are the ratio this whole subject rests on, and the classification underneath the figure is worth reading rather than skipping. Two are nimbers. Four are up-and-down values. Two are a number with a star added to it. The remaining seven have no short name at all and are printed as the brace expressions they are — which is already, on day two, most of what there is.

That last count is the one that matters for everything above. A value with a short name is a value somebody has found a reason to name, and by the second day of the construction the majority have not been. $\ast 2$ is one of the two nimbers and is the cleanest illustration of why: it is confused with zero, neither above it nor below it nor equal to it, so it does not fit anywhere on a line of numbers. Three of the four outcome classes are comparisons with zero and the fourth is not, and day two already produces every one of them.

Day three, which was supposed to be out of reach #

Day three is built from day two exactly as day two was built from day one: choose a subset of the 22 for Left and a subset for Right. That is $2^{22} = 4{,}194{,}304$ option sets a side and about $1.8 \times 10^{13}$ forms, and reducing eighteen trillion positions is not a build step. This site said as much, declined to enumerate them, and quoted 1,474 as a published count rather than a computed one. That is not the search that has to be run, and the reason is the reduction from three sections ago.

A canonical form has no dominated option. If two of Left’s options were comparable, the smaller would be dominated and would already have gone. So Left’s options are pairwise incomparable — an antichain in the partial order on values — and so are Right’s. A game born by day three has a canonical form whose options are canonical forms of values born by day two, with no option dominating another, so each side is an antichain of the 22.

There are 98 antichains of the 22, counted by enumerating the independent sets of the comparability graph. Not four million: ninety-eight. So the day-three enumeration is $98 \times 98 = 9{,}604$ forms, each canonicalised and deduplicated by interning key. It finishes in about 250 ms and yields 1,474 distinct values — the published count for day three, arrived at here by enumeration rather than quotation. The birthday sequence 1, 4, 22, 1,474 is the literature’s; the first four terms are now this site’s as well.

Why 98 is so much smaller than four million is the same fact from the other side. Of the 231 pairs among the 22 values, 179 are comparable — the order is very nearly total, and only 52 pairs are incomparable at all. Its width — the largest set of values no two of which are comparable — is 4, and the four are $0$, $\ast$, $\ast 2$ and the switch $\{1 \mid -1\}$. A nearly total order has very few antichains, and every one of them is small.

One honesty note. The antichain condition is necessary for a canonical form and not sufficient, so some of the 9,604 have reversible options still in them. That costs nothing: the set is a superset of the canonical day-three forms, and canonicalising each one is what collapses 9,604 down to 1,474.

The surprise is the connection rather than the number. Domination was introduced to make values comparable, so that equality could be decided by comparing two small trees instead of by searching a difference game. The same rule turns out to bound the search space of the next day, because “no option dominates another” is a strong combinatorial restriction on a set and not merely a tidiness rule. The reduction that makes the birthday bound attainable is the reduction that makes the enumeration finish.

Day four, and where the model stops #

The same trick does not survive one more day, and it fails for a reason the day-three answer supplies. Antichains of the day-two order are few because that order is nearly total; the day-three partial order is not. A greedy sweep over the 1,474 values — take each in turn, keep it if it is incomparable with everything kept so far — finds an antichain of 45. Greedy is not optimal, so 45 is a lower bound on the width, and the count of option sets is therefore at least $2^{45} \approx 3.5 \times 10^{13}$ a side, and at least $2^{90} \approx 1.2 \times 10^{27}$ forms.

That is not a search this site can run, and no further pruning is on offer, because domination has already been spent. The published count of values born by day four is about $3.4 \times 10^{434}$; that number is quoted, and it was established by an argument rather than by anybody reducing that many positions.

Three other limits are worth stating plainly.

“Form born by day two” means a form over a fixed pool. The 256 are the games whose options are the four day-one games. A position of birthday two can also be written with options that are themselves written wastefully — the hero figure’s depth axis stops at 2 because the pool does.

Day three was enumerated as values, not as forms. The 1,474 is a count of classes. A depth-against-birthday matrix for day three needs the $1.8 \times 10^{13}$ enumeration that was avoided.

Duplicate options vanish before any reduction runs. game(L, R) interns on the sorted option identities, so $\{0, 0 \mid 1\}$ and $\{0 \mid 1\}$ are the same object before domination is consulted. That collapse sits underneath the two the theory names, and is why the smallest classes come out at four forms rather than one.

What the picture cannot show #

The hero figure is a matrix of counts, which is the honest way to state a claim about 256 forms and the least illuminating way to look at any one of them.

It cannot show which forms. The 15 in the corner is a fact about a set, and the set has structure — every member is a position where one player has no moves at all and the other has only bad ones — that a total cannot display. That is why the twenty-four are listed in full further down rather than sampled: at this size the list is short enough to be the evidence, and a count of twenty-four is not.

It cannot show the reduction happening. That canonicalising attains the bound is a claim about a process, and the matrix shows only where forms end up. Neither does the table of all 22 values: it reports that the canonical form is the shallowest and not how the two rules got there, and the one worked reduction beside it is a single position doing what the table says all 256 do.

An absence has no picture. The strongest statement on this page is that three cells are empty, and empty cells look exactly like cells nobody thought to fill. That is why the fourth empty cell prints “none” rather than “0” and the three above the diagonal are labelled impossible: the distinction between nothing arrived here and nothing can arrive here is invisible in a drawing, and it is most of the content. Day three is not drawn at all for the same reason in reverse — a census figure for 9,604 forms would be a wall, so what reports it is a table of five numbers.

Who found it, and the convention it rests on #

The construction, the canonical form and the birthday sequence are all Conway’s, from On Numbers and Games in 1976, where the reduction is introduced precisely so that equality can be decided by comparing forms. The sequence 1, 4, 22, 1,474 is his; the day-four term was established much later and by machine, and is a number with 435 digits in it.

The bound itself — a value is never older than the form it is written in — is the induction the construction is defined by, and reads as a triviality until the converse is asked. That converse, whether it is attained, is the part that needs the canonical form, and it is why birthdays are stated on values rather than on positions throughout the subject.

The convention is normal play, as everywhere on this site: the player who cannot move loses. Every number here depends on it. Domination and reversibility are theorems under that convention and not the other one, so under misère play there is no canonical form of this kind and no shallowest representative to read a birthday off. The construction still runs and the word “birthday” still has a definition; the sentence birthday equals the depth of the canonical form has nothing left to stand on.

Two smaller conventions decide the numbers. Depth counts levels of braces from the empty position at zero, so the form $0$ has depth 0 and $\ast$ has depth 1. And “born by day $n$” is cumulative while “born on day $n$” is not: 22 values are born by day two and 18 of them exactly on it.

Where the ladder goes next #

This anchor started with a rule for evaluating a position whose options are numbers, asked what its central word means, turned the answer into a piece of strategy, traced where the numbers came from, and then walked off the end of what this site can compute. This rung goes back and measures the finite part: not which numbers exist by day $n$, but how the day of a value relates to the writing of it.

Birthday as an ordinal. The bound above is an induction with no upper limit in it, so nothing forces a birthday to be finite. Past every finite day comes day $\omega$, and the objects born there — $\omega$, its reciprocal, and the numbers on no finite day at all — are already surveyed one rung down, with the reason this site’s evaluator cannot hold them. What belongs here is the arithmetic of ordinal birthdays rather than a second tour of the objects: what a birthday of $\omega + 1$ means, and why the bound survives the transition while the enumeration does not.

The birthday of a sum. Two games with birthdays $m$ and $n$ have a sum whose birthday is at most $m + n$, the bound that stops a position built from many small parts from being unboundedly complicated. Whether it is attained, and how often it is slack, is the measurement this essay made for depth.

The width of the day-$n$ order. The day-three enumeration turned on one number: 4, the width of the day-two order. Day three’s is at least 45, and the sequence of widths decides how far this kind of enumeration ever reaches.

And birthdays under a bounded pool. Every count here is over forms whose options come from a fixed set. Bounding instead the number of options, or the size of the written form, gives a different census with a different diagonal — the version that would say something about positions a player might actually meet, where a board with forty pieces is routinely worth a value born on day two.