Every group must keep breathing

NoGo is played on a Go board and nothing is ever captured. Players alternately place a stone of their own colour on an empty point, and a placement is illegal if, afterwards, any group of either colour has no liberty. The game ends when the player to move has no legal placement, and under normal play that player has lost.

The rule is one sentence and it does something none of the other board games on this site does. In Domineering a move is legal or not by looking at the two squares it covers. In Clobber, at the piece and its neighbour. In Cutcake, at the line being cut. Here a placement can be made illegal by stones it does not touch: filling in the last liberty of a group at the far end of the board is forbidden, and whether it is the last depends on everything in between.

That has a direct consequence for the one technique the whole of this site is built on.

The empty boards #

The first thing to ask of a new ruleset is what its empty boards are worth, and the answer is short enough to print.

The one-row column is the striking one. A row of one is worth $0$; a row of two is $\ast$; a row of three is $\{1 \mid -1\}$; and then $0$, $\ast$, $\{1 \mid -1\}$ again. Three values, period three, no exceptions.

At seven squares it breaks. The row of seven is worth $\{1\!\ast \mid -1\!\ast\}$ — close to the switch the pattern predicts, and not it — and the row of eight is $\ast$ rather than the $0$ the pattern predicts. Two rows into the second cycle the pattern is gone.

That is a specimen of the trap a period is a proof is about, seen from the wrong side. A repetition over two full cycles is exactly the evidence a periodicity claim needs when the game is one whose periodicity theorem applies, and NoGo is not one: it is partizan, its values are not Grundy values, and there is no theorem here saying that a repeated block must continue. Six terms of a three-cycle in a partizan board game is a coincidence, and the seventh says so.

The rule that consults everything #

The real content of the ruleset is what happens when the board has stones on it.

A group’s liberties are the empty points adjacent to it, and a placement is legal exactly when it leaves every group with at least one. Two things follow.

A point can be legal for one player and not the other. Playing next to a lone enemy stone with one liberty is fine if the placement joins a friendly group with room to spare, and illegal if it does not.

A point can be legal for neither. In a fully enclosed single empty point, any stone placed has no liberty and no friendly neighbour, so nobody may play there. Such points are dead squares that neither side can use, and a board can accumulate them.

Both of those are properties of the board, not of the point. And that is the thing that matters for the arithmetic.

Whether a board is the sum of its parts #

The standard move in this subject is to notice that a board has fallen into regions that cannot interact and to evaluate them separately. It is what makes Amazons tractable, it is why a Domineering board can be analysed corner by corner, and it is the reason the disjunctive sum is the object the theory is about.

The technique needs the regions to be independent, and independence is a claim rather than a picture. In NoGo it is usually false, and the reason is a single observation.

A wall between two empty regions has liberties in both of them.

Every liberty of a chain is an empty point, and every empty point belongs to some region. So a chain that separates region $A$ from region $B$ breathes into $A$ and into $B$, and whether a placement in $A$ is legal can depend on how many liberties the chain still has in $B$. The regions are not independent, and they are not independent by construction rather than by accident.

The twenty-four that do add #

They are not random, and looking at them says what the failure is really about.

Many of them are symmetric — a wall with equal room on each side. A single stone in the middle of a five-square row splits it into two regions of two, the stone has one liberty in each, and the whole is worth $0$ while the parts are worth $\ast$ each; $\ast + \ast = 0$, and the sum is right.

Move the stone one square along and the sum is wrong. A stone on the second square of a five-square row leaves regions of one and three, the whole is worth $\{2 \mid \ast\}$, and the sum of the parts is $\{1 \mid -1\}$: not equal, not even the same outcome under every background.

Symmetry is not the rule, though, and the six examples that suggest it are misleading. Checked against all 117, fourteen symmetric boards fail to add and sixteen that add are not symmetric — when the regions add is the census that settles it, and the condition that survives is about liberties rather than about shape: if no stone group breathes into two different regions, the regions add.

