Loopy — where it appears
Named by 31 essays across 7 fields — each of them below, with the objects they name alongside it.
The first theorem, and the winner it declines to name
Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.
Who moves last
The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it.
Loopy games
The whole theory assumes play stops. Allow a position to recur and the induction that every value rests on has nothing to stand on — and a fifth outcome appears that normal-play theory has no name for.
The rule that makes Go a finite game
A ko is a point in Go where a capture can be recaptured for ever, and every set of rules forbids it. That prohibition is not etiquette or tidiness — it is the hypothesis that puts Go inside the class of finite games that the theory of values is about, and removing it removes the values.
Start at the end and work backwards
When play can return to where it started there is no bottom for the recursion to stand on. What replaces it begins at the positions where somebody has already lost and propagates outwards — and the positions it never reaches are exactly the draws. There is no test for a draw, and there does not need to be.
An outcome with no value behind it
Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches.
The condition the recursion rests on
Not that the moves run out, and not that the options are few. Poker Nim's heaps can grow without bound and it ends; the game called `on` has one option and never does. What every game value needs is that no infinite run of moves exists — and there are three separate ways to fail it.
One part that never ends
The game called `on` has one move and it is back to itself. Add anything to it — a star, a point, its own mirror image — and the whole board is drawn. So `off` is exactly the negative of `on` and their sum is not zero, which is the group law failing for a reason that has nothing to do with who is winning.
The class is named after memory, and that is not an accident
A 4×4 Domineering board has 6,257,129 routes through it, 5,700 distinct positions, and a deepest line eight moves long. Those three numbers are three different resources, and the smallest of them is the one that gives games their complexity class.
When never ending is a win
Retrograde analysis labels a position a win when somebody can force the opponent to be stuck, and leaves everything else blank. Calling the blanks draws is a rule from outside the game — and two other rules are available. The labelling does not change under any of them; only the residue does, and on a three-cycle that residue is every position on the board.
The one outcome that adds
Finite outcomes do not add: two first-player wins can sum to anything. Loopy play has seven outcome classes instead of four and adds even less — of the 28 cells in the table, eleven hold several answers. Two do not, and they are the two worth having: a second-player win added to anything leaves the outcome alone, and a draw added to a draw is a draw. A draw added to anything else is not.
Amazons on one line
A board one square high is small enough to evaluate completely: every strip from two to ten squares with one amazon a side is 37,886 positions taking 81 distinct values, and every one of them is an integer, a switch, a number plus a star, or a bare star. Not one is a fraction — and forcing the arrow onto the square just vacated, which takes a freedom away rather than adding one, produces 1,196 that are.
What can be struck out
From G + X = H + X it follows that G = H, in one line, by adding −X to both sides. It is the shortest theorem here and the most used: it is what makes comparing two boards region by region legitimate. Over 10,648 triples the hypothesis fires 484 times and the conclusion holds 484 times — and the licence expires in three separate directions, each of which loses the same axiom in a different way.
A stopper and how to find one
The class a value theory for loopy games would need is the ones with no infinite alternating run, and the qualifier does the work: seventy-nine of the two hundred and fifty-six two-node loopy games qualify and seventy-two of them have a cycle. Every one has a decided outcome, and under eight tests the seventy-nine collapse to six.
A position with no value, and the rule that gives it one
A fortress is a cycle in the position graph, so the recursion defining a value has nowhere to bottom out and the propagation never reaches it. Chess has a rule for that — count fifty moves and call it drawn — and the rule does not merely tidy the theory up. On eleven cells of the sweep it takes away a win.
A ko is won somewhere else
The rung below shows the ko rule buying finiteness by deleting one edge. What it buys with the same edge is a fight nobody can settle by looking at it — the prohibition forces a player to spend a threat, threats are counted on the rest of the board, and every decided cell of the sweep goes to whoever is ahead on a quantity that is not in the picture.
The gap between two answers
A draw is usually described as what the backward labelling never reached, which makes it sound like a shortfall of the algorithm. Written as one predicate the winning condition is an equation, the equation is monotone, and it has a least solution and a greatest one — and the set the two disagree about is exactly the drawn set, on every game checked.
What the play keeps coming back to
A draw is what the backward labelling never reaches, and handing every never-ending play to one player turns the draws into wins wholesale. Judge an infinite play instead by what it keeps returning to, and every draw gets a winner of its own: over the 262,144 three-node games, 15,432 send some of their draws to one player and some to the other, which no wholesale rule can do. Finding those winners takes a fixed point inside a fixed point.
One bit of memory
Judge an infinite play by whether one position keeps recurring and every winner can play from a table of one move per position, with nothing remembered. Ask for two positions to keep recurring and that stops being true. At a hub with two spokes a player has to alternate, and a table cannot alternate: over every three-node game, 49,487 position-and-mover pairs are won with one bit of memory and lost without it.
The rule decides who has to remember
Whether a winner needs memory is a property of the winning condition and not of the board, and the property everybody reaches for is the wrong one. Of the 128 conditions on which of three positions a play keeps returning to, 32 demand memory and 19 of those are closed under union. What separates them is measured two independent ways and the two agree on all 128: a condition needs no memory exactly when it can be rewritten as a number on each position.
Two things to hold at once, or three
Whether a condition makes a winner remember has been settled over every condition on three positions; how much it makes them remember has not. A tree built out of the condition alone, with no board in it anywhere, prices all 128: sixty-one cost nothing, fifty-eight cost two states and nine cost three. It also names the property that was nearly right — closure under union of the sets a condition rejects decides it exactly, where being writable as numbers is sufficient and reaches twenty-six.
Four positions, sampled
Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.
Each size is built from the last
At three positions the sides that needed new names were sums of nothing older: no pair of stoppers, and no two-position stopper with a small game beside it, wrote any of them. At four positions the thirteen names three positions forced are available as parts, and they change the answer. Of the fifty sides the samples met that nothing earlier names, twenty-three are sums of two earlier games — fifteen of them using a three-position name — and twenty-seven are not.
Composition at every size
Twenty-seven of the fifty new four-position sides were written by no sum of two earlier games. Sums of three write sixteen of them — seven plain finite games born after day two, nine built on the names three positions forced — and leave eleven, met seventeen times in nine thousand regions. Run the same test one size down and the story the counts told falls apart: eight of the thirteen names three positions were thought to invent are sums of up to three older parts, two of them just two finite values. Every size composes. What each invents is a residue — five, then eleven.
The same rule on a star
Kōnane turned out to hold the theory's whole vocabulary, and one old game is an anecdote. Mū tōrere, a Māori game on an eight-pointed star, has the same rule for losing — a player who cannot move loses — and is small enough to solve whole. Of its 630 arrangements, not one is a win for whoever moves first or a loss for whoever must move, sixteen go to each side whoever starts, and most are drawn. A random player still loses it every time. The vocabulary was never in the rule for losing; it was in the captures.
The solution that was a losing set
In 1944 von Neumann and Morgenstern defined the solution of a game by two conditions on a set of outcomes: none overrules another, and each outcome outside is overruled by one inside. They were writing about coalitions. The same two conditions, read with a move in place of an overruling, describe exactly the lost positions of a game that must end. Where play can loop, the same definition gives several answers or none, and three positions are enough to show both.
What a stable set knows about a draw
On a graph with cycles, outcome labelling calls a position lost, won or drawn, and stops. The stable sets go further in exactly one place. On every game of up to five positions they hold every lost position, no won one, and among the drawn positions are exactly the stable sets of the drawn part taken alone. So a stable set is a certificate that the player who keeps returning to it never gets stuck. It can distinguish draws that labelling cannot, and two parts with no stable set can have one between them.
A win is not a way of winning
Solve a lone king against a rook completely and every one of 175,168 positions with white to move is won. Now let white play any move the table says keeps the win, and black resist as long as it can: in 400 games of up to 2,000 moves, white never mates. On a graph that loops, staying won is not progress. From every won position in the queen and rook endings white can stay inside the won set for ever, and what wins is a second number, the distance, which the theory of finite games never had to ask for.
A rule that let the game run for ever
In 1929 German chess drew a game when the same sequence of moves came three times running, and the rule was meant to make chess finite. Max Euwe, six years from the world title and trained as a mathematician, showed that it does not, using a word that had already been found twice for other reasons. Two round trips are enough. The board returns to one position thousands of times, no block of play ever comes three times running, and the rule has nothing to say.
What counting positions buys
A rule that counts arrivals at a position ends every game, which the rule of 1929 could not do, and it needs no proof beyond arithmetic: with L arrivals barred on n positions, no game is longer than (L − 1)n − 1 moves. What it does not do is change a single result. Over every game on three and four positions and a sample on five, drawing on the second arrival or the third gives exactly the labels retrograde analysis had before any rule was written. The rule pays for the game's ending and for nothing else.
The number in the rule
Draw on a repeated position and no result moves. Refuse the move instead, as Go does, and nothing is left drawn: over every game on four positions, 10,324 of 16,384 starts are drawn with no rule and every one of them acquires a winner. Which winner depends on the number written into the rule. Bar the third arrival rather than the second and 1,392 of those starts change hands. A question with a linear answer has become one that needs the history, and the extra difficulty lies entirely in the positions the labelling called drawn.
Named alongside it
The objects these essays reach for when they reach for this one.
DrawExhaustive searchRetrograde analysisOutcome classPosition graphTerminationDeterminacyDisjunctive sumFixed pointNormal playOn, the game that never stopsStrategy