A loop is written with two names

Where the braces stop found the first hard edge of the brace notation. A game with a cycle in it — a position a play can return to — has no finite expression, because the brace form is a recursion on options and a cycle gives the recursion nothing to stand on. A board is written as a sum then measured what writing a real board costs, a board of several regions joined by plus signs, and closed on the case it could not handle. A Go player with a ko in one corner is writing a sum one of whose parts has no expression at all. Whether that part can be named, and what adding it to the rest would mean, was left open.

It can be named, and the name is two names. This essay counts how many are needed, over every loopy region small enough to take entire, and checks each pair against every finite game born by day three.

Two questions a loop does answer #

A region with a cycle cannot be asked what it is worth. It can be asked something narrower, twice.

The obstacle is a play that never ends. Under the ordinary rule the player unable to move loses, and a play that goes round a cycle for ever has no such player, so it has no winner. Suppose instead the rule is completed: every play that never ends is a win for Left. Now every play has a winner, nothing can be drawn, and the region beside any finite game is a game with two outcomes again. Complete the rule the other way, giving every endless play to Right, and there is a second such game.

The first is the region’s onside and the second its offside, in the terms Winning Ways gave them, and the pair is written with an ampersand: onside & offside. The theory behind the pair was worked out in that book’s chapter on games infinite and indefinite, and so were the loopy names used below — on, off, over, under, upon. What this essay adds is not the theory but a count: how far the names actually reach, measured rather than derived.

A side is identified here, not computed from theory. The region is added to a finite game, the sum is solved backwards from its lost positions, with each unsettled position given to Left for the onside or to Right for the offside, and the winner is recorded with Left moving first and with Right moving first. Doing that against every test game gives a column of winners. A name is any game — finite, or one of the loopy stoppers — whose own column is the same. The test games are the 1,474 values born by day three, so a name quoted below is a name as far as 1,474 games can tell.

Ten names for every region of two positions #

A region of two positions is any set of moves for each player between two positions, which gives sixteen choices for Left and sixteen for Right: 256 regions, 112 of which loopy games found drawn when played alone. Every one of their 512 sides is named, and ten names cover all of them: the four finite values 0, 1, −1 and ∗, and six loopy ones — on and off, over and under, and upon and its negative, each with ∗ added.

Only 25 regions need finite names alone: twenty are 0 & 0, and the others are 1 & 1, −1 & −1, ∗ & ∗, 1 & 0 and 0 & −1. The other 231 need a loopy name on at least one side, and the shape of the grid says which. on is {on |}, the position in which Left may pass for ever and Right can never move, and off is its mirror. The top row, where the onside is on, holds 160 regions, and so does the right-hand column, where the offside is off.

One warning about the word. Loopy games defines on this way in its prose, but its own figure, and the essays built on it, use the name for the one-position loop that both players may take. In the notation used here that game is not on. Its onside is on and its offside is off, and it sits in the largest cell of the grid.

The largest cell by far is on & off, with 94 regions. These are the regions in which either player can keep the play going for ever: giving the endless play to Left makes the region as good for Left as anything can be, and giving it to Right as good for Right. Winning Ways calls the simplest such game dud, a deathless universal draw. It has two names and no value, and the grid shows it is not a rare pathology among small loopy regions but the most common thing they are.

The grid is also triangular. With the names set out from on down to off, every pair sits on or above the diagonal, and none has an offside above its onside. That is what the definition requires: handing every endless play to Left can only help Left.

One region beside six finite games #

The pair is a claim about sums, and the plainest way to test it is to watch it make a prediction.

The region drawn is one of the smallest with a loop that belongs to neither player: from a only Left may move, to b; from b only Right may move, back to a. Started at a, the players can only hand the play back and forth. If endless play goes to Left, Left has in effect a free move in hand and the region is worth 1. If it goes to Right, the region is worth 0. It is written 1 & 0.

