A stopper and how to find one

A stopper is a loopy game with no infinite alternating run in it, and it is the class a value theory for loopy play would have to be about. This page measures the class: how many games are in it, what being in it buys, and whether its members are as different as they look.

Six rungs of this anchor stay at the level of outcomes, and an outcome with no value behind it says why: a loopy game can be drawn, a drawn game is not a number, and there is nothing to add. The one outcome that adds found the one thing that does compose and closed by naming what a value theory would need:

whether the games that behave well under addition — the ones with no infinite alternating run in them — can be given canonical forms the way finite games can.

That sentence has a class in it and the class is worth measuring before anything is built on it.

The qualifier does the work #

An infinite run and an infinite alternating run are not the same thing, and the difference is the whole definition.

off is a position where only Left may move, and Left’s move is back to the same position. It runs for ever. It has a cycle. And it has no infinite alternating run, because an alternating run needs Right to move and Right never can — so off is a stopper, despite being as loopy as anything on this anchor.

That is not an edge case. Over all two hundred and fifty-six two-node loopy games, seventy-nine are stoppers and seventy-two of those have a cycle. So the class is not “the loopy games that are secretly finite”; only seven of the seventy-nine are acyclic. It is a genuinely loopy class, picked out by whose turn it is rather than by the shape of the move graph.

It is worth seeing why a game can loop for ever and still have no alternating run, since the two feel like the same thing. Play in off goes: Left moves, Left moves, Left moves. That is an infinite sequence of moves and it is not a run in the sense the theory cares about, because a run is what happens when both players are playing — and the reason the theory cares is that a sum is played with alternating turns. A component in which only one player has anything to do contributes moves to whoever owns them and never forces the play to continue; a component both players can move round for ever does.

The right object to search is therefore not the move graph. It is the graph whose nodes are a position together with whose turn it is — from (position, Left) the edges go to (option, Right) — and a stopper is a game whose turn-graph has no cycle at all. That graph has twice the nodes and quite different cycles, and searching the wrong one is what would put off on the wrong side.

What being a stopper buys #

The point of the class is that the theory should work on it, and the outcome column is the first thing to check.

Every one of the seventy-nine stoppers has a decided outcome — thirty-one Left wins, thirty-one Right wins, fourteen second-player wins, three first-player wins. Not one is a draw. Not one is uncertain.

That is the property the rung below was reaching for, and it is exactly one-directional. It is not necessary: fifty-seven of the games that are not stoppers are decided anyway. So the class of stoppers is strictly smaller than the class the outcome theory copes with, and choosing it costs something.

What it buys in exchange is that the property is checkable from the graph. Deciding whether a loopy game is drawn means running the retrograde analysis; deciding whether it is a stopper means looking for a cycle. The first is the whole theory and the second is a depth-first search.

The fifty-seven decided non-stoppers are worth a moment because they are the price of the choice. They are games in which the players could go round for ever and one of them can do better, so the outcome is decided and the drawn run is available and declined. Any theory built on the stoppers alone will have nothing to say about them, and there are more of them than there are second-player-winning stoppers.

That is the usual shape of a restriction that makes a theory work: it is defined by a property that is easy to check and stronger than the property that is actually needed, and the gap between the two is where the theory is silent about things it could have handled.

Whether they collapse #

A canonical form is worth having when it identifies things: two positions that look different turn out to be the same game, and the form is what they have in common. So the question is whether the stoppers collapse.

They do. Put each stopper in a sum with each of eight named loopy games, record the outcome of every sum, and two stoppers are in the same class when no test tells them apart. The seventy-nine fall into six classes, of sizes thirty-one, twenty-nine, fourteen, two, two and one.

Four of the six are the outcome classes themselves. The other two come from splitting the three first-player wins, so the eight tests separate barely more than the outcome does — which is the caveat that matters. Six is a lower bound on the number of distinct values and not a count. A wider test set could split any of those classes, and thirty-one games in one class is a large class to be confident about on eight tests.

What the number does establish is the direction. Seventy-nine games do not stay seventy-nine; they behave like a handful of values, which is what having canonical forms would mean and what the six rungs below could not say.

The single-member class is the one to notice. One stopper is distinguished from every other by these eight tests, which means at least one of them is doing real work — a test set that separated nothing would give four classes, the outcome classes, and one that separated everything would give seventy-nine. Six is in the interesting middle, and the singleton is the evidence that the middle is real rather than an artefact of two nearly-blind tests.

What the classes look like #

The three large classes are the three ordinary outcomes and their sizes say something about the family.

Thirty-one stoppers are Left wins and thirty-one are Right wins, which is the mirror symmetry the construction guarantees: every game has a mirror with the two players’ edges exchanged, and the mirror of a stopper is a stopper. Fourteen are second-player wins and three are first-player wins.

Three first-player wins in seventy-nine is the number worth pausing on. A first-player win is a position where whoever moves can win, which in a finite game is what star is and is common; among these stoppers it is rare, and it is the class the eight tests split. So the smallest class of the four is the one carrying whatever structure there is beyond the outcome, which is not what a reader would guess and is the natural place for the next test set to be aimed.

The mirror symmetry is also a check the census would fail if the search were wrong. A cycle search that treated the two players differently would break the thirty-one against thirty-one, and it does not.

Why the test set is weak and what a strong one would be #

The eight test games are the named family — on, off, a cycle of three, and so on — and they were chosen because they are the games this site has, not because they separate well.

