How thick a wall has to be

NoGo is the game where a move that leaves any group without a liberty is illegal, which makes a stone on the board a constraint on squares nowhere near it. That is why the game does not decompose: two empty regions with a stone between them are not two games, because a move in one can take away the liberty the other was relying on.

When the regions add found a criterion covering part of the failures and closed by naming the rung above:

A wall one stone deep is the only kind here, and the interesting question is quantitative: how weakly does a wall couple its sides as it gets thicker?

Asked that way, the question has an encouraging answer. Asked one level down, it has a better one: thickness is not the thing.

The question as asked #

The census is 590 strips. Each is a row of between four and ten squares with a run of k stones somewhere along it, in every possible colouring of the run, leaving a non-empty stretch of empty squares at each end. For each, the value of the whole strip is computed and compared with the sum of the values of the two ends taken as separate boards.

The answer is that thickness helps a great deal. At one stone the two ends add on 2 strips of 70. At two, 46 of 112. At three, 116 of 168. At four, 212 of 240 — eighty-eight per cent.

That is a clean monotone trend and it is what the rung below expected. A thicker wall has more of its own liberties inside itself, so it is less dependent on the two regions, so a move out in one region is less likely to matter to the other.

The explanation is wrong, and the way to see that it is wrong is to split each of those four rows in two.

Colour, not depth #

A NoGo wall is made of stones and stones have colours, and a run of stones all one colour is one group. A group’s liberties are pooled: any empty square adjacent to any stone of the group keeps the whole of it alive.

So a wall of four blue stones lying between two regions has liberties on both sides, pooled. A move out in the left region that fills the last empty square there can leave the group depending entirely on the right region — which is exactly the long-range coupling that stops the board decomposing, and it does not care how thick the wall is.

A wall of one blue and one red is two groups. The blue stone’s only empty neighbour is on the left; the red stone’s is on the right. Neither group has anything to do with the other side, and the two regions genuinely cannot reach each other.

A wall all of one colour separates the sides on two strips at every thickness — one, two, three and four. Not two per cent more at each step; the same two, every time.

A wall of more than one colour separates them on 44 of 56 at thickness two, 114 of 126 at three, and 210 of 210 at four.

So the trend in the first figure is not a fact about thickness. It is a fact about counting: a wall of four stones has sixteen colourings and only two of them are monochrome, while a wall of one has two colourings and both are. The thicker the wall, the smaller the share of colourings that make it a single group, and the whole of the apparent trend is that arithmetic.

The criterion, and what it is a criterion about #

Stated properly the condition is not about colours at all: no group of the wall reaches both regions. On a strip a group is a maximal run of one colour, so a wall reaches both sides exactly when it is monochrome, and the two statements coincide. On a two-dimensional board they would not, and the group version is the one that generalises.

That is a proper answer to the rung below’s question and it is a different kind of answer from the one asked for. The rung below wanted a quantity — how weakly, with an amount attached. What the census produces is a condition, and the quantity turns out to be a side effect of how many walls satisfy it.

The condition scores 558 of 590. Two hundred and thirteen of those are correct refusals — monochrome walls that do not separate — and 368 are correct separations.

The thirty-two it gets wrong, both classes #

Thirty-two strips are called wrongly and they fall into two groups, each with a description, and each description is asserted by the census rather than observed.

Twenty-four have a mixed wall and do not separate. Every one of them has an end of one or two squares. A region that small has no room: its only empty squares are the ones adjacent to the wall, so a move there fills a liberty of the wall stone immediately, and the wall stone’s fate is decided by whether the other region can supply it — which is precisely the coupling the two-group argument said could not happen. The argument assumes the group has a liberty on its own side to lose; with a one-square end there is nothing else there.

Eight have a monochrome wall and separate anyway. Every one of them has two ends of the same size. Those are strips like ..B.. and ..BBBB.., and the reason they pass is arithmetic rather than independence: the whole strip is symmetric, so it is its own negative and worth nought, and the sum of two equal-and-opposite ends is nought too. Both readings are nought and neither is telling the truth about decomposition.

The second class is worth dwelling on because it is a failure mode of the measurement rather than of the criterion. Testing decomposition by asking whether the whole equals the sum will always be fooled by a position where both happen to be nought, and a symmetric strip is exactly that position. A test that compares two numbers cannot tell agreement from coincidence, and the eight are what that looks like.

What this does to the rung below’s criterion #

When the regions add found that no reachable position ever mixes the colours is sound and covers 254 positions without being necessary on 860 more. This page’s criterion is a different animal and it is worth saying how.

The rung below’s condition is about what can happen during play and it is checked by search. This one is about what the position looks like now and it is checked by looking at the stones. The first is stronger where it applies and expensive; the second is cheap and has thirty-two exceptions of which twenty-four are describable by a second glance at the board.

For a solver the cheap one is worth more, and the reason is the shape of the saving. Deciding to split a board is worth doing only if deciding costs less than not splitting, and a criterion requiring a search over reachable positions has already paid most of the price of evaluating the board. Looking at the colours of a wall costs nothing.

The practical rule that comes out of the census is short: split a NoGo board at a wall whose stones are not all one colour, unless one of the resulting regions is smaller than three squares. That rule is right on 566 of the 590 strips here — the 558 the criterion gets right, plus the eight it gets wrong in the harmless direction, since treating a symmetric strip as coupled loses nothing but time.

Why a group and not a stone #

The mechanism deserves one paragraph on its own, because it is the whole of NoGo and it is not obvious from the rule.

