The chains decide it before the boxes do

The previous essay ended on a quantity that has no units. A good Dots and Boxes player is not fighting over boxes; they are fighting over the obligation to open the next chain, and boxes are what they spend to acquire it.

A quantity with no units and no place in a score is exactly the kind of thing this site is for. And there is a game about it, played on the same position, with no score in it at all.

Throw the score away #

Take a strings-and-coins position and change one rule. No points. Whoever makes the last cut wins.

That is Nimstring, and everything else stays: cutting the last string on a coin still pockets it, and pocketing still obliges another cut. The only thing gone is the accounting.

By the time either game reaches an endgame the position has drifted to the state the scoring rung draws: every coin still on the table holding exactly two strings, because both players spend the whole middlegame refusing to hand over a coin with one. A graph in which every vertex has degree two is a disjoint union of paths and cycles, so an endgame of any board whatever is a multiset of two kinds of component — chains and loops — and every figure below is drawn on such a multiset rather than on a grid of dots.

What that change buys is enormous. Nimstring is impartial: both players have the same moves from every position, since a cut is a cut whoever makes it. So the whole of the impartial theory applies to it — Sprague–Grundy, the mex rule, the nim-sum of a decomposed position, all of it — where the scoring game had none of them.

There is one wrinkle and it is the only one. A cut that pockets a coin obliges the same player to cut again, so such a move does not hand the position over — which means a turn is a run of capturing cuts ending in one that captures nothing. Folded into the definition of an option, that is all the difference amounts to, and the resulting game is an ordinary finite impartial game under normal play. The recursion here says so directly: a capturing cut that empties the board is a win, because the mover made the last cut.

What being impartial buys is the whole of the normal-play apparatus at once. Every impartial position under that convention is equivalent to a single Nim heap, the value of a sum is the nim-sum of the parts, and a total of zero means the player to move loses. Dots and Boxes has none of that and never will, because it keeps a score; the game underneath it has all of it.

Does it answer the right question? #

Berlekamp’s claim is that the Nimstring game decides control of the scoring game, and control is what wins it.

That is a strong claim and it is not an identity. A player can hold control and still lose on points, if there is not enough left on the table for the control to be worth anything. So the honest form of the claim is a rate, and the rate can be measured: solve every position of a board twice — once as a scoring game and once as Nimstring — and count.

Ninety per cent, and the shape of the remaining ten is the informative part. With one box left the two agree every time — with fourteen such positions, all fourteen. With three boxes left the rate is at its worst. With six the rate recovers.

The reason is worth stating: with very little left, control is worth nothing and the scoring game is decided by what is on the table. With a lot left, control is worth more than anything on the table and Nimstring settles it. The dip is the region where the two quantities are comparable, and it is exactly the region where a player has to think.

The same measurement on a four-box board comes out at 89.6% over its 4,095 positions — within a point of the six-box figure, which says the relationship between the two games is not an artefact of board size. The shape repeats as well as the rate: with one box left the two agree on all twelve such positions, and the dip is again in the middle. That is the board on which the beginner’s rule costs nothing at all, so it is worth knowing that the impartial game is no less informative there; what is missing on a small board is not the relationship but anything long enough to be worth declining.

The rule players learn #

Somebody who has played a few hundred games arrives at a sentence: whoever has to open the first long chain loses. A long chain is one of three boxes or more, which is the length at which declining becomes possible — a chain of two can be opened hard-heartedly, by cutting its middle string, after which every remaining cut in it completes a box and there is no non-capturing move to decline with; a chain of one has no tail to leave.

The sentence is folklore in the precise sense that it is passed on without a derivation. Here it is checked instead.

Sixty-nine of sixty-nine. On positions made only of long chains, the player forced to open loses every time in range. That is as clean as a folklore rule ever gets, and it is worth noticing that the rule as usually stated does not say “made only of long chains” — it says “the first long chain”, which is a looser claim with 80 counterexamples in this range alone.

The counterexamples all contain a short chain, and the smallest of them is worth playing out rather than quoting.

A chain of one is not an obligation; it is a present. Opening it costs one box and passes the turn immediately, because there is nothing left to decline, so each one is a free change of whose turn it is to be in trouble.

Which suggests the exceptions are about how many presents there are rather than about there being any, and that is what the recursion says. Remove one of the three and the verdict comes back.

Two chains of one and the opener loses; three and the opener wins; four and the opener loses again. The exceptions are a parity, and the quantity whose parity it is has nothing to do with the long chain the rule names.

Why the rule is true when it is #

The derivation is short enough to give, and giving it is what turns a measured rate into an understood one.

Suppose every chain is long. The player who opens one hands it over; the opponent takes all but two and hands the obligation back, keeping the difference. That exchange repeats down the whole list of chains, and each repetition costs the opener the length of a chain and returns two boxes. Since every chain is at least three, every exchange is a net loss for whoever is opening — so the player who opens first opens every time, and loses by the accumulated difference.