So some of the twenty-four are genuine independence and the rest are cases where the coupling exists and does not bite. The wall is shared, a move in one region does change what is legal in the other, and the two effects happen to cancel. That is a much weaker thing than independence, and telling the two kinds apart is what a criterion has to do.

What is lost when the decomposition is wrong #

The 93 failures are not near misses. The difference between the whole and the sum has an outcome of its own, and it is a Left win in 37 cases and a Right win in 37 — so in nearly two thirds of the failures the decomposition does not merely misprice the position, it hands one player an advantage that is not there.

The mechanism is visible in the smallest case. A one-row board with a blue stone at one end and four empty squares beside it splits, if the stone is interior, into two regions. Each region considered alone is a bare strip, and a bare strip’s edge points have liberties into empty space. In the real board those same edge points are adjacent to the stone, and the stone’s presence is what makes several placements legal that would not be legal in an isolated strip — and several illegal that would be legal.

Cutting the region out therefore changes the rules inside it. There is no way to embed a region faithfully except by keeping the stones that bound it, and once those are kept, the two regions share them.

A placement game among placement games #

NoGo is the fourth placement game on this site and the comparison is instructive, because the other three are all legality-by-inspection and this one is not.

Col — a player may colour a vertex not adjacent to one of their own colour. The condition looks at the vertex and its neighbours and at nothing else.

Snort — the opposite condition, and the same locality: a vertex and its neighbours.

Cram — a domino on two adjacent empty squares. Two squares.

NoGo — every group on the board must still breathe. Unbounded.

The values line up with that. Col is cold — one rule makes it cold and the other hot — and Snort is hot, and both have positions that split into independent regions the moment a graph disconnects, because their legality conditions never look further than one edge. NoGo’s condition looks arbitrarily far, and the price is that nothing disconnects.

So the trade is explicit. A rule that consults the whole board buys a game where a stone’s influence is not bounded by its neighbourhood, which is what makes NoGo feel like Go; and it sells the arithmetic that makes the rest of this site work.

What a rule that consults the whole board costs #

The failure here has a shape that recurs across this site, and NoGo is the cleanest specimen of it, so it is worth stating in general terms before it is stated about liberties.

A move rule can be local — legality decided by the position within some fixed distance of the move — or it can be global, decided by a quantity computed over the whole board. Col’s rule is local: colouring a vertex forbids its neighbours and reaches no further, so two components of a graph are two games and no census is needed to say so. Domineering’s is local. Clobber’s is local. NoGo’s is not: whether a placement is legal depends on whether the group it joins has a liberty somewhere, and somewhere has no bound.

A local rule gives decomposition for free and a global one does not, and the reason is that decomposition is exactly the claim that a move in one part cannot change what is legal in another. A rule stated in terms of a global quantity has no argument available for that claim, and NoGo shows it is not merely unavailable but false: a stone in the wall has liberties on both sides, so a placement on the left can be what makes a placement on the right illegal.

That is a different failure from the one a component that has to carry something records. There the rule is local and the state is not — a heap has to remember its cap, or a token has to remember whether it has been spent — and enlarging the component sometimes repairs it. Here the rule itself reaches across, and there is no enlargement short of the whole board.

So the two ways a sum can fail are worth keeping apart. Carrying history is a problem with the component; consulting the board is a problem with the rule. The first has a repair that costs a bigger table. The second has no repair at all, and what is left is to find the boards on which the reaching happens not to matter — which is what this anchor spends its remaining rungs doing.

What the picture cannot show #

A NoGo board looks exactly like a Go board and behaves nothing like one. The most misleading thing about the drawing is the empty point: an empty point on a Go board is a place either player may play, and on a NoGo board it may be a place neither may.

The second is that liberties are not drawn. A group with one liberty and a group with four look identical, and the difference decides which of the neighbouring points are playable. A reader tracing the legality of a move has to count liberties by eye, and the count is the whole of the rule.