The rule says a move is illegal if it leaves any group without a liberty. Group, not stone. Two adjacent stones of one colour share their liberties completely: fill every empty square next to one of them and the other’s empty neighbours keep both alive.

That pooling is what makes distance irrelevant. A blue group snaking across a board has one pool of liberties, and a move at one end of the board can be illegal because of a liberty count at the other. It is the same structure as a chain in Dots and Boxes, and the same reason independence has to be claimed rather than assumed — a long object whose fate is decided as a unit — and it is why NoGo is the site’s standing example of a game that looks decomposable and is not.

So the two-colour wall works not because two colours are magic but because two colours are the cheapest way to guarantee two groups. A wall of four stones arranged as blue, blue, red, red is two groups and separates; a wall arranged blue, red, blue, red is four groups and separates. What matters is only whether some group has an empty neighbour on each side.

What a thicker wall does buy #

None of the above says thickness is irrelevant, and it would be a poor reading of the census to conclude that it is. Thickness buys two things and neither is the one the rung below hoped for.

It buys colourings. A wall of four stones has sixteen arrangements and fourteen of them are two groups or more. That is the whole of the trend in the first figure, and it is a real effect on a real board — a player who has played four stones in a row has almost certainly played two colours’ worth, because the two players alternate.

That last observation is worth pulling out, because it changes what the census means for a game in progress. A wall on a board that arose from play is nearly always mixed, since the stones were placed alternately by two players; a monochrome wall of four is a position both players would have to have cooperated to reach. So the coupling this page is about is a feature of constructed positions much more than of played ones, and the criterion’s ninety-five per cent is, if anything, an underestimate of how often a real board decomposes.

And it buys distance, which this census does not price. A thick wall puts the two regions further apart in squares even when it does not separate them, and the difference between the whole and the sum is recorded for every strip here as a game rather than as a number. Whether that difference gets smaller as the wall thickens — on the monochrome walls, where it never reaches nought — is the how weakly the question actually asked for, and it is a measurement this page has not made. Comparing two games that are neither above nor below one another needs a scale to compare them on, and picking one is the work.

Why colour is the variable and thickness is not #

The result reads as a surprise and it is not one once the mechanism is stated, which is worth doing because it turns a measurement into something a player can apply at the board.

A wall couples its two sides when a stone group in it has liberties in both regions. Whether that happens is a question about the group, and a group is a maximal connected set of stones of one colour. So four stones of one colour in a row are one group, with liberties on both sides of the wall — exactly like a single stone, and coupling exactly as much.

Thickness in one colour does not make more groups; it makes one bigger group. And a bigger group has more liberties, which is if anything worse, since it has more ways to be short of room somewhere and more places for the two regions to meet inside it.

Two colours behave completely differently. A wall of alternating stones is several groups, each small, and a group whose liberties lie entirely on one side of the wall couples nothing at all. So what insulates is not the number of stones but the number of colour changes, and a wall of four stones alternating is a genuine barrier where four of one colour is not.

That also explains why the aggregate over 590 strips shows thickness helping. Thicker walls in a random pool are more likely to contain both colours, so thickness is correlated with the thing that matters and has no effect of its own — the standard shape of a confounded variable, and the standard fix, which is to split the sample by the confounder rather than to widen it.

What the census does not say #

Four limits, and the first is the one to fix next.

Strips only. Every board here is one square high. On a strip a group is a run and the criterion collapses to not all one colour, which is why the census can be exhaustive. On a two-dimensional board a wall can be a diagonal staircase, a group can loop, and no group reaches both regions is a real condition rather than a restatement. Nothing here says it still holds.

Ten squares. The longest strip is ten, which is what the evaluator affords with a wall in the middle. The exception class an end of one or two squares is a claim about small ends and it is measured on strips whose other end is at most eight.

Walls that are runs. A wall here is a contiguous run of stones. A pair of stones with a gap between them is a different object and would divide the strip into three regions, and the census does not contain one.

And decomposition is tested by comparing values. The whole against the sum of the parts, which the eight symmetric exceptions show is a test that can pass by accident. A stronger test would compare the two as games in every company rather than as values — equality in a universe rather than equality — and that is a much larger computation than this one.

The convention, named #

Normal play. A move places a stone of one’s own colour on an empty square, and is illegal if after it any group of either colour has no liberty; a player with no legal move loses. Left plays blue and Right red.

A group is a maximal set of same-coloured stones connected orthogonally, and its liberties are the empty squares adjacent to any of its stones. A wall here is a contiguous run of stones on a one-square-high board with at least one empty square on each side.

The two ends are evaluated as boards in their own right, keeping the stones that bound them — which is the same lifting the rung below uses, and it matters: an end evaluated without its bounding stone is a different position, because the stone is what its edge squares are adjacent to.

Where the ladder goes next #

The nogo anchor has three rungs: the game with its census of failures, a criterion that explains part of it, and now the property of a wall that decides whether the sides are separate.

The rung above is the two-dimensional case, and it is where the criterion stops being a restatement. On a board a wall can be a staircase, a group can wrap round a region, and no group of the wall reaches both regions is a genuine graph condition with a genuine cost to check. Whether it still scores in the nineties, and whether the small-end exception survives when a region can be small in one direction and large in another, is a computation of the same shape on boards a build can only just afford.

Two neighbours are worth the trip. Every group must keep breathing is where the rule’s long reach is established, and it is the page that makes this one’s mechanism — pooled liberties — into the thing the game is about. And the board falls apart is what a decomposition is worth once it is available, which is the reason a cheap criterion for when it is available is worth more than an expensive one.