Where the braces stop

The notation was the argument makes the case that {L | R} is not shorthand. Up, star and the brace form are the claim that these objects add, and no table of outcomes can replace them, because two positions with identical outcomes can have different sums. That is a defence of the notation against the thing it replaced.

This rung is about what it costs and where it stops. Both are measurable, and neither is a matter of preference.

Start with the property worth having. Day three holds 1,474 games and produces 1,474 different expressions. No two games are written the same way, which is not automatic and is the whole reason a notation is worth more than a description — an expression that named two games would make every equation on this site ambiguous. It is checked here rather than assumed.

Now the cost. Day 0 is one character. Day 1 is two. Day 2 reaches eleven. Day 3 reaches fifty, and its middle expression is twenty-two characters: things like {1/2, {1 | 0}, {1 | ∗} | −1/2, {0 | −1}, {∗ | −1}}.

Day four is not in the table because day four holds something over 10³⁸ games, and its expressions would be built from day three’s the way day three’s are built from day two’s — so the longest would be somewhere past two hundred characters. The notation remains exact. It stops being readable somewhere between the third row of that table and the fourth.

It is worth being precise about what “exact” is doing in that sentence, because it is the property everything else trades against. The expression is not a summary of the game and it is not a label attached to it. It is a complete construction: from the expression alone, the whole game tree can be rebuilt, every option recovered, every sum recomputed. Nothing about the position that could affect play is left outside it. That is why two different games cannot share one, and it is why the length grows the way it does — the expression is carrying the whole object, and the objects roughly square each day.

The alternative that was actually tried, and dropped, was to carry less. A table of outcomes carries one of four values per position and is very short indeed. The rung below shows why it fails: two positions with identical outcomes can sit in sums with different outcomes, so the table throws away exactly the information that adding needs. Between the two extremes there is nothing anybody found — no partial description that is shorter than the expression and still adds. The notation is long because it is the minimum that works, not because nobody tried to trim it.

Why the table stops at three #

Four rows is a short table and the reason it is short is worth a paragraph, because it is the same reason the notation strains.

Day 0 has one game. Day 1 has four. Day 2 has twenty-two. Day 3 has 1,474. The pattern is not a growth rate, it is a tower: each day’s games are the pairs of sets of the previous day’s, so the count is roughly exponential in the previous count. Day 4 is upwards of 10³⁸ and nobody has enumerated it. This site cannot, and neither can anybody else — not because the recursion is hard but because there is nowhere to put the answers.

So every measurement below is a measurement over days nought to three, and that is the whole of what exists to measure over. Anything said here about “how long an expression gets” is said about the last day anybody can look at, and the honest form of the claim is a direction rather than a curve: one, two, eleven, fifty, and the next term is not going to be sixty.

That is also why the vocabulary question below is the interesting one rather than the length question. The lengths are going to grow whatever anybody does. What can vary is how much of the universe gets a name instead.

What people actually write #

Nobody writes those expressions, and what they write instead is measurable too.

0, 1, −1, ∗, ↑, ⇑, ∗2, 1/2, 2·↑∗, −1/4, −1/2∗. Those are the objects the subject is written in, and the measurement is how far they reach.

Every game born by day two: all 22 of them, or rather 18 of the 22 with the other four needing a brace — 81.8 per cent. Then day three: 63 out of 1,474. Four point three per cent.

That number is the shape of the whole subject and it is worth sitting with. The named vocabulary is not an abbreviation of the notation; it is an abbreviation of the small corner of the notation where the interesting objects live. Numbers, stars, ups and their small combinations are the values that turn up in real games, and they turn up because real games are sums of simple things rather than arbitrary points of the day-three universe. The birthday of a sum is about how that corner is reached; the count here is about how small it is.

The curve between those rows is worth reading rather than the endpoints. One hundred per cent, one hundred, eighty-two, four. The collapse happens in a single step, and it happens at exactly the day when the games stop being combinations of the day before and start being arbitrary choices of option sets. Day two’s games are still describable as this number plus that infinitesimal; day three’s mostly are not, and there is no vocabulary anybody could have invented that would keep up, because the number of things to name outruns the number of things worth naming.

There is a temptation to read 4.3 per cent as a failure of the vocabulary and it is the opposite. A vocabulary that named all 1,474 would have 1,474 words in it and would be a list, not a language. What has happened is that the objects worth naming got named and the rest kept their expressions, which is the right division and is why the expressions had to be exact.

The first hard edge: a game that cannot be written out #

Two places the notation does not reach, and the first is structural.

A brace expression is built by listing a game’s options, then their options, and so on until the options run out. The construction is a recursion and it terminates because games are well-founded: every line of play ends.

Loopy games are the ones where that is false. on is a single position whose only move, for either player, is back to itself. Its options are {on | on}, whose options are {on | on}, and the expansion does not terminate — not because it is long, but because there is nothing at the bottom of it. Twelve of the thirteen loopy positions this site keeps have a cycle among the positions reachable from their start, and none of the twelve has a finite expression.

So they were named. on, off, dud, over, under are not abbreviations for expressions the way ∗ is an abbreviation for {0 | 0}. They are primitives, added to the language because the language could not build them, and each had to be given its own arithmetic by hand. One part that never ends is what that arithmetic looks like when one of them turns up inside a sum.

The thirteenth game in that table is the control and it is there on purpose. It is a loopy-looking position with no cycle in it, and it has a perfectly ordinary finite expression. What separates the two is not that one is drawn with arrows and the other is not; it is whether a move can lead back to a position already on the way. That is a property of the graph and it is decidable, which is why the figure computes it rather than sorting the games by reputation.