Now let a chain of one in. Opening it costs one box and passes the obligation immediately, because there is nothing to decline. A chain of one is therefore a tempo move: it changes whose turn it is to be in trouble and costs almost nothing. Enough of them and the parity of the whole list reverses, which is precisely what what a value leaves out is about — two positions of the same nominal worth differing in how many moves they take to collect.

That is the whole rule and the whole of its exceptions, and neither sentence mentions a board.

Set those two side by side and a reader could conclude that three chains tie and two do not, which would make the tie a fact about the count. It is a fact about the length instead, and the way to see that is to keep the count and lengthen the chains.

Why this is a decomposition #

A Nimstring endgame is a sum, in the strict sense this site uses everywhere. The chains do not interact: a cut in one changes nothing about any other, and a player must choose which part to move in.

That is the same saving a board that falls into regions buys, arriving inside one drawing rather than across two: the whole costs the product of the parts’ searches and the parts cost their sum, because no move in one component can reach another. Every figure on this page is that decomposition drawn — a row of components with the reader asked which one to open — and the reason the rows are legible at all is that the components genuinely do not interact.

It is also why the scoring rung’s endgame recursion is short. It is not a special-purpose trick for this game; it is the disjunctive sum with one extra decision at each step, and the extra decision — accept the whole component or leave its tail — is what the scoring convention adds. Choosing which part to move in is the general form of the question, and here it has an unusually crisp answer: which component matters far less than whether the tail is left, and the tail is decided by a parity rather than by a size.

What a Grundy value would buy #

Since Nimstring is impartial, every position of it has a Grundy value, and the value of a sum of chains is the nim-sum of theirs. That is a real theorem about a real game people play, and it is worth being precise about what it would give a player.

It would give the outcome of any endgame instantly: compute a value per component, exclusive-or them, and a total of zero means the player to move loses. It would not give the score, because Grundy values are about who moves last and nothing else. And it would not give the loony decision directly, because that decision is about points rather than about moving last.

So the impartial theory settles the question of control completely and the scoring question not at all — which is the division of labour the measured agreement rate above is a picture of. A player who knows the Nimstring value knows who will be forced to open, and still has to count.

Such a table would be of the same kind as any other impartial value table on this site — a mex over options, one entry per component — and having it would turn an endgame from a search into an exclusive or. What it would not turn into anything is the decision the figures on this page are drawn around.

The other kind of component #

Every endgame above is a row of chains, and half of what a real board falls into is not a chain. A loop is a cycle of coins rather than a path, and it changes one number: eaten down to its last four, a loop cannot be left with two, because taking two more would open the rest of the ring. So a loop is declined four boxes at a time rather than two, and its fee is double.

That is a component with the same purchase available at twice the price, which is the ordinary situation everywhere else on this site and is why the recursion has to be run rather than replaced by a rule. A player facing a chain and a loop is choosing between two ways of buying one thing, and the cheaper purchase is not always the one to make.

The wrinkle is a compulsion, and it folds away #

The section that introduces Nimstring passes over its one irregularity quickly — a capturing cut obliges the same player to cut again, so a turn is a run of cuts rather than a single one — and it is worth slowing down, because that irregularity is a rule this site has an essay about, and the reason it causes no trouble here is precise.

A move that constrains what happens next is an entailing move, and entailing moves break the disjunctive theory. They break it badly: in Top Entails the Sprague–Grundy theorem fails at two heaps of two, $G + G$ stops being a second-player win, and the whole apparatus this essay has just finished invoking is unavailable.

So why is Nimstring fine? Because of who is compelled.

In Nimstring the compulsion falls on the mover: capture, and another cut is compulsory. That can be absorbed into the definition of an option — a turn is any run of capturing cuts followed by one that captures nothing — and once absorbed, the game hands over to the opponent in the ordinary way with the ordinary freedom to reply anywhere. Nothing constrains the opponent, so nothing constrains the mirror strategy the Sprague–Grundy proof runs on.

In Top Entails the compulsion falls on the opponent: take the top coin, and they must move in that heap. That cannot be folded into the mover’s turn, because the opponent still chooses among the moves available there. The constraint lands on somebody else’s decision, and the argument that a sum can be answered component by component is exactly an argument about the freedom of that decision.

A compulsion on the mover folds away; a compulsion on the opponent does not. That is the whole of why one of these games has a complete impartial theory and the other has a counterexample at two heaps of two.

Which is where the word came from #

That also explains a piece of vocabulary the entailing essay borrows without ever coming home.

The word loony — a move nobody would make, a position that wins for the mover whatever else is present — is Dots and Boxes vocabulary, and it arrived there because this game is where players had to name the thing. Opening a chain when a chain is already open is loony; so is taking a chain in full when declining is available. A loony move hands the opponent everything, and the reason it can be identified without reference to the rest of the board is that its badness does not depend on the rest of the board.

Notice that the folding above is what makes the loony decision a choice rather than a rule of play. If a capturing run were forced to be maximal — capture everything available, always — there would be no decline, no fee to pay for control, and no essay. The option set is “any number of captures, then a cut that captures nothing”, and the freedom to stop early is what the previous rung’s entire endgame recursion is about.

