The values nobody's game produces

Every essay on this site that reaches for a pool of values reaches for the same one: the values born by day two, or by day three. There are 22 of the first and 1,474 of the second, they are produced by a construction that needs no game at all — write down two sets of values already born and take the game with those options — and they are the natural pool because they are complete. Nothing born by day three is missing from the list.

What the construction never asks is whether any of them is the value of a position. A value is born on day three because two sets of day-two values can be written down, and writing something down is not the same as somebody being able to play it.

So this essay asks the other question. Take every ruleset this site implements, enumerate its small positions, evaluate them, and collect what comes back.

What was swept, and how far #

Seventeen rulesets, each cut off at a size a build can pay for: blue-red Hackenbush strings to seven edges and blue-red-green ones to five, every Domineering rectangle up to twelve squares, Toads and Frogs on every strip to seven squares, Cutcake and Maundy Cake to five by five, Clobber and Amazons on every one-row board to seven, Col and Snort on the site’s graph family, End-Nim on four heaps of four, Shove and Push on every strip to six squares, Toppling Dominoes to seven, NoGo on the shapes that finish, partizan subtraction on four pairs of lists, and Nim heaps up to eight.

That is 11,397 positions. It is not a random sample of anything and it is not meant to be: it is the set of positions this site can evaluate, which is the set of positions it has essays about.

Sums are excluded deliberately. Almost any value is the value of some sum — a sum of Hackenbush strings reaches every dyadic rational, and a sum with a star in it reaches a great many more — so counting sums answers an easier question and gets a much larger and much less interesting number. What is counted here is single positions of single rulesets.

The two values nothing here produces #

Twenty of the 22 values born by day two turn up. The two that do not are

$$\{1 \mid 0, \ast\} \qquad \text{and} \qquad \{0, \ast \mid -1\}$$

and they are each other’s negatives, so it is one absence counted twice.

Neither is a way of writing something simpler. $\{1 \mid 0, \ast\}$ is already canonical: Right’s two options are $0$ and $\ast$, and $0$ and $\ast$ are confused with each other, so neither dominates and neither may be deleted. It is a genuinely distinct value from $\{1 \mid 0\}$, which several positions in the sweep do produce.

What is it about the two of them? A short computation over the 22 answers it.

Exactly five of the values born by day two have an incomparable pair inside an option list: $\uparrow\!\ast$, $\downarrow\!\ast$, $\ast 2$, and the two missing ones. Every other day-two value has option lists that are chains, which is to say each player’s choice is between things that can be ranked.

Three of those five are realised, and they are $\uparrow\!\ast$, $\downarrow\!\ast$ and $\ast 2$ — the three that are all small. The two that are not realised are the two that are hot: both have temperature $\tfrac12$, both are switches with a stake in them, and both hand the player who is losing the exchange a second option that is neither better nor worse than the first.

So the shape a position would have to have is specific. One player has a single move that settles the position in their favour; the other has two, one of which ends the fight level and the other of which ends it in a tie of the star kind — and the two are incomparable, so the choice between them is genuinely open. Every all-small game on this site produces positions with an incomparable option pair, because being all small is close to being made of them. No game here produces one with a fight attached.

That the seventeen chain-shaped values are realised without exception is the half of the table worth pausing on. It says the sweep is not sparse in some general way that happens to have missed two things: it reaches every day-two value whose options can be ranked, and it stops precisely at the two whose options cannot be ranked and have something at stake.

That is a claim about seventeen rulesets and a bounded sweep, and it is the kind of claim that a wider sweep may kill. It is worth stating exactly because it is refutable: exhibit a Domineering board, or a Snort graph, or an Amazons strip whose value is $\{1 \mid 0, \ast\}$, and the sentence is gone.

The direction that is a real gap #

The day-three number is not like that, and it is large.

Of the 1,474 values born by day three, 116 are produced by a position in the sweep. That is 7.9 per cent, and every one of the missing 1,358 is a perfectly ordinary object: a pair of antichains of day-two values, with an outcome, a temperature and a thermograph, that no game here has a position for.

The other direction is bigger still. Of the 1,193 values the sweep produces, 1,077 are born later than day three. A Toads and Frogs strip of seven squares has a canonical form several days deep; so does a Clobber row of six; so does almost any position with more than a handful of moves in it. The construction’s third day is exhausted long before a real game’s positions have got going.

