The parts are worth nothing and the sum is not

The chains decide it puts an impartial game underneath the scoring one. Strip the points out of Dots and Boxes, keep the moves, and play for the last cut: that is Nimstring, and who wins it is very nearly who wins the game people actually play, because it answers the question the scoring game keeps asking — which player is going to be forced to open the next chain.

That essay establishes that the skeleton exists and that it decides things. It stops short of the obvious next question, which is what the skeleton is made of. An impartial game under normal play has a Grundy value. A position that falls into independent components should have the nim-sum of theirs. Dots and Boxes endgames fall into components more cleanly than almost anything on this site — a board reduces to a bag of chains and loops, and the bag is all that matters. So the arithmetic ought to be short: value each chain, value each loop, exclusive-or the lot together, and the whole endgame is one line.

The values are easy to get. There are eleven of them and they are all the same.

Nought, eleven times over. A one-chain is worth nought, an eight-chain is worth nought, a four-loop and a six-loop and an eight-loop are worth nought.

Read as a fact about single components that is entirely sensible. A lone chain is one thing that has to be opened by somebody, and whoever opens it hands the whole of it to the opponent, who takes every box in it and thereby makes the last cut and wins. The player to move loses. That is a second-player win, and a second-player win is Grundy value nought.

Read as an input to the nim-sum it is catastrophic. Nought exclusive-or nought is nought. If the theorem applied, every Nimstring position built out of chains and loops would be a second-player win, and the whole subject would collapse into a single sentence.

What the theorem actually requires #

It does not collapse, and the reason is a condition in the theorem that Dots and Boxes quietly fails.

Sprague–Grundy is about a disjunctive sum: a position made of components, where a move consists of moving in exactly one of them, and then the turn passes to the other player. Nim and the nim-sum is the base case and the sum is the object is the general statement. Both halves of that condition are load-bearing, and it is nearly always the first half people check.

Nimstring satisfies the first half perfectly. A cut is a cut in one component; the components share no strings; nothing a player does in one chain has any effect on another.

It fails the second half. A cut that frees a coin obliges the same player to cut again — that is the rule that makes the game the game, and it is where the score in Dots and Boxes comes from. So a move does not necessarily pass the turn, and a player who takes a coin in one component may take their next cut in a completely different one. The components are joined, not by a shared string, but by a shared obligation.

That is enough to break the theorem, and the size of the break is worth seeing rather than conceding.

Two components, both worth nothing, and the pair is worth one or two. A one-chain beside a three-chain is a first-player win; a one-chain beside an eight-chain is a first-player win; a two-chain beside anything long is worth two. And a three-chain beside a four-loop is worth nought, exactly as predicted, which is the part that makes the failure hard to notice by accident — two thirds of the pairs come out right.

A theory that is right two thirds of the time on the cases somebody happens to try is worse than one that is wrong every time. This is why the check is over every pair rather than a few.

The pattern in the failures is already visible here and it is the shape of everything that follows. Every pair that breaks the prediction has a short chain in it — a chain of one box or two. Every pair of long components, whatever their lengths, comes out at nought as predicted. So the arithmetic is not failing everywhere at random; it is failing in a place, and the place is where a component can be given away without giving away the turn.

That is also the answer to the obvious repair. Faced with a sum rule that does not hold, the natural move is to look for the right values — to suppose that the components have some other number attached to them that does add, and that nought was simply the wrong number. It is not a foolish idea and it is what a great deal of loopy and misère theory amounts to. It cannot work here, and the reason is in the figure rather than in an argument: a one-chain contributes 1 when it sits beside a long component and contributes nothing when it sits beside another one-chain. Whatever a component is worth, it is not worth the same thing in different company, and a value that changes with its neighbours is not a value that adds.

How the values were computed at all #

Between the failure and the replacement there is a piece of machinery, and it is worth a paragraph because the awkwardness of the rule is exactly what the machinery has to encode.

A Nimstring move is a cut. A Nimstring turn is a run of cuts: each one except the last takes at least one coin, and the last takes none. Only at the end of a turn does the position change hands. So the options of a position, in the sense Sprague–Grundy needs, are the positions reachable at the end of a turn — not the positions reachable after one cut. Written that way the game is an ordinary impartial game again, alternating properly, and Grundy values are well defined for it.

