The rule that makes Go a finite game

Go has a rule that reads like housekeeping. A ko is a point where one player captures a stone and the other could immediately capture it straight back, returning the board to exactly where it was; the ko rule forbids that immediate recapture.

Every set of Go rules in use has one. It is usually explained as a device to stop the game going round in circles, which is true and makes it sound like a convenience.

It is not a convenience. It is the hypothesis.

What the rule is doing #

Every value on this site is defined by a recursion on options, and the recursion needs play to end. Allow a position to recur and there is no base case: the definition of a value has nothing to stand on, and a fourth possibility appears that no number represents — neither side can force a win and the game goes on for ever.

Zermelo’s 1913 theorem, which is the subject’s first result, is a statement about finite games and it is exactly as strong as its finiteness hypothesis. Go without a repetition rule does not satisfy that hypothesis. Go with one does.

So the ko rule is the surgery that puts Go inside the class of objects the rest of this site is about, and it is possible to watch the surgery being performed.

The model, stated #

Nothing here plays Go, and being exact about what is modelled is the whole of what makes the essay honest.

A ko fight here is some number of ko points. Each is held by one player. A move captures a point the opponent holds, which flips who holds it. A player with no move loses, by the normal-play convention. That is the entire rule set, and every label below is a retrograde labelling of the graph those rules generate.

Filling a ko — resolving it for good — is switched off in most of the figures, and the reason is a real Go position rather than a modelling convenience: a seki is precisely the situation in which filling loses the group, so the players have the captures and nothing else. That is the case the rule sets are written for.

Three rules and three points #

The interesting question is not whether a rule helps. It is which rule, on how many kos, and the answer is not the one a reader would guess.

With no rule, even one ko point is drawn. The two captures are a two-cycle, and backward induction reaches only the two labels where the holder of the point is to move and has no capture; the two labels that matter — what the fight is worth to the player who can capture — are never set at all. That is the purest possible statement of what a repetition does to the theory: the base case exists, and nothing that anybody wants an answer about can reach it.

The simple rule settles one point and two. For one, obviously; for two, less obviously, because the rule only forbids recapturing the point just taken and a player may take the other one instead. Working the sequence out by hand shows why it still terminates: after each capture the mover has taken the only point available to them, and the alternation runs out.

The two-point case is worth following move by move, because it is the one the table was built expecting to fail and it does not.

Black holds one point and White the other. Black takes White’s; White may not take it straight back, and the other point is now Black’s own, so White has no capture at all and loses. Try it the other way and the same thing happens one move later. The rule that forbids only the immediate recapture is enough here because with two points the players run out of different points to take, and running out is exactly what the theorem needs.

Three points are drawn under the simple rule. Nineteen of the fifty labels never get set. This is the triple ko, and it is the position Go’s own rule sets name explicitly and score as no result — and nothing in the module that produced that number was told about it. It fell out of the move rules.

Superko, and what a stronger rule costs #

The modern rule sets forbid more: no whole-board position may repeat, ever. That is superko, and it settles everything in range.

The price is visible in the picture. Under the simple rule a position is a configuration of the ko points; under superko a position is a configuration and a history. Two points went from nine states to seven, which sounds like a saving and is not — three points go from twenty-five states to eighty-six, and the growth is in the histories rather than in the board.

That is not a modelling artefact. It is what superko does in practice: it makes a Go position depend on the whole game record, so two boards that look identical can be legally different. Players find this counterintuitive and it is the exact price of the finiteness the rule buys.

When filling is available #

Everything above has the fill move switched off, which models a seki. Switching it on is the ordinary case: a player may resolve a ko they hold, taking it out of the game for good.

To see what the fill does on its own it has to be switched on with no repetition rule in force, so that the cycle is still there for it to escape.

So an escape hatch does what retrograde analysis predicts and no more. The propagation now has a base case, and it settles every position from which somebody can reach it — which is exactly the positions of the player holding a ko. It does not settle the other half, because a way out that only one player can take is not a way out of the cycle for the other. That is the same mechanism that makes a loop with a way out settle while a bare loop does not, stated with the qualification the one-point graph forces on it.

