One part that never ends

Every game has a negative, and the proof is one sentence: swap the two players’ roles all the way down the tree, put the two copies side by side, and answer every move in one with its mirror in the other. The copier always has a reply, so the copier moves last, so the sum is a second-player win — worth exactly zero.

That sentence has a hidden clause. The copier moves last is only a win if there is a last move.

What on is #

on is the smallest game that never ends: one position, and from it each player has exactly one move, back to the same position.

Neither player can ever be stuck, so neither can lose by the normal-play rule. Play continues for ever. The backward analysis that replaces the recursion starts at positions where somebody has run out of moves, and there are none, so it never starts.

off is its mirror: Left may move, back to the same position; Right may not move at all. Right is stuck immediately, so Right loses whoever starts, and the analysis settles it in one round — a loopy game with a completely decided outcome, which is worth knowing before anything else here.

The general situation is a position graph with a cycle in it: play leaves a position and is back at it a move or two later, so the recursion every value on this site rests on has no base case, and an outcome beyond win and loss appears. Normal-play theory has no name for it, and every figure here draws it as a blank rather than as a symbol.

on absorbs everything #

Add a component to on and the answer does not change.

on + ∗ is drawn. on + 1 is drawn. on + off is drawn. on plus a loop with a way out is drawn, and on plus a three-cycle is drawn. Every sum computed here leaves every position-and-mover pair unsettled.

Those two components are short: they end, they have values, and each is worth something a reader can name. The case worth checking separately is the one where the second component never ends either, since that is the case with a reason to behave differently.

The mechanism is immediate once stated: nobody is ever stuck, because on always offers a move. Losing under normal play means having no move, and a component that always has one makes that impossible for both players at once.

So on is an absorbing element for the disjunctive sum, in the way zero is absorbing for multiplication. That is not something any short game can do: adding a short game to another changes the answer according to the values, and there is no short game whose presence fixes the outcome regardless of what it is added to.

off does not absorb #

The mirror image behaves quite differently, and the asymmetry is the interesting part.

off + ∗, off + 1 and off + off are all settled with no draws at all. The reason is that off gives Right no move: Right runs out immediately, and running out is what losing means.

But off does not fix the answer either, and the component that breaks it is the one just used to show on absorbing.

The two figures above it are the same component added to two different things, and the answers are the same and the reasons are not. Beside on the cycle is redundant: both players were already inexhaustible. Beside off it is decisive: it supplies the one player who had nothing.

So there are three behaviours rather than two: a component where both players always have a move absorbs everything; a component where one player is stuck is decided until something else gives that player a move; and a short component contributes its value in the ordinary way.

Three behaviours, which are really four #

The three behaviours listed above are three of a set of four, and completing the set turns a list into a classification with a criterion attached.

Call a component inexhaustible for a player when that player has a move in it at every position it can reach. Two independent yes-or-no questions, so four cases:

The essay’s three are this table with the two middle rows collapsed, and separating them is what makes the next step available.

And the criterion composes #

The useful part is that inexhaustibility is a property of a sum and it is read off the components by a disjunction.

Left is never stuck in $G + H$ exactly when Left is never stuck in $G$ or never stuck in $H$ — one component that keeps offering a move is enough, whatever the other does. Same for Right, independently.

So the sum’s row in the table is the componentwise or of the parts’ rows, and the outcome follows:

A sum is drawn throughout exactly when both players have an inexhaustible component in it.

Check it against every figure on this page. on + ∗: on is inexhaustible for both, so both boxes are ticked and the sum is drawn — which is what the labelling found. off + ∗: Left is covered by off, Right by nothing, so Right runs out and Left wins. off + off: same again. off plus a three-cycle: the three-cycle is inexhaustible for both, so Right is covered after all and the sum is drawn — which is the case the essay singles out as surprising and which the criterion predicts.

That makes on’s absorbing power a special case rather than a phenomenon. on absorbs because its row is yes, yes, and an or with yes is yes — so adding it ticks both boxes whatever the other components do. Nothing about on is doing the absorbing; the disjunction is.

Which is a rare thing to find here #

It is worth saying what kind of statement that is, because outcome-level statements about sums are almost always negative on this site.