There is one boundary case and it is the one that gives every lone component its nought. A run of cuts that clears the board never ends in a non-capturing cut, because there is nothing left to cut. It is not an option at all; it is a win for the player making it. So a turn that empties the board is a move to a position with no moves, and the mover has made the last cut.

That construction is new code, and new code that produces a surprising answer is the code to distrust. The three boards at the bottom of the first figure are the answer to that: the same positions solved by the turn-by-turn walk and by the plain win-or-lose solver the chains decide it already used, agreeing on all three. Neither knows anything about the other, and the figure refuses to draw if they disagree.

The two pieces of code differ in exactly the way that makes the check worth something. The older one asks does the player to move win, recursively, with the capture rule handled by the same recursive call rather than by an explicit notion of a turn — a boolean, propagated. The new one asks what is this position’s Grundy value, which requires enumerating whole turns, taking the set of values they lead to, and finding the least number missing from it. They agree on which player wins because that is a consequence of the Grundy value, not because either was written to match the other. An implementation that had the turn boundary in the wrong place would still terminate, still produce plausible small integers, and would part company with the boolean solver on the first board with two components in it.

The other thing the construction settles is the shape of the components. A chain of n boxes is n coins in a row, joined by n − 1 strings, with a string from each end coin out to the ground; a loop of n is the same row closed up, so the two ground strings are gone. Every coin holds exactly two strings in both. That is the whole difference between a chain and a loop, and it is the reason the two behave so similarly: from the point of view of the person who has to open one, they differ only in how much is handed over, and the law below says that quantity is not what anything depends on.

The rule that replaces the theorem #

What is left when Sprague–Grundy goes is not a mess. It is a rule with three numbers in it, and it is a good deal simpler than the theorem would have been.

The first player wins exactly when the number of short chains is odd — unless there is no long component at all, in which case it is when the number is even and not nought.

That is the whole law, it is checked against every one of the 207 positions the walk reaches, and the function refuses to return a result if a single one of them disagrees. Not a tendency, not a rule of thumb with exceptions listed underneath: a prediction, applied uniformly, that has yet to be contradicted.

Three things in it are worth pulling out.

The lengths of the long components do not appear. A three-chain and an eight-chain and a twelve-loop are entirely interchangeable, and so is any number of them beyond the first — a position with one long component and a position with three behave identically. All that matters is whether there is at least one.

The lengths of the short chains barely appear either. A one-chain and a two-chain count the same towards the parity. They differ in the value — a two-chain beside a long component gives two where a one-chain gives one — but not in who wins.

And the parity flip is the strangest of the three, because a long component contributes nothing on its own and reverses everything in company. With no long component present, an even number of short chains is a first-player win; add a single long chain, change nothing else, and it becomes a second-player win.

One more thing does not appear in the law, and its absence is worth noticing because it is the quantity the scoring game is entirely about. The number of boxes does not appear. A position with a three-chain and one with a twelve-chain are the same position as far as this table is concerned, and they differ by nine points. That is not a defect of the skeleton; it is the definition of it. Nimstring throws the score away and keeps the question of who is forced to move, and the reason it is worth studying is that the second question turns out to decide the first almost always — which is the measurement the rung below made and this rung is entitled to lean on.

Where that flip comes from #

The flip is not an anomaly to be reported and left. It is the same fact the chains decide it is about, arriving in a different notation.

A short chain is a chain a player can open without giving anything away — with one or two boxes in it, the opponent takes them and is then obliged to cut again, which means opening the next thing. Short chains are therefore tempo: each one is a turn that gets passed straight back, and an even number of them cancels.

A long chain is not like that. Whoever opens one hands over every box in it, and the opponent finishes it and is then obliged to cut again — into whatever is left. That is why the last long component is the thing everybody is manoeuvring not to open, and it is why the count of long components does not matter beyond zero: they all end the same way and only the last one settles anything.

So the parity flip is the arithmetic of a single question — who is standing there when the last long component has to be opened — written as a Grundy value rather than as a strategy. The folklore rule players are taught, and the exceptions the rung below found the solver disagreeing with, are both in this table.