For the argument of this essay it is a distraction rather than a help, which is why the survey turns it off. A position in which either player may unilaterally end the repetition is not a test of the repetition rule; it is a test of whether anybody wants to repeat. The interesting case is the one where nobody may end it, and Go supplies that case by name.

Three rules, three games on one graph #

There is a way of stating the whole survey that makes the three rows of the table into three objects the theory already has names for, and it explains the state counts rather than merely reporting them.

Fix the graph whose vertices are the configurations of the ko points and whose edges are the captures. Every rule in the table is a restriction on how a token may walk that graph.

No rule at all is an unrestricted walk. A token moves along edges for ever, revisiting whatever it likes, and the player who cannot move loses — which never happens, because from any configuration somebody can always capture. Every position is drawn, and it is drawn for the reason a walk on a graph with no dead ends never ends.

The simple ko rule is a non-backtracking walk: the one edge forbidden is the one just traversed in the opposite direction. That is a genuine restriction and a very local one — the token remembers a single step. It is enough to strand a walk on a graph whose vertices have degree one after the ban, which is what the one- and two-point cases are, and not enough on a graph where every vertex still has somewhere else to go, which is what the triple ko is.

Superko is a self-avoiding walk: no vertex may be visited twice, ever. And a self-avoiding walk on a graph, played alternately, with the player who cannot move losing, is not a new object. It is Generalized Geography — the game this site uses to show what quantifier alternation costs, drawn on a different graph.

Why superko explodes, and what it explains #

That identification does the explaining the state counts were left needing.

A superko position is not a configuration. It is a path: where the token is, plus every vertex it has already used. So the reachable states are the self-avoiding paths of the configuration graph, and self-avoiding paths are the classic object that outgrows the graph it lives on. Two points went from nine states to seven and three points from twenty-five to eighty-six, and the reason the second number goes the other way is that paths multiply where configurations do not.

It also explains why players find superko counterintuitive in exactly the way they do. The complaint is always that two identical boards can be legally different, and under this reading that is not a quirk of the rule — it is what a self-avoiding walk is. The token’s position is not the state; the state is the trail behind it.

And it says something about the hardness results the last section gestures at. Generalized Geography is the standard PSPACE-complete game, and the reduction this site draws from quantified boolean formulas lands in it. So the rule that makes Go finite is the rule that turns a ko fight into an instance of the canonical hard game — the finiteness and the difficulty arrive together, from the same clause, and there is no version of this trade in which a rule buys termination for nothing.

That is a sharper form of the essay’s own conclusion. The section below says the three rules give three different answers and would agree if the rule were housekeeping. The stronger statement is that the three rules give three different games, each of which the literature has studied on its own terms, and the ko rule is the choice of which one is being played.

A rule that changes the answer is a rule about the graph #

Here is the thing worth carrying away, and it generalises well past Go.

The ko rule looks like a rule about stones. It is a rule about the position graph: it deletes edges. Chess’s threefold repetition rule and its fifty-move rule do the same job by different means — one deletes edges, the other adds a decreasing counter to the state — and both exist for the same reason and neither is usually described that way.

What that buys is stated once and applies to every row of the survey. Backward induction on a graph with no cycles settles every position in a finite number of rounds and then runs out of work with nothing left over; a single reachable cycle anywhere is enough to leave a region it never gets to, and the region is what the drawn labels are. Deleting edges until no cycle remains is therefore not a way of making the analysis easier. It is the whole of what makes there be an analysis.

The general shape: termination is a property of the graph, not of the game’s flavour, and rules that enforce it are doing mathematics rather than good manners. The clearest evidence is that the three rules above give three different answers to the same fight. If the rule were housekeeping the answers would agree.

It also has a cost that shows up in the complexity field rather than here. Superko makes the state depend on the history, so a solver’s table is keyed on something that grows with the length of the game rather than with the size of the board — which is why what “solved” means is a harder question for Go than for games with no repetition rule at all, and why the hardness results for Go are stated separately for each rule set.

What a drawn label means on a real board #