Outcomes do not add: two first-player wins can sum to anything, and the loopy table is worse still, with eleven of its twenty-eight cells holding several answers. Against that, here is a property of components that determines a property of the sum, by an operation as cheap as or.

The reason it composes when outcomes do not is that it is not an outcome. It is a statement about move supply, and move supply is the one thing a disjunctive sum genuinely pools — a player’s moves in a sum are the union of their moves in the parts, so anything defined by “does this player have a move” is a union of the same shape.

That also says the limit of it. The criterion decides drawn throughout and nothing finer: two sums that both fail it are both decided, and which player wins is not something a disjunction of two bits can say. What composes is exactly the coarsest question, and the finer ones need the product graph the next section builds.

How a sum of two graphs is built #

The figures in this essay are computed rather than drawn by hand, and the construction is worth a paragraph because it is the ordinary disjunctive sum with nothing special about it.

A position of G + H is a pair: a position of G and a position of H. Left’s moves from the pair are Left’s moves in the first component, keeping the second, together with Left’s moves in the second, keeping the first. Right’s likewise. That is the definition of the sum, written as a graph rather than as a recursion.

So the sum of a one-node game and a two-node game has two nodes; two three-node games give nine. The graph grows as the product, which is the same explosion decomposition exists to avoid — except that here it cannot be avoided, because there are no values to add instead.

Then retrograde analysis runs on the product with no knowledge that it was built from two things. It starts at pairs where the mover has no move at all, works outward, and stops. Nothing in the procedure is told which component anything came from, which is what makes the results evidence rather than restatement: the drawn positions are drawn because the labelling could not reach them, not because a rule about on was applied.

That is the honest cost of losing values. Under the short theory, a sum of two positions is settled by adding two small objects; here it is settled by building the product graph and labelling all of it.

Why the mirror strategy fails #

Go back to the theorem at the top, and watch it break.

off is exactly −on: the two are the same graph with the players exchanged, which is the definition of the negative. So on + off is G + (−G) for G = on, and the mirror strategy applies verbatim: whatever one player does in one copy, the other answers in the other.

The strategy works. The copier always has a reply, every move is answered, and the game never finishes. The copier does not move last, because there is no last move, and the conclusion the strategy was for does not follow.

This is one of two ways the group law fails on this site, and the pair is worth holding together. Here the mirror strategy is unbeatable and the game never stops. Under misère play the game stops and the mirror strategy loses, because the player who always has an answer is the player left making the last move.

Same strategy, two different clauses of the same theorem, two different failures.

What survives #

Loopy game theory is a working subject, and it is worth saying what replaces what.

Outcomes survive, with a fifth class. Every position is a win for Left, a win for Right, a first-player win, a second-player win — or drawn. An outcome with no value behind it is the essay about that fifth class.

Values do not survive in general. There is a theory of loopy values — on, off, over, under, dud — and it is a separate apparatus rather than an extension of this one. Nothing in it is a number.

Additivity is worse than it was. Under normal play the outcome of a sum is not determined by the outcomes of its parts, which is why values were needed. Here the parts’ outcomes fail to determine the sum and the values that fixed it are unavailable.

And the analysis still answers the question asked of it. Retrograde labelling settles every position it can and leaves the rest blank, which is a complete and honest answer: the blanks are the draws, by definition rather than by test.

A mixed board #

The most instructive case is neither wholly drawn nor wholly settled.

That figure is why the loopy theory needs graphs rather than values. The answer for this board is not a property of the two components taken separately; it depends on which positions of the product are reachable from which, and the labelling is the only thing that knows.

The four classes the short theory guarantees are the contrast worth holding beside it. Every short position is a win for Left, a win for Right, a first-player win or a second-player win; the classification is exhaustive, and it is exhaustive precisely because play stops — which is the condition the games in this essay do not satisfy. Take the condition away and a fifth answer appears, and the fifth answer is the absence of the other four rather than another of their kind.

What a player can still be told #

An essay about a theory failing should say what advice survives, and there is some.

A component where both players always have a move is a shelter. A player who is losing everywhere else can take refuge in it: the game never ends, nobody runs out, and the loss never arrives. That is precisely what “drawn” means from the losing side, and it is why chess players in trouble look for perpetual check.