Those two positions differ by a single box sitting on its own, worth nothing to anybody, and they have opposite outcomes. That is the parity being visible in the only way parity is ever visible, which is by adding one and watching everything invert.

It is also the practical content of the law, and the reason it is worth having in this form rather than as a strategy. A player counting long chains — which is what the folklore says to do — is counting the thing that does not matter past the first. A player counting the short ones is counting the thing that does.

Interchangeable for the answer, not for the value #

There is one more measurement, and it is the one that says how far the law can be pushed.

Twenty-seven of the shapes are realised by more than one set of components, and inside every one of them the winner is the same. That is the interchangeability claim, and it is tested rather than asserted: if a three-chain and a five-chain ever produced different winners in otherwise identical company, the walk would stop.

The values are not interchangeable. A two-chain with two three-chains is worth 1; a two-chain with two five-chains is worth 2. Same shape, same winner, different number.

The gap has a location, too. Both positions in the witness have the same shape — one two-chain, two long components — and the long ones are three-chains in the first and five-chains in the second. So the value is sensitive to a length that the outcome ignores, and it is sensitive to it in a small way: 1 against 2, both of them first-player wins. Nothing about the game changes; a number the theory would have used to add the position to another one changes.

That is the honest limit of the result and it is worth stating plainly rather than rounding off. What has been found here is a complete law for the outcome and no law at all for the value. The distinction usually does not matter in impartial theory, because the value is what allows positions to be added and the outcome falls out of it — but here the adding is exactly what does not work, so the value has lost the job it was for. What remains of it is a number that varies with the lengths of components the outcome does not care about, and nothing in the essay uses it.

What was measured and what was not #

The walk covers every position that is a handful of chains and loops inside a budget of fifteen strings — 207 positions, 53 distinct shapes, chains up to five boxes and loops of four and six. That is a small window and it should be described as one.

What it establishes firmly is the failure. A single pair of components worth nought whose sum is worth something is a counterexample to the nim-sum, and there are 96 of them here rather than one. Nothing about a larger board could repair that.

What it establishes less firmly is the law. A parity rule that holds on 207 positions is a parity rule that holds on 207 positions, and the honest statement of its status is that it has had 207 chances to fail and has not taken one. The components it has been tested on are short — the longest chain is five boxes — and a real endgame has chains of eight and ten in it. The construction gives every reason to expect the law to keep holding, since the length of a long component never enters the argument for why the flip happens, and no reason at all to be certain.

Extending the window is not free and the reason is worth knowing if anybody wants to. The walk is over subsets of strings, so a position of k strings costs on the order of two to the k, and each of those masks needs a search over whole turns rather than single moves. Fifteen strings is a few minutes. Twenty would be an hour or two and would add chains of eight; the shape of the answer would not change and the confidence in it would.

What this is an instance of #

Nimstring is not the only place the theorem’s second condition fails, and the pattern is worth carrying.

Any rule of the form and then the same player moves again breaks disjunctive sums, because the extra move can be taken anywhere. That is Dots and Boxes; it is also every game with a capture-and-continue rule, and it is the same structural failure as a pass is not a move approached from the other side — there, a move that does not change the position; here, a move that does not pass the turn. Both are moves that fail to do the one thing the sum theory needs a move to do.

Where the impartial theory stops collects the boundary cases, and this is a sharper one than most, because everything that usually signals trouble is absent. The game is impartial. The components are genuinely independent. Every position terminates. The values exist and are easy to compute. Nothing looks wrong until the nim-sum is checked against a position with two components in it and comes out wrong on a third of them.

The general lesson is about what a decomposition licenses. Which part to move in is a question that presumes the answer is a comparison between parts; splitting is a move is about a game where the components change. Here the components never change and are never confused, and the sum still fails — because the parts of a position being independent is not the same statement as the turns being independent, and only the second is what the theorem is about.

That last position is the whole essay in one picture. Three components. Each is worth nought. There is nothing to add up, and there is nothing to add them with, and the answer is nevertheless completely determined — by a count of things the position does not contain.