The third is the one this essay is about. Two regions of empty points that a reader would take for separate components are separate to look at and joined by the stones between them. Nothing in a drawing distinguishes a wall that couples its two sides from a wall that does not, because whether it couples them is a question about the values on both sides.

The convention, and the bound #

Normal play throughout: the player who cannot move loses. That convention is doing more work here than usual, because in NoGo running out of moves is the only way a game ends — there are no captures, no scoring and no territory, so the board simply fills until somebody is stuck. It is a placement game in the same family as Col and Snort, and like those it is finite for the plainest possible reason: every move puts a stone down and no move ever takes one up.

The bound on the sweep is small and worth stating plainly. Three by three is nine points and its game tree is already substantial; three by four is past what a build should pay for. The independence census covers boards of one and two rows with one or two stones on them, which is 117 split boards, and the counts above are about those and about nothing wider.

A board worth playing out #

The three-by-three empty board is worth $\ast$, which means it is a first-player win and the winning move is not obvious: a tie value on a symmetric board says the mover must find the move that leaves nothing, and there is no reason for it to be the centre.

The board tightens quickly. Every stone placed reduces somebody’s liberties, and a board with six or seven stones on it has most of its remaining points illegal for at least one player. The endgame is a scramble for the last point that anybody may legally take, and it is decided several moves before it arrives.

That is a different shape of endgame from every other game here. In Domineering the last move is a matter of counting the space that is left; in Clobber, of counting the pieces. In NoGo the space that is left and the space that is usable are different quantities, and the second one shrinks faster.

Who built it, and why #

NoGo was proposed in the late 2000s — Kao and collaborators, in the computer-Go community rather than in the combinatorial game theory one — and the motivation was practical. Go is a scoring game, and a scoring game is outside everything the normal-play theory does; Go’s endgame needed a theory of its own, built by Berlekamp and Wolfe out of chilling and thermographs, to say anything exact at all.

Removing captures removes the score. What is left is a placement game that ends when somebody is stuck, which is normal play, which means every theorem on this site applies to it. That is a genuinely good trade and it was made deliberately.

What it did not buy is the arithmetic, and the reason is worth stating in the form the designers would recognise. Go’s whole endgame theory is a decomposition: the board falls into regions, each region is chilled, the values are added, and the answer comes out. NoGo keeps the normal-play convention and loses the decomposition, because the condition that replaced capture is a condition about the entire board.

So the two games trade the same property in opposite directions. Go is a scoring game whose positions decompose; NoGo is a normal-play game whose positions do not. Neither is comfortable, and the discomfort is in a different place.

Where the ladder goes next #

nogo opens here with the finding that a NoGo board’s regions do not add, and the two rungs above take the two questions it leaves.

When the regions add replaces this page’s description of the boards that do add — the ones with symmetric walls — and replaces it because it is wrong. Fourteen symmetric boards do not add and sixteen that add are not symmetric, so the guess made from six examples was a guess made from six examples. What stands in its place is a criterion about liberties: no stone group has liberties in two different regions. It is sound on all 117 boards and provable in a line, and it is complete on only nine of the twenty-four, so the description is exact in one direction and a long way from exact in the other.

How thick a wall has to be then takes the quantitative version this page asks for — a statement about liberty counts rather than liberty regions — and finds the variable was never thickness. Over 590 walled strips a thicker wall does help; split the same 590 by the colour of the stones in the wall and the effect vanishes into that split. A wall of four stones all one colour couples its two sides exactly as a single stone does.

That is the useful form of the finding for anybody playing the game. A wall does not insulate by being solid; it insulates by containing stones of both colours, because a group of one colour needs liberties on both sides of itself and is therefore the thing joining the two regions. Thickness of one colour is not a wall at all — it is a larger group with the same problem.

The direction neither rung takes is the two-dimensional case, where a wall can span the board and where a group can be surrounded rather than merely crowded. Everything measured on this anchor is one and two rows, which is the size at which a wall is a line of stones and not a shape.