So the wrinkle is not a technicality tucked into a definition. It is the game: the compulsion is what makes captures come in runs, the freedom to end a run early is what makes control purchasable, and both survive the folding that keeps the impartial theory applicable.

And it is worth noticing how narrowly that worked out. Change the compulsion’s direction — make a capture oblige the opponent to cut on the same coin — and the folding is unavailable, the sum theory goes, and no amount of Nimstring rescues the analysis. The game people actually play sits on the safe side of a distinction nobody playing it has ever had to make.

What the impartial game does not know #

Nimstring is not a substitute for the scoring game and the ten per cent is where the difference lives.

The clearest statement of the gap: Nimstring cannot tell how much is at stake. Two positions with the same Nimstring verdict can differ by twenty boxes, and a player who has been handed control of a position with nothing in it has been handed nothing. Control is a binary and score is a number, and converting between them requires the very accounting Nimstring threw away.

There are six-box positions with five boxes still on the table where the scoring solver and the Nimstring solver both call it a win for whoever cuts now — and the margin the scoring solver returns is one box, not five. The two answers agree and they are answers to different questions: one says who ends up having to open, the other says what that is worth, and five boxes of material can come down to a margin of one.

This is the same shape as outcomes not adding. An outcome class is a coarse reading of a position, a value is a fine one, and the coarse reading composes badly precisely because it discards the quantity that composes.

The second thing Nimstring does not know is how a position got here. Control is a property of the position and the score is a property of the history, so two identical Nimstring positions can sit under wildly different scores. That is not a defect — a game value is a statement about the future in every theory on this site — but it is the reason a Nimstring analysis has to be carried alongside an ordinary count rather than instead of one.

The convention, named #

Nimstring is normal play and Dots and Boxes is not, and the whole of this essay is about the relationship between them.

Every theorem cited here — Sprague–Grundy, the nim-sum of a sum, the mex rule — is a theorem about normal play and holds of Nimstring exactly. None of them is a theorem about Dots and Boxes and none is claimed to be. What connects the two is a measured rate, and rates are not theorems.

That distinction is the reason this essay counts rather than asserts. It would have been easy to write “Nimstring decides Dots and Boxes” and quote Berlekamp; what is written instead is that the two agree on 118,507 of 131,071 positions and that the disagreements cluster where the boxes remaining are few.

It is also the reason the previous rung and this one are separate essays. The scoring game is measured against a solver and the impartial game is analysed with theory, and running the two together would have let the theory take credit for the measurements. Where the theory stops and the search starts is a line this site keeps drawing, and it runs straight through the middle of this game.

The surprise: the decomposition is inside one position #

Everywhere else on this site a sum is several positions side by side and the theory is applied across them. Here the sum is inside a single drawing: one grid of dots, which is one game, whose endgame is a multiset of independent components that no move can carry between.

That is the same manoeuvre a row of coins makes — a single row that is already a sum, with a component per head — and it is worth noticing because it is the shape a decomposition takes in games people actually play. Nobody sets out three separate Nim heaps. What happens is that one position falls apart, and the theory’s whole apparatus becomes available at the moment it does.

The falling-apart is not a courtesy either. It is forced, by the argument in the previous essay: both players avoid reducing a coin to one string, so the position drifts to the state where every coin has two, and a graph with every vertex of degree two is a union of paths and cycles whether anybody wanted it or not.

What that means for a player is unusual. The theory is inapplicable for most of the game and becomes exactly applicable at a moment neither player chose, and the skill the endgame rewards is recognising that the moment has arrived. Comparing two positions is a decidable question once the components are known and a hopeless one before.

What the picture cannot show #

One loop is drawn here and a real endgame has several, in company with chains of every length, and nothing above draws that.

Every endgame on this page has at most three components and none has more than one loop. The recursion handles any multiset of either kind and the counted claims come from a survey of endgames of up to four components, so the arithmetic is not the limit; the row of squares is. A position with two loops and four chains would be a legible drawing of nothing, because the branch worth watching would be one component out of six and the reader would have to be told which.

The second thing not shown is the board. Every figure here is an endgame already decomposed into its components, and finding those components on a grid of dots is a separate skill that no picture of a row of squares contains. A player at the table is looking at lines and has to see chains; these figures start after that has been done.

And the third is how the position got there. A row of components carries no score, so nothing above says whether the player who is about to be handed the obligation is twelve boxes ahead or twelve behind — which is exactly the quantity the agreement rate says the impartial game discards.

Where the ladder goes next #

This anchor stops at two rungs and the reason is worth recording.

A third rung would be the full Nimstring theory — the Grundy values of chains and loops, the way they combine, the point at which the analysis of a whole board becomes tractable — and that is a substantial piece of work whose figures would be tables of values rather than pictures of positions. It is a candidate rung rather than a gap in this one.

What the two rungs here establish is the shape of the thing: a game everybody plays, a rule everybody is taught that is wrong, an impartial game underneath that explains why, and a folklore rule that turns out to be exactly right on the positions it was really about and to have counterexamples everywhere else.