Combinatorial Game Theory
who wins, and by how much
Concept

Go — where it appears

A territorial board game whose endgame was the first thing the temperature theory was tested on, and whose repetition rule makes it finite. Its endgame is a sum of independent regions, which is the situation the whole temperature theory was designed for.

Named by 13 essays across 4 fields — each of them below, with the objects they name alongside it.

1 ko point, no ko rule. A ko fight drawn as a position graph and labelled by retrograde analysis: blue edges are Black's captures, red are White's, and each position carries the verdict for whichever side is to move. Positions the propagation never reaches are drawn — neither player can force a win and the game does not end — and they appear only where the rules permit a repetition.

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 games every theorem on this site is about, and removing it removes the values.

applied · Go A game where the last move decides nothing. Rows of coins taken from either end, with the exact score for each side moving first. Under the normal-play convention this family is settled entirely by the parity of the row — nobody is ever without a move until the coins run out — so normal-play theory returns the same answer for every row and it is not the answer anybody wants. The scoring answer depends on nothing but the numbers.

Counting at the end changes everything

Go is scored. So are Dots and Boxes, chess and almost everything anybody plays for money — and none of them is the kind of game this site's whole apparatus is built for. The simplest scoring game there is shows what that costs — the normal-play theory gives every position of it the same answer, and the answer is useless.

applied · Scoring Is {{5 | 3} | {2 | −4}} double sente?. One local fight with a follow-up on each side, played out inside a sum with a switch whose temperature rises. The two middle columns are what optimal play does when each player opens the fight. Whether the opponent has to answer is settled by the ambient temperature and not by the shape, so the same position is double sente, sente for one player, and gote for both, at three different ambients.

Double sente is not a property of the position

A fight with a threat on each side is called double sente, as though the phrase named a shape. Swept against a rising ambient temperature, one such fight — { {5 | 3} | {2 | −4}} — is double sente up to an ambient of 1, sente for one player only from 3/2 to 3, and gote for both from 7/2, and the two band edges are the temperatures of the two follow-ups.

temperature · Sente a loop with a way out under three rules for never ending. One graph, one labelling, and three ways of reading the residue the labelling never reaches. A draw is not a computed outcome here — it is what is left over — so declaring infinite play a win for one side is a legal alternative that costs no extra search and changes who wins.

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.

limits · Loopy Every empty NoGo board a build can solve. The empty boards, with the value the recursion returns and the outcome that follows from it. The one-row boards run 0, star, switch and repeat, which is a pattern with no reason behind it that survives past six squares.

Every group must keep breathing

NoGo is Go with no captures at all: a stone may be placed only if, afterwards, every group on the board still has a liberty. That makes a move's legality a fact about the whole board rather than about the squares it occupies — and a board therefore almost never breaks into independent parts. Of 117 boards here whose empty points fall into two regions, 24 are the sum of their regions and 93 are not.

positions · Nogo When the regions add. Every board in the independence census — 117 positions whose empty points fall into two or more regions — tested against a stated criterion and against the guess it replaces. The criterion is that no stone group has liberties in two different regions, which makes a move in one region unable to change what is legal in another. It holds on 9 boards and the regions add on every one of them.

When the regions add

The rung below described the NoGo boards whose regions add as the ones with symmetric walls, and said the description was a guess made from six examples. It is wrong: fourteen symmetric boards do not add and sixteen that add are not symmetric. What replaces it is a criterion about liberties — sound on all 117 boards, provable in a line, and complete on only nine of the twenty-four.

positions · Nogo Thickness is not the variable; the wall's own groups are. The same strips split by whether the wall is all one colour. A wall of one colour is a single group with liberties on both sides and it never separates them, at any thickness. A wall of two colours is two groups breathing in opposite directions and it nearly always does.

How thick a wall has to be

A single stone between two empty stretches of a NoGo board couples them, and the obvious repair is a thicker wall. Over 590 walled strips a thicker wall does help — and splitting the same 590 by the colour of the stones shows that thickness was never the variable. A wall of four one colour couples the sides exactly as one stone does.