A strong test set would be the stoppers themselves. Two games are equal exactly when no third game distinguishes them, and the third games that matter are the ones in the same universe; testing the seventy-nine against each other is seventy-nine times seventy-nine sums, each of which is a loopy game on four nodes needing its own retrograde analysis. That is affordable and is not done here, and it is the obvious next measurement.

There is a reason to expect it to split further and a reason to expect it not to. Against: a two-node game is small, and small games have few distinguishable behaviours — the finite games born on day two number twenty-two, so six for a family of this size is not absurd. For: the classes here are very lopsided, and thirty-one games in one class usually means the instrument is blunt rather than the games identical.

The same shape of question turned up on what identifies two subsets, where a construction collapsed 1,793 objects to 96 and the collapse was explained rather than merely counted. The explanation there was domination: the objects that were identified were identified for a reason readable off their shape. Nothing of that kind is available here yet, and finding it would be worth as much as the finer test set — a collapse with a reason is a canonical form and a collapse without one is a table.

What the ladder can now say #

Putting the three measurements together, the class the value theory would need has been located and partly described.

It is definable from the graph — no infinite alternating run — and the definition is a cycle search on the turn-graph rather than anything about values.

It is sufficient for the outcome theory to be definite, on every game in the family, and it is not necessary.

And its members are far from all different. Seventy-nine to six is a large collapse even under a weak test, so there is a small value set here to be found.

That is a different position from where the anchor started. Loopy games introduces positions whose moves lead back to themselves and says the ordinary recursion has nothing to stand on; start at the end and work backwards supplies the retrograde analysis that gets outcomes anyway. Everything since has been outcomes, because a drawn game has no number behind it. What this page adds is that the drawn games are avoidable by a graph condition, and that avoiding them leaves a family small enough to be worth naming.

What is not here is the canonical form itself: a procedure that takes a stopper and returns a reduced representative, the way domination and bypassing do for finite games. That procedure is the actual content of the rung the ladder-top named, and this page is the survey that should come before it — a class, its size, what it buys, and evidence that there is something for a canonical form to be canonical about.

What a canonical form would have to survive #

It is worth setting out what the missing procedure has to cope with, because the obstacle is not the one the anchor has been worrying about.

Domination on a finite game deletes an option when a sibling is at least as good, and the comparison is decided by playing the difference. That works here: the difference of two loopy games is a loopy game, its outcome is computable by the retrograde analysis, and $G \ge H$ when Right cannot win $G - H$ moving first or second. So the test is available and cheap.

What is not obviously available is termination. On a finite game each deletion makes the form strictly smaller and the process stops because there is nowhere further down. On a graph with cycles there is no “further down”: deleting an edge at a node changes what that node is worth, which changes what its own ancestors are worth, which may include itself. The reduction and the thing being reduced are the same object, and nothing about the ordinary argument survives that.

The reduction that reads a graph is the finite version of exactly this difficulty and it terminates for a reason that does not carry over — its graph is acyclic, so a rewriting at a node cannot come back round to itself. A loopy reduction needs a different termination argument or a different reduction, and which of the two is the real content of the rung above.

What is measured #

Two-node games only. Two hundred and fifty-six of them, which is every loopy game on two positions, so the census is complete at that size and says nothing about three. Three nodes is 4,096 games and each cycle search is cheap; it is the sums that are not.

That completeness is worth having and it is also what limits the reading. A two-node game has at most two options a side and every position is one move from every other, so the family cannot contain anything with depth. The proportions here — seventy-nine of two hundred and fifty-six, six classes — are proportions for the smallest possible loopy games, and there is no reason to expect them to hold at three nodes except that the definitions do not mention size.

Eight test games and no more. Stated throughout, because the number six depends on it entirely.

The sums are two-node plus two-node. A sum of two loopy games is a game on the product of their positions, so testing a two-node stopper against a two-node test game is a four-node retrograde analysis. That is why eight tests are affordable and seventy-nine are the obvious next step rather than the one taken.

And “stopper” here is a graph property, not the literature’s definition. The standard definition quantifies over subpositions and this is a cycle search over the turn-graph; on a finite graph the two agree, since an infinite alternating run in a finite game must repeat a (position, turn) pair, which is a cycle. That equivalence is the reason the search is legitimate and it does not survive to infinite graphs.

Why the qualifier is the definition #

No infinite alternating run is a stricter condition than no cycle, and the difference is where every loopy value theory lives.

A cycle is a fact about the position graph and a player can be in one without either player wanting to stay. An alternating run needs both players willing to go round, which is a fact about the outcome of going round rather than about the drawing. So a game can have a cycle and be perfectly well behaved, and the class that admits a value theory is defined by the second condition rather than the first.

Where the ladder goes next #

The loopy anchor has seven rungs: loopy games, working backwards, a draw is not a value, one part that never ends, when never-ending is a win, the one outcome that adds, and now the class a value theory would be about.

The rung above is the reduction. The stoppers collapse and nothing here says how — there is no operation taking a stopper to a smaller stopper worth the same. The two reductions finite games have are domination, which needs comparison, and bypassing, which needs comparison too; comparison of loopy games is decidable by playing the difference and reading its outcome, and every ingredient is therefore in place. Whether the reductions terminate on a graph with cycles in it is the question, and it is the same question the reduction on the shared form answered for finite games with a cycle-free graph.

Two neighbours are worth the trip. Start at the end and work backwards is the retrograde analysis every outcome on this page comes from, and it is the machinery a comparison test would run. And an outcome with no value behind it is the obstruction this class is defined to avoid, worth rereading now that the avoidance has a count attached.