So the two lists cross at a hundred-odd values and then diverge in both directions at once. Birthday and reachability are different orderings and they are close to unrelated. A value can be born on day two and be unreachable in seventeen rulesets; a value reached by a five-square strip can have a birthday nobody would want to compute.

The values every game arrives at #

The other half of the picture is which values are shared, and it is the more cheerful half.

The list of widely shared values is exactly the list of values with short names, and that is not a tautology. It would be perfectly possible for two unrelated rulesets to keep landing on some awkward switch, and they do not. What they share is $0$, the small integers, the halves and quarters, and $\ast$.

The reason is the one Hackenbush makes visible. A position worth a small integer is a position in which one player has a few free moves and the other has none, and every partizan game has such positions — they are the endgames. A position worth $\ast$ is a position in which each player has exactly one move and it goes to the same place, and every game has some of those too. The small values are the ones a shape of position produces, and shapes recur across rulesets because the rulesets are all games on small boards.

The values that are not shared are the ones produced by the middle of a game rather than the end of one, and the middle of a game is where the ruleset’s own character lives.

The other end of the same observation is Clobber, which is all small — whoever has a move, the other has one too — so its values are infinitesimals and its 3,272 swept positions carry 56 values between them. A ruleset whose positions are all one shape produces few values, and it is the extreme case on the table above: three thousand positions and fewer values than Hackenbush gets out of a dozen.

What the count is a count of #

Four cautions, and every one of them narrows the claim.

The sweep is bounded and the bound is arbitrary. Every ruleset is cut off at a size a build can pay for, and a larger cut-off produces more values. A claim that a value is realised is a claim with a position attached to it. A claim that a value is not realised is a claim about this table and about nothing else — absence here is absence here.

The rulesets are the ones this site implements. Seventeen is a lot for one collection and it is not a census of games. Adding partizan octal games, or Fox and Geese, or any of the several dozen games in Winning Ways that are not here, would move every number in the table upward.

Only single positions count. The exclusion of sums is what makes the numbers small, and it is the right exclusion for the question, but it means the table is not measuring what a player would meet. A player meets a board that has fallen into parts, and the board that has fallen into parts is a sum.

A canonical form is what is counted. Canonicalisation is applied to every position before its value is recorded, and that is a decision with consequences, and the consequences run the other way too: two positions with wildly different pictures and the same canonical form count once.

Which day the mismatch is really about #

There is a reading of the 7.9 per cent that makes it less alarming and more precise, and it is worth separating from the headline because the headline invites the wrong conclusion.

The construction’s third day is not a sample of anything. It is the set of values writable with three levels of nesting, and it is built by taking every antichain of the previous day as an option list, on both sides, independently. A ruleset does not do that. A Domineering board’s Left options are the vertical placements available on it, and those are constrained by geometry in a way that has nothing to do with which sets of values happen to be antichains.

So the question what fraction of day three does a game reach? is comparing a set generated by one construction against a set generated by a completely different one, and a small overlap is what two unrelated generators produce. What would be surprising is a large overlap, and nothing predicts one.

The sharper question the table can answer is which parts of the day are reached. The numbers are reached in quantity, because a number is what a lopsided endgame is worth and every ruleset produces lopsided endgames. Star and its immediate relatives are reached, because a symmetric position is what a tie is and every ruleset produces symmetric positions. What is not reached is the middle: values with several incomparable options a side, which the construction produces by the thousand and which a board produces only when its geometry happens to offer several genuinely different moves whose consequences are incomparable.

That is a statement about option lists rather than about values, and it is the honest form of what the table measures. The construction’s day three is wide because antichains are plentiful; a ruleset’s positions are narrow because a board’s moves are few and usually comparable. The mismatch is the difference between those two facts, and it would persist at any size.

The four rows also settle what the 7.9 per cent is an average of, which is the thing a single ratio hides. It is not a uniform thinning; it is one class covered completely, one covered about half, and a class three quarters the size of the whole day covered at four in a hundred.

Why the gap is not a defect #

It would be easy to read a 7.9 per cent overlap as a criticism of the construction, and it is not one. The construction’s job is to produce a closed universe — a class in which every sum, every difference and every comparison stays inside the class — and it does that by generating everything writable. Completeness is the point, and completeness is exactly why most of it is unvisited.