Beside a finite game G, the pair predicts two games, 1 + G and 0 + G, and the three rows of the figure set them against what the region plus G actually does when endless play is left drawn. Against 1/2 and 1 both names say Left wins whoever starts, and the region, solved directly, agrees: Left wins. Against −1 the names split when Right moves first — 1 − 1 is a win for the second player, so Left, and 0 − 1 a win for Right — and the region is drawn with Right to move. Against −1/2 they split with either player first, and against 0 only with Left first; the region is drawn in exactly those columns. Against ∗ they split only with Right first, and the region is drawn only with Right first.

A draw arrives exactly where the two names disagree, and nowhere else. That is not a coincidence of six games: it follows from how the sides are defined, since a position left unsettled by the propagation is precisely one whose winner depends on who is given the endless play. What the figure shows is that the two finite games 1 and 0 carry that dependence correctly for this region. Against all 1,474 values born by day three the region draws against 932, and every one of those draws is a place where 1 + G and 0 + G name different winners.

Never, or against a large share of everything #

If a draw is where the names disagree, then a region whose two names are the same can never draw beside a finite game, and all 133 regions with one name twice draw against none of the 1,474. They behave as ordinary games in every sum with a finite one, and for them the pair collapses to a single name.

The other 123 are the surprise, because they do not draw occasionally. The fewest finite games any of them draws against is 690, nearly half. The regions named 1 & 0 and 0 & −1 draw against 932. The sixteen regions whose pair is 0 & off, ∗ & off, on & 0 or on & ∗ draw against 1,257. And the 94 regions of on & off draw against every one of the 1,474, which is what dud means.

The gap between nought and 690 has a reason that can be read off the names. A region draws beside G when onside + G and offside + G name different winners, which happens whenever G lies between the two names closely enough to change sign between them. For 1 & 0 that is every G from −1 up to about 0, a band the width of one whole move; for 0 & off it is every G that is not negative, since off plus any finite game is a win for Right and 0 + G is not. Among the values born by day three a band one move wide already contains most of them, because they crowd around nought. So a small loopy region is either indistinguishable from a finite game or conspicuously not one, and no region of two positions sits between.

What a loopy name swallows #

Writing a board as a loopy part plus finite parts invites adding the finite parts to the loopy name. Some of those additions do nothing at all.

on and off absorb every one of the 21 nonzero values born by day two. Adding 2, or −2, or {1 | 0, ∗} to on gives on again, against every test game. It is the one-sided version of what one part that never ends found for the loop both players may take: a component that supplies moves for ever is not outweighed by any finite amount of material elsewhere. It is also why on & off draws against everything. Both of its names swallow any finite game added to them, so the two names stay apart and the draw survives whatever the board holds.

over and under are subtler. over is {0 | over}: Left can end it by moving to 0, and Right can only pass back to over. It absorbs exactly six of the 21: ∗, ↑, ↓, ↑∗, ↓∗ and ∗2 — the day-two values that are infinitesimal — and nothing that is a number or hot. So over behaves as something positive that none of the infinitesimals born by day two can move, not even ↓, which would bring ↑ down to nought. under is its mirror and absorbs the same six.

upon absorbs none, and it appears on the grid only with ∗ added: upon alone, {upon | ∗}, is not the side of any region of two positions, while upon + ∗ is the side of several.

For the notation this settles something the previous essay could only ask. A board with a loopy part is written as a pair of sums, onside + G & offside + G, and a loopy name frequently absorbs the finite part outright: wherever a side is on or off, every finite region beside it disappears from that side before anything is added.

A name is only as good as its tests #

Every name above was identified against 1,474 games. The obvious question is whether fewer would have done, and the answer shows exactly what identification by testing can and cannot promise.

Tested against the 22 values born by day two, the vocabulary of names separates into 70 distinct columns rather than 88, so eighteen names are run into others that the small test set cannot tell them from. It still names every one of the 512 sides. But it names four of them wrongly: four sides that the larger test set names under are named over − 1/2 by the smaller.

