The cheapest way to show a value

A value exists because a construction produced it. A value is realised because somebody can point at a position worth it. The values nobody’s game produces counted the difference and found under a tenth of day three ever turning up on a board, and closed by naming what came next:

The obvious next rung is a value’s cheapest witness: for each realised value, the smallest position of any ruleset producing it, and the growth of that size against the value’s birthday. If the two grow together, birthday is a proxy for complexity after all.

The sweep is 11,397 positions across fifteen rulesets and it reaches 1,193 distinct values. For each of those there is a smallest exhibit — the fewest pieces any position in the sweep needs to show it — and the answer to the question as asked is that the two do not grow together. The correlation is 0.32, which is close enough to nothing to be reported as nothing.

That answer is wrong, or rather it is right about a population that should not have been measured in one piece.

What counts as a piece #

Fifteen rulesets count their positions in fifteen different units, and a census across all of them has to pick one. The unit here is the thing a player can see: an edge in Hackenbush, a square in Domineering or NoGo, a counter in an End-Nim heap, a coin in a Shove strip, a vertex in a Col graph.

It is deliberately not a measure of difficulty. A 3 × 3 Domineering board is nine squares and a game tree in the thousands; a nine-edge Hackenbush string is nine pieces and a value readable straight off the drawing in binary. Size here is the size of the exhibit — how much board a reader has to be shown — and it is the only measure across fifteen rulesets with a reading anybody can check by looking at the picture.

The consequence is that the measure rewards games played along a line. A row of n coins is n pieces; a rectangle of the same area is a product. So the cheap exhibits are rows, and the census confirms it before it says anything else.

Fourteen rulesets, and three of them do most of the work #

Every one of the fifteen rulesets in the sweep contributes positions; fourteen of them are the cheapest way to show at least one value, and the fifteenth is Cutcake, whose values are whole numbers a Hackenbush string shows in fewer pieces.

The distribution is lopsided in a way that says more about drawing than about games. Hackenbush with green edges owns 297 exhibits, Shove 278 and End-Nim 214, and those three between them own two thirds of the census. Toppling Dominoes adds 84, Toads and Frogs 48, Clobber 45. Domineering owns exactly one.

That is not a ranking of how interesting the games are. Domineering is one of the richest games on this site — its small boards produce switches, infinitesimals and the hottest values in the sweep — and it owns one exhibit because a Domineering position of n squares is a rectangle or a piece of one, and a rectangle of nine squares is nine pieces where a nine-edge string is also nine pieces and gets much further.

The measure rewards a line. A game played along a strip converts pieces into value at the best possible rate, because each piece adds one move and the moves compose. A game played on a region spends pieces on adjacency. So the cheap exhibits are lines, and a reader wanting to be shown an unfamiliar value should expect to be shown a row of coins.

There is a real consequence in that for how this collection is written. Nearly every figure on this site that has to display a named value displays it as a Hackenbush string or a Shove strip, and the reason is not that those games are more fundamental — it is that they are the cheapest exhibits, which is this census stated as an editorial habit.

Half of everything fits in six pieces #

The distribution of exhibit sizes is not what a reader who has spent time with day three expects.

Half the 1,193 values are shown by a position of six pieces or fewer. Four values need one piece, sixteen need two, and 334 — more than a quarter of the whole census — need exactly five. The largest exhibit anywhere is fifteen.

The fall past seven is not evidence that large exhibits are rare. It is evidence that the sweep stops: most rulesets here are enumerated to six or seven pieces because that is what a build can pay for, so a value whose cheapest exhibit is twenty pieces is not recorded as needing twenty — it is recorded as not being realised at all. The census can say a value is realised and cannot say a value is unrealisable, and the same asymmetry applies one level down to the sizes.

The five rows that break the pattern #

The last five rows of the first figure are values born on days seventeen through twenty-one, and every one of them is exhibited on six squares.

