Four thousand nine hundred regions with no name

A loop is written with two names settles the two-position regions completely. All 256 of them, each written as its onside and its offside — the game it is when every infinite play goes to Left, and the game it is when they go to Right — and ten names cover all 512 sides: nought, one, minus one, star, on, off, over, under, upon + star and its negative.

It ends by asking about three positions, and by saying why it does not answer: 2¹⁸ is 262,144 regions, and identifying each against 1,474 test games is four hundred million sums.

Two reductions, both stated #

The count is affordable after two cuts and neither is free, so both are on the figure rather than behind it.

The region is its reachable part, named up to relabelling. A graph whose third position cannot be reached from the first is a two-position region with a spare node attached, and the other two positions can be called either way round. That takes 262,144 to 111,364 distinct forms, of which 110,976 are genuinely three positions.

The test set is the 22 values born by day two rather than the 1,474 born by day three. A name is only as good as the games it was checked against, and the earlier essay already measures what the smaller set gets wrong: the two-position census runs both, and the names that change between them are counted there. So the cost of this reduction is known rather than guessed.

Of the 110,976, 110,934 have a cycle in them. A cycle is what puts a region outside the brace form entirely. Forty-two do not — those have brace expressions and need no sides at all, which is a reminder of how rare a three-position graph without a loop is once both players have arbitrary edges.

What the vocabulary covers #

The two-position vocabulary is 70 entries against this test set: the 22 day-two values, and each of the six stoppers with each of those values added, dropping any whose sum with a test game is drawn.

Against it, 106,003 of the 110,934 regions are named on both sides, and 4,931 are not.

The shape of the named ones is startlingly familiar. On & off is 57 per cent of them — 60,654 regions — with off & off and on & on at 15,050 each. At two positions the same three pairs led with 94, 53 and 53 of 256, which is 37, 21 and 21 per cent. So the leading pair has grown and the second and third have shrunk, and the ordering is identical.

Thirty-two thousand of them have the same name on both sides, which is the condition for never being drawn against anything. At two positions that was 133 of 256, a little over half; at three it is 32,146 of 106,003, under a third. A larger region draws more often, which is the direction one would guess and is worth having counted.

What the leading pair means #

The dominance of on & off is worth reading rather than reporting, because it is the same fact at both sizes and it says what a loopy region mostly is.

A region’s onside is on when giving every infinite play to Left makes Left able to move for ever; its offside is off when giving them to Right does the same for Right. So on & off is the name of a region in which both players can keep the play going, and the convention alone decides who benefits.

At two positions 37 per cent of regions are like that; at three, 57 per cent. The reason is arithmetic: keeping a play going needs a cycle a player can stay on, and three positions offer far more cycles than two. So the commonest kind of loopy region is the one with nothing to say — the outcome is whatever the convention says it is, at every split, against everything.

That is the loopy analogue of a position at temperature nought: a game whose whole content is a rule from outside it. And the regions worth naming are the minority underneath.

The ones with no name #

The 4,931 are the answer to the question the earlier essay asks.

3,990 of them are named on one side and blank on the other. That is the shape that says where the gap is: the region is perfectly ordinary read one way and needs something new read the other, which is what a region whose two conventions differ sharply looks like.

The smallest of them is short enough to write out. One position with a Left move to an empty position and a Right move to a position where Right can move to itself for ever — in braces, if braces reached it, {0 | off}. Left’s option is nothing at all and Right’s option is the game in which Right passes indefinitely.

That is three positions and it is not a sum of anything the vocabulary holds. Read it with infinite play given to Right and Right’s second option is a win, so the offside is off; read it with infinite play given to Left and the same option becomes a loss, and what is left is a game the vocabulary has no entry for.

Thirty-five names, and then more #

Among the regions the vocabulary can read, 35 distinct names are used — three and a half times the ten that two positions needed.

The new ones are not exotic. They are the ordinary day-two values that two positions never produced as a side — a half, two, minus two, up, down, star-two, one-star — together with the stoppers carrying those values: over + a half, over + minus two, upon + down, minus upon + up. Two positions produce a side from the small end of the vocabulary and three positions reach into the rest of it.

The sums of named values run out in the same way, one day earlier and for a different reason. So the growth has two parts and they are different in kind. The vocabulary’s unused entries get used, which is a fact about how small two positions is. And the vocabulary runs out, which is a fact about three.

How much of the space is actually new #

One arithmetic check makes the growth legible, because 110,934 against 256 is a ratio that means nothing on its own.

Two positions give 2⁸ = 256 graphs and every one of them is a region. Three give 2¹⁸ = 262,144 and 110,934 survive the reduction, which is 42 per cent. The loss is almost entirely the unreachable third position: a graph in which neither player can get from the first position to one of the others is a two-position region, and there are a great many of them.

So the space grows by a factor of 433 and the vocabulary by a factor of 4.8. The names grow far more slowly than the regions, which is the shape a notation has to have if it is to be worth anything — a naming scheme growing as fast as the objects it names is a list rather than a notation.

Whether that continues is the question four positions would answer, and 2³² graphs is not a census this apparatus can take.

Why the region has to be reduced first #

The reduction from 262,144 to 110,976 is worth one paragraph, because it is doing more than saving time.

A three-node graph in which the third node is unreachable is not a three-position region; it is a two-position region with an irrelevant position drawn beside it. Counting it would report the two-position answers twice over and inflate every share. And two graphs differing only in which of the two other positions is called b are the same region written twice, so leaving them separate would double-count every asymmetric one.

That is the same discipline the whole anchor runs on. A position’s value is what a notation names and two expressions of one value are one object, so a census over expressions rather than over values is a census of the notation rather than of the subject.