A component where only the opponent is stuck is a win, and it stays one. off keeps its verdict against a star, a point, or another off — anything that does not hand Right a move.

And a shelter beats a lead. on + 1 is drawn, so a free point does not convert. That is the practical content of absorption: material means nothing in a game that never reaches a count.

Those three sentences are the whole of the strategic advice, and it is worth noticing how much smaller they are than what the short theory gives. There, a player has values, sums, comparisons and a move rule with a bound attached. Here there is a three-line summary of who can hide where — which is the honest measure of what a component that never ends costs.

Where the model stops #

Five graphs is not a theorem. on absorbing everything is checked here on sums with a star, a point, off, a three-cycle and a loop with an exit. That it absorbs every game is the general statement, and its proof is the one-line argument about nobody being stuck rather than the sweep.

The sums are drawn as product graphs. A sum of two loopy games is built by taking a position of each, which is the ordinary disjunctive sum, and the graph grows as the product of the two. Two components of three positions each give nine, and a real board would be far past drawing.

And the loopy values are not developed here. on, off and dud have a theory with an ordering and an arithmetic, and this essay uses only the graphs. The theory is a genuine one and it is a different subject with different machinery — everything above is about what happens to this subject’s machinery when a component never ends.

Where a real game meets this #

The graphs here are as small as they can be, and the situation they model is one that turns up in every game people actually play.

Go forbids it outright. A ko is a capture that can be recaptured for ever, and the ko rule exists to make the position graph acyclic — which is the surgery that makes Zermelo’s theorem apply rather than a matter of etiquette. Without it, a Go position with three kos is drawn in exactly the sense this essay means.

Chess allows it and scores it as a draw. Perpetual check is on embedded in a larger game: a component neither player can leave, entered by the losing side to prevent the game from ending.

Card and board games with a “pass” are the same phenomenon in a milder form. A rule that lets a player decline to move removes the losing condition and, with it, the termination argument.

The common shape is that the designers of every one of these games had to make a decision about infinite play, and every decision is a choice among the same three: forbid it, score it, or let the game not end. This subject takes the second, calls the result a draw, and then finds that its whole apparatus was built on the first.

What the picture cannot show #

A blank in a retrograde figure means “never settled”, and blankness is the least visible thing a diagram can contain.

That is not a drafting failure; it is the definition. A draw is the complement of what the analysis reached, so the only honest way to draw it is as an absence, and an absence looks like an oversight. Every one of these figures prints the count of unsettled pairs beside the graph for exactly that reason.

The other invisible thing is the infinite play itself. on is drawn as one node with a loop, and the loop is a picture of a move; the infinite sequence of moves that makes the game drawn is not on the page and cannot be. A reader has to supply the repetition, which is the one act of imagination this collection routinely asks for.

The two failures, side by side #

This site now has two essays about G + (−G) not being zero, and setting them together is the clearest statement of what the group law actually needs.

Under misère play the game ends, the mirror strategy answers every move, and the answerer is the player left making the last one — which loses. So the sum is a first-player win, computed for every game in a pool and never a second-player one.

Under loopy play the mirror strategy answers every move and there is no last move at all. So the sum is drawn.

The theorem it breaks is the same theorem, and the clause it breaks is different each time. The copier moves last and therefore wins has two hypotheses: that there is a last move, and that making it is a win. Loopy play removes the first, misère play removes the second.

That is a good way to read any theorem in this subject. The hypotheses are usually invisible — nobody writes “assuming play stops” in front of a one-line strategy argument — and the way to find them is to look at the conventions two neighbouring theories change.

The convention, named #

Normal play, and one convention that is doing all the work.

A player who cannot move loses, and a game that never ends is a draw. The second half is a convention rather than a consequence: it would be perfectly consistent to declare infinite play a win for one side, and some games do — chess scores it as a draw, Go’s superko rule forbids it outright, and the rule that makes Go finite is the essay about paying to avoid the case entirely.

The other convention is that the sum is disjunctive: a move is a move in exactly one component. Under a compound where a player must move in every component at once, a component that never ends would end the game the moment any other did — a completely different answer, from the same two graphs.