The workaround the subject settled on is worth naming precisely, because it is not “give up”. A loopy game has no finite expression, but it does have a finite graph — thirteen positions at most in the table above, and one in the case of on. So the object is written as a graph and the theory is rebuilt on graphs: outcomes are computed by working backwards from the positions that end rather than by recursion on options, which is a different algorithm answering the same question. What is lost is not the answer. What is lost is the expression, and with it the ability to write a game down in a line of text and hand it to somebody.

That loss is why the primitives were named rather than drawn. on is a graph with one node and two self-loops, and nobody wants to draw that every time; it is easier to call it on, state its arithmetic once, and use the name. The vocabulary grew for the same reason it grew in the finite case — because a small number of these things turn up over and over — and it stopped at about five for the same reason: past that, the graphs are all different and there is nothing to name.

What the notations that were dropped got wrong #

The two edges are worth setting against the notations that did not survive, because those failed on a different axis and the difference is the whole reason the brace form is the one still in use.

Grundy’s numbers came first and they are still the right tool for the game they describe. An impartial position gets a single non-negative integer, sums are computed by exclusive-or, and the whole of impartial theory fits in that. It was dropped as a general notation for one reason: it has nowhere to put the fact that the two players have different moves. There is no Grundy number for a Domineering position, not because the number is hard to compute but because the object it would describe does not exist. That is a coverage failure and no amount of extension repairs it.

The outcome table came second and is the one the rung below dismantles. It covers every game — every position has an outcome — and it fails on arithmetic instead: two positions with the same outcome can sit inside sums with different outcomes, so the table cannot be added. Complete coverage, no arithmetic.

Between those two the brace form is the object that has both, and the price it pays is the length measured above. That is the trade the subject made and it is worth stating as a trade rather than as a discovery: shorter notations exist and each of them loses something the brace form keeps. Nothing here is an argument that fifty characters is a good length. It is an argument that the alternatives cost more.

The second hard edge: the minus sign #

The second failure is not structural. It is worse, because the notation writes it down perfectly and means something else by it.

−G is defined by turning the game round: swap Left’s options for Right’s, all the way down. The point of the definition is the equation G + (−G) = 0, which says that a game and its mirror image cancel — whatever Left does in one, Right copies in the other, and the second player wins.

Under normal play that is exactly right, on all 1,474 games born by day three, checked one at a time. Every sum is worth 0 and every one is a second-player win.

Under misère play, where the player unable to move wins, every single one of the 1,474 is a first-player win. Not most of them. Not the awkward ones. All of them, including the sum 0 + 0.

The reason is the same copying strategy read backwards. Under normal play the copier always has a reply and therefore never runs out first; under misère running out first is what he wants, so the strategy that guaranteed him the win now guarantees him the loss. The mirror argument does not weaken under misère — it inverts.

That is a much sharper failure than the loopy one. The expression G + (−G) is finite, well-formed and unambiguous. The notation is not straining to write it. What has happened is that the equality the notation encodes is normal-play equality, and misère play needs a different one — which is why the genus of a sum exists and why misère theory had to build a separate apparatus rather than reusing this one with a sign flipped.

What the two edges have in common #

They look unrelated and they are the same failure seen twice.

The brace form is a statement about a game’s options, and everything the notation can do follows from two assumptions about options: that following them terminates, and that a game is determined by which player is left without one. The first assumption is what loopy games break. The second is what misère play breaks — the moves are identical, the option structure is identical, and the convention that reads it is different.

So the notation is not a description of a game. It is a description of a game under a convention, and the convention is invisible because there is only ever one of it in view. A pass is not a move makes the same point from a third direction: a rule that looks like it changes nothing about the position changes what the notation is about.

That is why the two edges resisted patching in such different ways. Loopy games got new primitives and a modified equality, and the result is a workable theory — on and off behave, sums involving them can be computed, and this site computes them. Misère play got the genus, then misère quotients, then the discovery that the quotient can be enormous for games whose normal-play theory is a line of arithmetic. The first edge needed more vocabulary. The second needed a different subject.

What survives #

None of this is a complaint about the notation, and the census is the reason.

Fourteen hundred and seventy-four games, fourteen hundred and seventy-four expressions, every one exact, none ambiguous, and an arithmetic on them that this site computes tens of thousands of times without the equality ever failing where it is claimed. The sum is the object is the argument for why that matters and nim and the nim-sum is the special case where it collapses to a single number. The notation delivers what it was designed to deliver.

What the measurements add is the boundary, stated in numbers rather than in warnings. It writes every well-founded game and no loopy one. It supports every normal-play equation and no misère one. And it does so at a length that is fine for the corner of the universe real games live in and unusable outside it — one game in twenty-three at day three, and day four is where anybody would stop reading.

There is one more thing the measurements settle, and it is about how to read the two edges together rather than as a list.

Both are places where a reader can write something perfectly well-formed and be wrong about what it means. on cannot be written at all, so a reader who writes {on | } and expands it has produced a sequence of symbols that does not denote a game — the failure is loud and arrives immediately. G + (−G) = 0 is a true statement, correctly written, that stops being true when the convention changes underneath it — and the failure is silent, because nothing in the expression records which convention it was written under. Of the two, the silent one has caused far more trouble, and comparison is a search is where the trouble shows up in practice: the machinery that decides whether two games are equal is machinery for one convention, and it does not announce that.

A notation that had none of those limits would have to be either less exact or less useful, and the interesting thing about the three numbers is how cleanly they separate. The length is a practical limit and could in principle be pushed by better abbreviations. The loopy edge is a theorem about recursion and cannot be pushed at all, only worked around. The misère edge is not about the notation; it is about which question the notation was built to answer, and where the order and the sum disagree is what happens when a reader forgets which one that was.