A drawn position is not a technicality either, and Go’s own scoring says so.

Under the simple ko rule a triple ko is no result: the game is annulled and, in some tournament rules, replayed. That is exactly the fourth outcome class — neither player can force a win — appearing on a board in a real tournament, and it is the same object a draw that is not a value is about.

A finite game under normal play has four outcome classes and no more: the first player wins, the second player wins, Left wins whoever starts, Right wins whoever starts. Four is not a convention — it is what the backward induction can produce, since every position is labelled for each player to move and each label is a win or a loss. A drawn position is a fifth thing and it is not in that list, because it is the case where the induction produced no label at all. It exists only once the finiteness hypothesis has been dropped, which is the whole of what a repetition rule is there to prevent.

The famous story about this is that a triple ko once annulled a game with political consequences; the story is repeated more often than it is checked, and this essay makes no claim about it. What can be checked is the mathematics, and the mathematics says the position class exists, has no value, and is removed by the stronger rule.

The surprise: the rule was found by playing #

The chronology is the part of this that is genuinely startling.

Go’s ko rule is old — older than any of the mathematics, by a margin measured in centuries rather than decades. Nobody who wrote it down had a theorem about finite position graphs, or backward induction, or outcome classes. What they had was a game that would not end, and a prohibition that made it end.

And the prohibition they arrived at is not the obvious one. The obvious rule is no position may ever repeat, which is superko, and which the table above shows settles everything. What Go actually adopted first is the weaker rule — forbid only the immediate recapture — which settles one ko and two and leaves three drawn. That is a rule with a hole in it, and the hole has a name, appears in tournament regulations, and is scored as no result rather than being ruled out.

So the empirical rule is strictly weaker than the mathematical one, and the gap between them is a real position class that real players reach. It took a very long time for anybody to close the gap, and closing it is what the modern rule sets do.

The reading this site would give: the players found the cheapest rule that fixed the problem they were actually having, and the cheapness is visible in the state counts. The simple rule keeps a position a property of the board; superko makes it a property of the record. Nobody adopts the second until the first is seen to fail, and the first fails only on a position that occurs rarely enough to be famous when it does.

That is a general shape and not a fact about Go. A rule adopted to fix a nuisance is tuned to the nuisance, and whether it also settles the mathematics is a separate question that somebody has to ask afterwards.

What the picture cannot show #

The figures here draw ko points and nothing else, and a real ko fight is not fought that way.

What is missing is the ko threat: a move elsewhere on the board that forces an answer, buying the time to come back and recapture. Ko threats are what make ko fights interesting, they connect the ko to every other part of the board, and they are precisely the thing this model has thrown away by drawing the fight in isolation.

The consequence is that the model gets the rules right and the play wrong. Whether a real ko is worth fighting depends on how many threats each side has, which is a property of the whole board and a quantity no figure here computes. What survives the simplification is the question the essay is actually about — whether the position graph has a cycle in it — because that question does not depend on what is happening elsewhere.

The other thing not shown: this model has no notion of territory. Go is scored, and a scoring game is a different object from the normal-play games this site is built on. The ko rule is one of the few pieces of Go that can be studied without confronting that, because it is a question about which positions exist rather than about what they are worth.

The convention, named #

The model here uses normal play: a player with no capture available loses.

Real Go does not work that way — a player with no useful move passes, and two passes end the game, after which the territory is counted. Substituting normal play is a genuine change and it is the reason the essay’s claims are about the graph rather than about who wins a Go game.

What survives the substitution is exactly the finiteness question, because whether a graph has a reachable cycle does not depend on the winning condition. That is why the figures above report drawn labels rather than values: a drawn label says the propagation stopped, and the propagation stopping is a fact about the edges.

Where the ladder goes next #

go opens here with the rule that makes the rest of the field possible, and there are two obvious rungs above it.

The first is the endgame, where Go’s own accounting and this site’s temperature theory meet — and where the theory told somebody something for the first time, on a position small enough to check completely.

The second is the harder one: what happens to all of it once the score is what matters. That is the next essay but one, and its answer is not encouraging.