The comparison worth drawing is with the numbers. Where the fight stops is a number in every partizan game there is, so the numbers are guaranteed customers. The dyadic rationals born by day three are a small finite set of fractions; the ones a Hackenbush string of seven edges produces are 254 of them, and both facts are unsurprising. The values that are not numbers are where the mismatch lives, because a switch or an infinitesimal born by day three has a specific pair of option sets, and a game’s position has whatever option sets its rules give it — which is a far narrower thing.

So the answer to “which values occur?” is: the numbers, in quantity, because a number is what an endgame is; star and a handful of its relatives, because a symmetric position is what a tie is; and then, in each ruleset, a long tail of values born deep and shared with nobody.

Who asked this first, and in what form #

The question has a standard shape in the literature and it is usually asked the other way round: given a value, exhibit a game with it. Toppling Dominoes is universal — every short value is the value of some Toppling Dominoes row, with green dominoes allowed — and the proof is a construction that builds a row from an option list. Hackenbush with green edges is universal too, and the construction is the ordinal sum.

Universality settles the existence question and says nothing about the counting one. A universality proof exhibits, for each value, a position; nothing in it bounds the size of that position, and the sizes it produces grow with the depth of the value. So a universal ruleset swept to seven pieces produces a few hundred values rather than all of them, which is what the table above shows for the two universal rulesets in it.

The counting question is the one a reader of this site is actually in: given the positions small enough to solve, what is the value landscape? And its answer is a much smaller and much lumpier set than the construction’s.

What a bounded sweep is evidence for #

Everything above is a table, and a table is evidence of a particular shape. It is worth being explicit about which claims it supports and which it merely suggests, because the two look identical in a row of numbers.

Realisation is exhibited. “This value occurs” is backed by a position, and the position is in the site’s index of every position it draws with the value the solver returned for it. Those 1,193 rows are the strong half of the table and nothing about the bound weakens them.

Non-realisation is not. “This value does not occur” is a statement about eleven thousand positions, which is a large number and a tiny fraction of the positions in any one of these games. The two missing day-two values are the sharpest instance, and the sentence in the section above says what would refute them.

The proportions are the weakest part. Seven point nine per cent is a ratio between a bounded numerator and a complete denominator, and the numerator is bounded by build time. It is not a constant of nature; it is a reading taken at one size. What would make it a real quantity is the same sweep run at two or three sizes with the curve reported, and that is a great deal more computing than one figure can carry.

The reason to publish a number of the third kind at all is that its order of magnitude is the finding. If the answer had been eighty per cent, the construction’s third day would be a good model of what games produce, and every essay on this site that reaches for the day-three pool would be reaching for something representative. It is not eighty per cent. It is under ten, and the day-three pool is a laboratory rather than a sample.

Where the ladder goes next #

realisability opens here with the mismatch between what the construction builds and what a ruleset reaches.

The rung above takes the cheapest-witness question and returns an answer that is about integers rather than about complexity. The cheapest way to show a value finds, for each of the 1,193 realised values, the smallest board of any ruleset that produces it, and sets that size against the value’s birthday. Read over everything, the two measures agree hardly at all — which is the result this page half expected and would have reported as the interesting divergence.

Taking the numbers out changes it completely. With the integers excluded the two agree rather well, and the whole apparent independence turns out to have been a fact about how integers are realised: a number is what a lopsided endgame is worth, so an integer of size $n$ needs a board with $n$ moves in it for one player and none for the other, and its cheapest witness grows linearly while its birthday grows linearly too — but with a different constant, and in enough rulesets to swamp everything else in the table.

That is a caution worth carrying back to every count on this page. The numbers are the largest and least representative part of the realised set, and any statistic taken over all 1,193 values is mostly a statistic about them. The 7.9 per cent overlap, the shape of the long tail, and the two missing day-two values are all quantities that would move under the same exclusion, and none of them has been recomputed that way here.

The two directions past that are the ones this page names and neither rung takes: the coverage measured at two or three sizes rather than one, so that 7.9 per cent becomes a curve rather than a reading; and sums, where the right question is whether the positions of a single ruleset generate the whole class — universality asked with a bound on the parts, which is a question about a group rather than about a set of values.