The forty-two without a cycle #

The regions with no loop in them are worth a paragraph for what they are not.

Forty-two of 110,976 — four in ten thousand — have no cycle reachable from the starting position. Those are ordinary finite games: they have brace expressions, they have values, everything the brace form is built to do applies to them, and they need no sides at all.

At two positions the same count is larger in proportion, because a two-node graph has fewer ways to close a loop. So the direction is clear and the endpoint is obvious: a region of many positions is almost certainly loopy, and the finite games are a vanishing corner of the space of graphs.

Which is worth holding against how the subject is usually presented. The brace notation comes first and the loopy theory is an extension for awkward cases; counted over graphs it is the other way round, and the brace form is the special case that happens to cover every game anybody constructs by the ordinary recursion.

The smallest unnamed region, followed #

One region is small enough to work through, and following it says exactly what the vocabulary is failing at.

Call the positions $a$, $b$ and $c$. From $a$, Left may move to $b$ and Right to $c$. Position $b$ has no moves at all. Position $c$ has one move, Right’s, and it goes back to $c$.

Read the offside first. Give every infinite play to Right; then Right, standing at $c$, moves there for ever and wins. So Right’s option from $a$ is a win outright, and the offside is the game in which Right can always move and Left cannot — off, which the vocabulary has.

Now the onside. Give every infinite play to Left. Right’s move to $c$ now loses: the play that never ends is Left’s, so Right moving there has thrown the game away. Right’s only option is a loss, and Left’s only option is the empty position. What is left is a game in which Left has one move to nothing and Right has one move that loses, and no name in the vocabulary reproduces its column against the 22 test games.

The convention has changed the game rather than the winner. That is what the two-name notation is for, and it is also where it runs out: the two readings of one region can differ by more than a name, and one of them can be a game nothing in the vocabulary is.

What a side is, and how a name is found #

The loopy convention throughout: a play that never ends is a draw, and a side is the game the region becomes when every infinite play is awarded to one player. The onside gives them to Left and the offside to Right.

Three conventions of the census.

A name is identified rather than derived. The region is added to every test game, each sum is solved by retrograde analysis under the convention, and the column of winners is matched against the same column for a vocabulary of named games. A name that reproduces the column is the side’s name as far as the test set can tell.

The test set is the day-two values. Twenty-two games, against the 1,474 the two-position census can afford. What that costs is measured there and not here.

And a region is its reachable part. Positions no play can arrive at are not part of the game and are dropped before anything is counted, and the two remaining positions are named either way round so that a region drawn twice is counted once.

A name is a name against a test set #

The names are names against a test set, and what the smaller test set gets wrong is measured on the two-position regions rather than here. Two sides identified as the same game are two sides no test game tells apart, which is a weaker statement than equality and is the only statement available.

The 4,931 are counted and not described. What they are is the subject of the essay that follows; here they are a count, and the count is what the earlier essay asked for.

Nor is the count of names a count of games. Thirty-five names are used by the regions the vocabulary reads, and the vocabulary holds seventy — so half of it goes unused, and a name nothing takes is not evidence about anything.

And nothing here runs the day-three test set. The two-position census runs both and measures the difference; whether a name that survives 22 games survives 1,474 is known for 256 regions and not for these.

What this does to the two-name notation #

The two-name notation survives the census and it survives changed, which is worth separating.

It survives. Every region here has two sides, both are well defined, and 96 per cent of them have names in a vocabulary built for a much smaller family. The notation is not breaking; it is being used at a size it was not measured at.

And it changes. The vocabulary is no longer a list somebody can carry. Ten names is a list; thirty-five is a table; and the 4,931 leftovers say the table is not complete. The brace form’s trouble was length — a game born on day three takes twenty-two characters and the abbreviations reach one game in twenty-three — and the two-name form’s trouble is different in kind: the names themselves run out.

That is the more serious failure of the two. A notation that is long is a notation somebody can still use; a notation missing a name has nothing to write down at all. And the count above is the first measurement here of a notation failing in that second way.

Where this leaves the measure #

Six essays here have been about what a notation costs, and every one of them has measured length: twenty-two characters for the middle day-three value, a brace needed by one board in so many, a sum shorter than its single value or longer.

This one measures something the others could not: whether there is anything to write at all. A length is a number attached to an expression that exists, and 4,931 regions here have no expression to attach one to.

That reorders the account of its subject. The brace form’s two hard edges are a game with a cycle, which has no finite expression, and the minus sign’s equation, which is false under misère play. The two-name form was the repair for the first of those. What the census says is that the repair is itself incomplete — not in principle, since the sides exist, but in the vocabulary anybody has written down.

A notation with a hole in its vocabulary is a different kind of object from one that gets long, and this is the first of the two this sequence has met.

Still open: what the missing names are #

The count says the vocabulary runs out and says nothing about what would fill it.

Two answers are available and they are not the same. The earlier essay guesses that the missing names are sums of two loopy ones — on + over, and the rest of that family — which would make the extension finite and describable. The other possibility is that a three-position region’s side can genuinely need three positions to write, in which case the vocabulary grows with the regions and there is no closed list.

Both are testable with the apparatus already here: build the extension, run the 4,931 against it, and count what is left.

The second possibility has a consequence worth noticing before it is tested. If a region’s side can need as many positions as the region, then the two-name notation is not a naming scheme at all past some size — it is a statement that the region has two readings, with the readings written out as graphs. That would still be worth having; it would not be what the ten names at two positions made it look like.

That is the essay that follows, and the answer is not the one the guess expects.