Six squares of Shove, to be exact. LLLLLL is worth 21, RRRRRR is worth −21, LRLLLL is worth 69/4. These are the deepest values in the whole sweep by birthday and among the cheapest to draw.

Meanwhile the largest exhibits in the census — four End-Nim rows needing fifteen counters — are values born on day four and day eight.

So the picture is an inversion, and stated that way it sounds like a deep fact about the two orderings. It is not. It is a fact about integers, and once seen it is obvious.

An integer’s birthday is the integer #

The number 21 is born on day 21. That is not a curiosity of the construction, it is the construction: n is {n−1 | }, so each whole number takes one more day than the one below it, and the number tree grows one integer a day along its spine.

A Shove strip of six coins all one colour is worth 21 because Shove’s values are sums of powers of two along the strip, and a six-coin strip can carry a value in the twenties. So the position is six pieces, its value is a large integer, and the integer’s birthday is large by definition.

Four hundred and sixty-five of the 1,193 values are numbers. They occupy the whole right-hand end of the birthday scale and the whole left-hand end of the size scale, and between them they drag the correlation down to 0.32.

Take the numbers out and the correlation is 0.73. The latest birthday drops from twenty-one to thirteen, and the two measures come into agreement — not perfect agreement, but the kind a reader would call a relationship.

So the answer the rung below wanted is yes, with a condition. Birthday is a fair proxy for the size of the smallest exhibit among values that are not numbers, and it is no proxy at all across the whole population, because the numbers are a family whose birthday grows without their exhibits growing at all.

Why the numbers behave that way and nothing else does #

The mechanism is worth separating from the observation, because it says which other families would do the same thing.

A number is a value with no fight in it, and its birthday counts the resolution of the dyadic fraction rather than the complication of the position. Seven eighths is born on day four; twenty-one is born on day twenty-one; and the two facts have nothing in common except that both are counted by the same clock. What a board has to do to reach a large number is add moves along a line, which costs one piece each.

Nothing else in the sweep has that property. An infinitesimal’s birthday counts the depth of the option structure, and option structure has to be built out of board — a Clobber row worth ↑∗ has to have the pieces to offer both players moves that lead into each other. A switch’s birthday counts how far apart its options are born, and those are positions too.

So the split is between values whose birthday counts arithmetic and values whose birthday counts structure, and only the second kind has a birthday that a board has to pay for. That is a sharper statement than the correlation and it is the statement the correlation is evidence for.

The residual, which is four rows long #

If the birthday predicts the exhibit size among non-numbers at 0.73, the interesting values are the ones it predicts badly — the values much dearer to show than their age suggests.

There are four of them at the extreme and they are all End-Nim: 3,4,4,4 and 4,4,4,3 are born on day four and need fifteen counters; 4,3,4,4 and 4,4,3,4 are born on day eight and need fifteen. A day-four value is one the construction reaches almost immediately, and here it takes the largest board in the census to point at.

The mechanism is the one End-Nim’s own census found: the game has no components. A row of heaps is a single indivisible object, so its size is the whole of it, and a value that happens to fall out of a large row has no cheaper row producing it. Every other ruleset in the sweep has small positions in quantity; End-Nim’s small positions are few, because the number of rows of at most four heaps is small and their values are almost all distinct.

Four rows is not a residual worth a theory. What it does establish is the shape a theory would have to take: the values that are dear to exhibit are dear because of the ruleset that exhibits them, not because of anything about the value. Give End-Nim a competitor that produces the same value on five squares and the residual disappears — and whether such a competitor exists is not a question about End-Nim at all.

That is the honest reading of every large number in this census, and it is why the whole page reports upper bounds. A cheapest exhibit is the cheapest known exhibit, and the census is a record of what fifteen rulesets happened to reach.

Why the integers dominate every statistic here #

The two measures agree badly overall and well once the numbers are taken out, and the reason is worth stating, because it says the integers should be excluded from most of the statistics on this anchor rather than only from this one.

