The endgame theory arrives late

The parts are worth nothing and the sum is not works out a complete law for Nimstring endgames: count the short chains, notice whether there is a long component, and the outcome follows. It is checked against every bag of chains and loops inside a string budget and it has never been contradicted.

What it does not say is how many positions are bags of chains and loops.

What a component has to look like #

A chain of $n$ boxes is $n$ coins in a row with a string out to the ground at each end: $n+1$ strings, and every coin holds exactly two of them. A loop of $n$ is the same row closed up: $n$ strings, every coin holding two. That is the whole of what the two shapes have in common and it is the property the theory needs.

A coin holding three strings is neither. A coin holding one string is not a component at all but an opened one — the box is free, anybody can take it, and the position is not one a player is choosing from.

So the positions the theory can read are exactly those where every surviving coin holds exactly two strings, and the count is over every subset of a board’s strings rather than over a sample.

The honest denominator #

Counted over all 131,072 subsets of a six-box board’s seventeen strings, 1,033 fall into chains and loops. That is under one per cent and it is the wrong number to quote.

Most of those subsets have a free box on the table. A player meeting one does not choose from it; they cut the last string, pocket the box, and are obliged to cut again. The positions anybody is ever deciding between are the quiet ones — no coin with a single string left, nothing to pocket for free — and there are 28,028 of them.

Against that denominator the share is 3.7 per cent, and on the smaller four-box board it is 11.2. Both are minorities and the larger board is the smaller share, which is the direction that matters: the theory’s reach shrinks as the board grows.

The gap between the two denominators is itself worth a sentence, because it is large and it is the kind of thing a share is often quoted without. Of the 131,072 subsets of a six-box board, 28,028 are quiet — a little over a fifth. The other four fifths have a free box somewhere, and a player meeting one of those is not making a decision at all: the box is taken, the turn continues, and the position moves on. Counting them in would report the theory as reaching 0.79 per cent, which is a true statement about subsets and a misleading one about play.

When it arrives #

The share is not a constant and the shape of the climb is the finding.

Nothing at all decomposes for the first five cuts: a board with twelve strings left on it has a coin with three or four somewhere, necessarily. The first decomposed position appears at six cuts, one of 6,277. At eight cuts it is 166 of 4,329. At twelve it is 86 of 148 — more than half, for the first time, with five strings left of seventeen.

So the chain-and-loop theory is not a theory of Dots and Boxes endgames in the sense of the last third of the game. It is a theory of the last few cuts. For most of a game the board has a branching coin on it somewhere and the whole apparatus — the parity law, the interchangeability of long components, the arithmetic of declining — has no input.

The four-box board tells the same story in less room: first decomposition at four cuts of twelve, half at eight. Two thirds of the way through, on both boards, and the agreement between them is what says the number is about the shape of the game rather than about a particular size.

What is standing in the way #

The obstruction has a name and it is drawn easily.

A coin with three strings is what an unfinished board is full of. Every interior box of a grid starts with four strings, every edge box with four as well counting the border lines, and cutting them one at a time takes a long time to bring every survivor down to two.

That is the arithmetic behind the late arrival. A six-box board has seventeen strings and six coins holding four strings each at the start; getting all six down to exactly two, with none dropping to one, is a narrow target, and the count says how narrow.

The board falls apart twice, and these are different #

There is a second and much larger body of work here about boards falling into pieces, and it is worth separating the two because the words are the same.

A Domineering board falls apart when its empty squares form regions that cannot interact, and the payoff is arithmetic: the value of the whole is the sum of the parts, by the disjunctive-sum theorem, and a product of searches becomes a sum. That decomposition is about independence.

A Dots and Boxes board falls into chains and loops when every coin has two strings, and the payoff is not a sum: the components are worth nought each and the whole is not, because a capture keeps the turn and lets a player cut across the join. This decomposition is about shape.

So the two share a word and almost nothing else. One says the parts do not interact and therefore add; the other says the parts are recognisable and therefore countable, while interacting freely. A reader carrying the first meaning into these essays would expect the nim-sum to work, and it does not.

The share is a different kind of quantity in the two cases as well. Domineering’s boards decompose 47 per cent of the time and the saving is immediate whenever they do. Here the decomposition is a precondition for a law rather than a saving, and the law arrives all at once rather than in proportion.

Why the theory is still the right theory #

None of this is an objection to the endgame analysis and it is worth saying why, because a share of 3.7 per cent looks like one.

The positions that decompose are the ones the game ends in. Every line of play passes through them, and the verdict they carry is the one the scoring game keeps asking for. Every line of play passes through them: once the branching coins are gone they cannot come back, since cutting a string never adds one. So a game is a walk that spends most of its length outside the theory’s reach and finishes inside it, and the finish is where the boxes are won.

And the decision that decides the game is made there. The chains decide it establishes that the question the scoring game keeps asking — who is forced to open — is settled in the endgame, and the endgame is exactly the part the theory reads. Most of the play before it is manoeuvring to arrive at a particular bag of chains and loops rather than another.

So the honest statement is about what the theory is a theory of. It is not a way of evaluating a Dots and Boxes position; it is a way of evaluating the position a game is heading towards. The 3.7 per cent is not a coverage figure; it is the size of the target.

What the first decomposition looks like #

The earliest a six-box board can be a bag of chains and loops is after six cuts, and there is exactly one such position out of 6,277 quiet ones at that depth.