positions · Nogo Two feet, and the one that halves the crossover. The thermographs of two follow-ups, drawn to the same scale. The first has a right wall that leans in from the axis and its move is answered up to the follow-up's full temperature; the second has a wall rising vertically first and its move is answered only to half of it.

What the halving is a function of

A move is answered while the board is cooler than the follow-up's temperature — or half of it, depending which of two classes the position is in, and the classes were stated in terms of forms. They are a feature of one wall: whether the follow-up's right wall rises straight up before it leans. Fifty-five positions, no exception, and the crossover becomes something a reader can see.

temperature · Sente When the players stop taking coupons. Every pair of fights from a pool of nine, played beside a coupon stack, with the coupon standing when somebody first plays on the board. Sixty of the eighty-one leave exactly when the coupon falls to the board's temperature.

When to leave the environment

A Go player's question is not which fight to take but when to stop taking the small stuff. Put two fights beside a stack of coupons and the orthodox answer — leave when the coupon falls to the hottest temperature on the board — is exact on sixty of eighty-one pairs. All twenty-one departures have a fight with a follow-up in them, and every pair of plain switches leaves on time.

temperature · Coupons A criterion that does not lift. The NoGo separation criterion run on strips and on three-row boards. On strips it holds on nine boards and explains all nine independent ones. On 227 three-row boards it holds on none at all.

A wall that bends

On a NoGo strip, two empty stretches add when no group breathes into both — a wall of two stones of different colours does it, and the criterion explains nine of ninety-three boards and all nine that it covers. On a three-row board it explains none of 227, and not because it is less accurate. A wall across a board has to bend, a stone at the bend sees empty squares on both sides by itself, and every one of the 227 has a group breathing into both regions. The condition is unsatisfiable.

positions · Nogo A ko fight decided somewhere else on the board. A ko fight against the number of ko threats each side holds. A threat is a play elsewhere that the opponent must answer, and it lifts the prohibition on recapturing, so a player short of threats runs out of ways to come back. Every cell is a full retrograde labelling and the pattern in them is read off afterwards: the fight goes to whoever is ahead on a quantity that is not on this part of the board at all. Where the labelling never settles, the fight is a no-result whatever anybody holds.

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.

applied · Go Where the two conventions come apart, counted. Every small Go endgame solved under both scoring conventions. The scores agree exactly when the number of neutral points is even and never when it is odd, which is the parity of the stones each side ends up placing. A counted fraction name different winners. And a smaller fraction are played differently, which is the half of the finding a rules argument does not predict: a neutral point is a one-point play under one convention and worth nothing under the other, so the two rule sets disagree about the order of the endgame and not only about its total.

Two ways to count a finished board

Territory scoring and area scoring are both in daily use and they are not variants of one rule. Over seventy-nine small endgames they agree exactly on the thirty-nine with an even number of neutral points and on none of the forty with an odd number — sixteen name a different winner, and twelve are played differently, which is not something a convention is supposed to do.

applied · Go What a pass buys, and what it costs. Rows of coins solved with and without a pass. Milnor's mean-value theory needs a non-negative incentive to move, and rows containing a coin nobody wants break that condition — a player forced to take is a player who would rather have passed. Allow a pass and the condition is not merely satisfied but unbreakable, on every row in range. The price is that a player who may pass is never stuck, so the last-move convention has nothing to attach to and the game needs a separate rule to end at all.

What a pass is worth to a theory

The rung below finds fifteen of twenty-seven coin rows where having the move is a disadvantage, and those are exactly the rows Milnor's mean-value theory has to assume away. Allow a pass and the hypothesis stops being a hypothesis — nought violations, on every row in range. What it costs is the convention the rest of this site is built on.

applied · Scoring

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchCounterexampleNormal playTemperatureDecompositionIndependenceOutcome classAdditivityDisjunctive sumEnumerationMean valueRegion

All concepts