An integer $n$ is what a position is worth when one player has $n$ moves and the other has none. Every ruleset produces those in quantity, because every ruleset has lopsided endgames — a strip only one player can enter, a region only one colour can reach, a heap the other player cannot touch. So the integers are realised by many positions in many games, and a table of realised values is full of them.

They also grow linearly in two different ways. A position exhibiting the integer $n$ needs about $n$ moves in it, so its size grows linearly in $n$; and the integer $n$ is born on day $n$, so its birthday grows linearly in $n$ too. Two linear relations with different constants, and comparing them across a table dominated by integers measures the ratio of those constants rather than anything about complexity.

That is the whole of the apparent independence. Take the integers out and what is left are the values whose cost and birthday both depend on how complicated they are, and those agree.

So the honest form of every statistic on this anchor is excluding the numbers, and this page is where that first becomes visible. It is also a caution about the other direction: a ruleset that produces mostly integers will look cheap on any measure of cost against birthday, and what is being measured is how lopsided its endgames are.

What the census does not say #

Four limits, and the second is the one that would change a number.

Every size is a size in this sweep. A value’s cheapest exhibit is the smallest position enumerated here that produces it, and a ruleset not in the sweep, or a larger board in one that is, could produce a smaller one. Every size in the census is therefore an upper bound on the true cheapest witness, and the bound is one the sweep could afford rather than one the mathematics supplies.

The correlation is a correlation and not a law. Nothing in the census asserts 0.73; a correlation is the kind of number that is meant to be read rather than checked, and the assertion the build does run is the structural one — that the deepest day’s exhibits are smaller than the shallow days’ largest, which is the inversion the whole page turns on. A sweep in which that stopped being true would stop the build.

Pieces are not moves and neither is difficulty. Fifteen End-Nim counters in four heaps is a bigger exhibit than a nine-square Domineering board and a very much smaller search. This page measures what a reader has to be shown, and what a value costs to compute is a different quantity with a different answer.

And the unit is a judgement. Counting a Col vertex as one piece and a Domineering square as one piece puts a five-vertex graph and a five-square region on the same footing, which is defensible and is not forced. A measure that counted moves available, or squares of drawing, would rank the rulesets differently and would not change the split between numbers and everything else — that split is about birthdays, and birthdays do not depend on the unit at all.

The convention, named #

Normal play throughout, and every value is a canonical form, so two positions count as exhibiting the same value when their reduced forms agree.

A value’s birthday is the number of days of the construction its canonical form takes: nought for zero, and one more than the largest birthday among its options otherwise. A value’s cheapest witness is the position of fewest pieces, over every ruleset in the sweep, whose value it is; ties are broken by ruleset name, which affects the attribution in the figures and none of the counts.

The sweep excludes sums deliberately, for the reason the rung below gives: nearly every value is the value of some sum, so counting sums would answer an easier question. Only single positions of single rulesets count.

Where the ladder goes next #

The realisability anchor has two rungs to here: which values a game reaches, and what the cheapest way to reach one costs.

The birthday is a floor establishes the relation this page finds. The birthday bounds the cost from below and the bound is attained about two thirds of the time, which makes it a genuine measure rather than a coincidence — and leaves the other third to explain. Wider costs less tries the width of the form as the explanation and finds it running the wrong way, with what is left correlating with the ruleset a position came from.

The entry fee was the cap then removes that residue entirely, and the removal is the most useful thing on the anchor. The per-ruleset constant is not a property of the rules: the excess falls as the birthday rises inside every ruleset, which is the signature of a censored sample, because the sweep’s size cap removes exactly the values that would have paid most. Three squares past the cap, Toads and Frogs exhibits values born later than the strip is long.

The rate was the alphabet supplies what a cap cannot censor — a slope rather than a level — and deflates it in the same direction. Every ruleset produces new values at close to the rate its positions have symbols, and the seven span less than a factor of two. What separates the games is the yield, which spans a hundred and nineteen.

Read in order the anchor is a sequence of quantities that looked like facts about games and turned out to be facts about the measurement, with two survivors: the birthday floor, and the yield.