The mistake is instructive because it is not random. under is below nought and above every negative number; over − 1/2 is about minus a half. What separates them is a game between nought and a half: under + 1/4 is positive and over − 1/2 + 1/4 is negative. No value born by day two lies strictly between 0 and 1/2, so nothing born by day two can tell the two names apart, while the day-three values include 1/4 and several games crowded near it.

So coverage is not what the larger test set buys. It buys the right name, and it says what the names here are: the finest names 1,474 test games can tell apart, and not a proof that two names agreeing on all of them are the same game. A stopper and how to find one found the same limit from the other side, where eight test games separated the 79 stoppers into only six classes.

Equal names, and the stoppers #

A stopper is a loopy game in which no play can alternate between the players for ever, and a stopper and how to find one proposed the stoppers as the class a value theory could handle. The count here says why and adds a qualification. All 79 stoppers have one name twice: a region with no endless alternating play never makes the convention matter, so its onside and offside agree and it acts in every finite sum as a single game.

But 54 regions that are not stoppers also have one name twice. In each of them a play can alternate for ever, and giving that endless play to Left or to Right changes no winner against any of the 1,474 test games. So the class a sum can rely on — regions that behave as one game — is 133 strong, and the stoppers are the part of it that can be recognised by looking at the move graph alone. The other 54 have to be recognised by their names.

What the ampersand buys a board #

Put back into the terms of the question this notation has been asking since the brace form — what can be written, and what writing costs — the answer has three parts.

A loopy region is written, but as a pair. The brace form cannot write it; the ampersand can, and on regions of two positions it needs only ten names. Two names that add to nothing nameable found the special symbols of finite play running out as soon as sums were taken; here a loopy name more often swallows a sum than fails to name it.

A board with a loopy region is written as a pair of sums, and its outcome, draws included, is read off the pair: decided where the two sums agree, drawn where they differ. What two numbers cannot tell apart found a two-number summary losing information; this two-name summary loses none that any of 1,474 test games can detect.

And the pair collapses often. 133 of the 256 regions need one name, and the loopy names swallow most finite additions whole. For a Go player the collapse is the practical content: a ko, before any rule about repetition is applied, is a loop, and the rule that makes Go finite exists precisely so that it never has to be written with an ampersand.

What 256 regions and 1,474 tests cannot show #

The regions are tiny. Two positions each, with every possible set of moves. A ko in a real game is a region of many positions, and nothing here says how many names a vocabulary needs for regions of three or four; the six loopy names were chosen from those known to occur, and a larger region could need one not on the list.

A name is a column of winners, not a proof. Two games with the same column against 1,474 test games are not thereby equal, and the four renamings found when the test set shrank are the evidence that this matters. A name quoted here is correct as far as the values born by day three can see.

The sums are with finite games only. Adding two loopy regions to each other is a different question, since both carry an endless play and the conventions interact; the one outcome that adds found how little of that is determined.

The convention is normal play. Under misère play the sides would be different games, and the ampersand has not been checked there at all.

The conventions the names rest on #

A region is a set of positions with moves for each player; it is started at a fixed position. A play is won by the player whose opponent cannot move, and a play that never ends is given to Left for the onside, to Right for the offside, and left drawn when the region is solved on its own terms. A sum is the ordinary disjunctive sum: a move is a move in exactly one component. Each sum is solved by propagating backwards from positions where the player to move is stuck; a position the propagation never settles is exactly one from which neither player can force a finite win. The loopy names are defined as positions: on is {on |}, off is {| off}, over is {0 | over}, under is {under | 0}, and upon is {upon | ∗}.

Still open: a region of three positions #

Every region of two positions takes one of ten names on each side. Regions of three positions number 2¹⁸ = 262,144, too many to add to 1,474 games each at the cost paid here, and among them are the smallest regions with two independent loops. Whether they introduce names outside the ten — sums of two loopy names such as on + over, or stoppers with no short definition at all — and whether the gap between never drawing and drawing against half of everything survives when a region has room for a loop that only matters against a narrow band of finite games, is the next count this notation invites.