It is worth working out what it has to be. Six boxes hold seventeen strings between them, and cutting six leaves eleven. Every coin has to end at exactly two, so the eleven surviving strings have to be distributed six coins at two each — twelve string-ends — with the ground absorbing the rest. A chain of $n$ uses $n+1$ strings and a loop uses $n$, so eleven strings over six boxes is a partition with the loops doing the work: a loop of four beside a chain of two uses four and three, which is seven, and so on. The arithmetic is tight, which is exactly why there is one of them.

By eight cuts there are 166, by ten 250, and the count then falls again as the board runs out of boxes. So the number of decomposed positions peaks in the middle while the share climbs to the end, and those are two different facts about the same profile.

A count that has a second reading #

There is a second way to read the by-cut profile and it is the more useful one for a player.

At twelve cuts of seventeen the board is more likely than not to be a bag of chains and loops, which is the point at which a player can start applying the law rather than searching. Before that, the position has a branching coin in it and there is nothing to apply.

That is a horizon, and it is not the horizon a search has. A search cut at a fixed depth guesses at its leaves and gets better as the depth rises; a player using the endgame law has no answer at all until the decomposition arrives and an exact one afterwards. The two failure modes are completely different and the second is easier to live with, because it announces itself: a coin with three strings on it is visible.

What a player is doing before it arrives #

If the theory has nothing to say for the first two thirds of a game, something else is deciding what to play, and it is worth naming what.

The two rules everybody is taught cover exactly that stretch. Take every box available is a rule about captures, which happen throughout; whoever opens the first long chain loses is a rule about the endgame stated early, as a thing to steer towards. Both of them are measured against a solver on the boards children draw, and the first costs nothing there while the second is nearly right.

What the census adds is why the second rule is stated the way it is. A player cannot count long chains on a branching board, because there are none — the chains do not exist yet. What they are actually doing is arranging for a particular set of components to exist when the branching runs out, and the folklore rule is advice about the arrangement rather than about the position.

That is an unusual shape for a rule in this subject. Most of what the essays here compute is a function of the position in front of the reader. This one is a function of a position several moves away that neither player has seen, and the whole skill of the game is in steering towards one.

Quiet, and what a subset of strings is #

Normal play for the Nimstring verdicts elsewhere in these essays; here nothing is being solved, only counted.

Three conventions of the count.

A position is a subset of the strings, and every subset is counted. Not every subset is reachable in a legal game — the capture rule constrains the order of cuts — so this is a count over the space rather than over the reachable positions, and it is an upper bound on what a player meets.

Quiet means no coin with exactly one string. That is the condition for there being no free box, and it is the right denominator because a position with a free box is one a player takes rather than chooses from.

And a coin with no strings is gone rather than present. A pocketed box is off the table, so the empty board counts as a decomposition into no components at all — one position on each board, and it is counted.

Two boards, both small #

Two boards, and both small. A six-box board is the largest this brute force reaches: 2¹⁷ subsets is a moment’s work and 2²⁴ for a nine-box board is sixteen million, which is a different piece of apparatus. Whether the share keeps falling and how fast is not measured here, and the two points available both fall.

Nothing weights the positions by how often they arise. A census over played games would be the useful version and is not this. Every subset counts once, and a real game does not visit them uniformly — it visits the ones reachable under play, and under good play far fewer than that. A census over played games would be a different and more useful number.

And the count says nothing about the sizes. A board that decomposes into six one-box chains and one that decomposes into a single six-chain both count once, and the law treats them very differently. A census weighted by how much each decomposition decides — by how many boxes are still on the table when it arrives — would be a different picture, and the profile above is the flat version of it.

Nor is the quiet condition the same as being at the end of a turn. A turn ends on a cut that takes no box, so the position afterwards has no free box and is quiet; but a quiet position can also be reached mid-turn, and the census cannot tell the two apart because it is counting subsets rather than plays.

The shape of the obstruction, counted #

One more way of putting the same number makes the lateness intuitive rather than surprising.

A six-box board laid out as two rows of three has, at the start, six coins of degree four: every box is bounded by four lines, and a border line is a string to the ground rather than an absence. For the position to decompose, every one of those six has to come down to exactly two, and none may fall to one on the way — a coin at one is a free box and the position is not quiet.

So the target is six coins landing simultaneously on a single value out of the five they pass through, which is a coincidence rather than a tendency. Seventeen strings offer a great many ways to arrive and very few of them land everything at once. The census is the arithmetic of that coincidence, and 3.7 per cent is what it comes to.

It also says why the share climbs so steeply at the end. Once most strings are gone the coins are near the bottom of their range and the remaining choices are few, so the ways of missing run out faster than the ways of hitting. The profile’s last four columns go 58, 73, 100, 100 per cent, and the climb is the space for error closing rather than anything about the game.

Still open: the positions a game actually reaches #

The measurement this essay wants next is the one it declines to make: the same census over positions reachable under play rather than over every subset.

Two things would change and they pull opposite ways. The capture rule forces a run of cuts whenever a box is freed, so positions with free boxes are passed through rather than rested in, which would raise the share. And good play avoids opening components early, which keeps the board branching for longer and would lower it.

Which effect wins is not guessable from anything here, and the measurement is straightforward: walk the game tree of a four-box board, record the positions at the end of each turn, and take the same census over those. That is a count over a few thousand positions rather than a few thousand subsets, and it is the number a player would actually want.