A compulsion that points elsewhere

One value more than Nim repaired the damage a move that must be answered had done to the theory of sums. Two games with entailing moves — Top Entails, where taking the top coin of a heap compels the reply in that heap, and entailing Nim, where taking exactly one counter does — turned out to need only one value beyond the nimbers. Read each heap off its pairing with Nim heaps, and it is either a nimber or loony, a win for the mover in any company; then one rule decides every sum. The essay was clear about why it worked. The compelled reply is made in the component that compelled it, so the entailing move and its answer happen at home and the rest of the board sees neither. Its last section asked what happens when the compulsion points somewhere else.

The question can be put to the same two games by reversing one arrow. A move that would entail now compels the reply in some other heap, the replier’s choice which. It is the shape of a threat on a board — a move in one region that must be answered in another — and it is exactly the kind of rule the previous essay had no reason to expect to survive. In Dots and Boxes the compulsion stays in the chain, which is why a counting theory exists there; a board where an answer is owed somewhere else is the case nobody has counted. The two games then go opposite ways. Entailing Nim does not change at all. Top Entails loses the loony heaps, and then loses every value of the Nim kind: no assignment of nimbers to heap sizes explains its sums, and two sums are enough to show it.

The rule, and what a compelled player may do #

The moves are unchanged. In Top Entails a player either takes the top coin of a heap or splits a heap into two non-empty heaps; in entailing Nim a player takes any number of counters from one heap. The entailing moves are the same ones: in Top Entails, taking the top coin and leaving the heap non-empty; in entailing Nim, taking exactly one counter and leaving the heap non-empty. What changes is what they compel. The opponent’s next move must be in a heap other than the one just moved in, and any other heap will do. A move that empties a heap compels nothing, as before.

One case needs a convention, because the same-heap rule never met it: the compelled player may have no other heap to move in. Two conventions are measured, and they are both natural. Under the strict one, a compulsion that cannot be met is a move that cannot be made, so the compelled player has no legal move and loses. Under the lapsing one, a compulsion with nowhere to go is dropped, and the player may move in the heap after all. Every count here is made under both, because a result that held under one and not the other would be a fact about the convention rather than about the compulsion.

Values are read exactly as before: each heap beside each Nim heap from none upwards, and the heap’s value is the Nim heap beside which the pair is a loss for the player to move, or loony if there is none. The table above sets those values beside the same-heap ones. Two things leap out of it. Entailing Nim’s column pointed elsewhere is the column of the integers — a heap of seven is worth ∗7 under either convention, where with the compulsion at home it was worth ∗4 and every even heap was loony. And nothing in either game is loony any more. The pass is gone.

The pass is gone for the reason the previous essay gave for it existing. A loony heap of two was a heap whose owner could take the top coin, compel the opponent to take the last one, and have the move back with the rest of the board untouched. The pass was the compelled exchange staying at home. Send the compelled reply elsewhere and the exchange no longer closes: the opponent answers in some other heap, the rest of the board changes, and the turn has passed over in the ordinary way. A compulsion that points away from its own heap cannot buy a pass, because the thing it buys is a move somewhere else.

Entailing Nim does not notice #

That entailing Nim’s values become Nim’s is not a coincidence of ten heaps, and it can be proved in a paragraph — which is worth doing, because the reason is the surprising part.

Take any position of Nim heaps worth nought, and let the first player move in some heap, taking it from h counters to h′. The nim-sum is now $h \oplus h'$, which is not nought, and Bouton’s rule says a winning reply exists: find a heap holding the nim-sum’s leading bit and reduce it so the nim-sum is nought again. Could that heap be the one just moved? Only if reducing $h'$ could make the nim-sum nought, and the heap that does that is $h' \oplus (h \oplus h') = h$ — larger than $h'$. A heap can only shrink. So in Nim, the winning answer to any move is never in the heap just moved: it is always somewhere else, in a heap that holds the leading bit, and since the heaps’ nim-sum was nought before the move, the moved heap was not the only one with that bit.

That is the whole proof. A position worth nought is lost for the player to move whether or not they were compelled away from some heap, because every move hands the opponent a position whose winning reply is elsewhere — and pointing a compulsion elsewhere only restricts the replier to elsewhere, which is where the reply was going. A position not worth nought is won by Bouton’s move, which leaves a position worth nought. It holds under both conventions, for heaps of entailing Nim and plain Nim mixed. The compulsion reverses an arrow that the game was already following: Nim’s answers always pointed elsewhere, and a rule that says they must is a rule Nim had been obeying all along.

Top Entails admits no values at all #

Top Entails pointed elsewhere also has values read off pairs — under the strict convention a heap of h past one is worth $∗2(h - 1)$, which grows without bound where the same-heap values never exceeded ∗1 — and they decide every sum of two parts. In sums of three parts they fail, and not only sums of Top Entails heaps — 3 + ∗2 + ∗2, a heap of three beside two plain Nim heaps of two, is a loss its values call a win: 27 of 322 mixed and pure sums under the strict convention, 60 under the lapsing one, and every failure under the strict convention goes the same way, a loss the values call a win.

That alone would say only that the pair values are the wrong values. The stronger statement is that there are no right ones. A backtracking search over every assignment of nimbers below 32 to heap sizes one to seven, tested against the outcome of every sum of up to four Top Entails heaps of those sizes — 329 positions — finds none that works, under either convention. Not a different set of values, not a larger set of nimbers: nothing of the Nim kind describes this game’s sums. Run on entailing Nim the same search finds one immediately, and it is Nim’s.

Two sums are enough #

The search does not have to be believed, because the contradiction it found can be read off two positions.

Any value theory of the Nim kind gives every heap size a nimber and adds them by exclusive-or, and in such a theory two equal heaps cancel — the mirror was the floor of the whole subject, the one fact every impartial theory keeps. So two heaps of one beside a heap of three must be worth the same as the heap of three alone, and so must two heaps of two beside it. Top Entails pointed elsewhere refuses both at once. 1 + 1 + 3 is a win for the player to move and 2 + 2 + 3 is a loss. No nimber for a heap of three can make one of those positions worth nought and the other not.

The play shows why. In 1 + 1 + 3 the winning move is to take the top coin of the three, leaving 1 + 1 + 2 and compelling the opponent away from the two — into a heap of one, which is all there is elsewhere. Taking a heap of one empties it and compels nothing, so the opponent’s forced move hands back a free position, 1 + 2, which the first player wins. In 2 + 2 + 3 the same move compels the opponent into a heap of two, and a heap of two offers a good move: its top coin is itself an entailing move, and the opponent takes it and compels the first player away in turn. Every first move from 2 + 2 + 3 loses, the top coin of the three among them.

What the compulsion does to a pair is the point. A pair of equal heaps cancels in ordinary play because the second player can copy whatever is done in one into the other. A compulsion that points elsewhere can force a player to move into the pair — to break the symmetry first — and whether that is a cost depends on what the pair offers. Forced into a pair of ones, a player can only remove one of them, and that hands the opponent the position. Forced into a pair of twos, a player can take a top coin and send the compulsion back. Forced into a pair of plain Nim heaps of two, a player can take one of them whole and leave a heap of two beside a Top Entails heap of two, which balance. Under the same-heap rule a pair of equal heaps was two copies of a thing and nothing more. Pointed elsewhere, every heap is also a place a compelled player can be sent, and what a player can do on arriving there is a fact about the heap that the heap’s value does not record.

Where the failures sit #

The misread three-heap sums have a shape. Every one is a loss the pair values call a win, never the reverse, and beside a heap of three the failures run straight down the diagonal: three with two threes, two fours, two fives, two sixes, two sevens, each a loss though the equal pair should cancel and leave the heap of three, which wins alone. Two more lie off it, 3 + 3 + 5 and 3 + 4 + 6. Beside a heap of two the failures are fewer and lie one step off the diagonal — 2 + 2 + 3, 2 + 4 + 5, 2 + 6 + 7. The diagonal says the same thing as the contradiction, at every size the search reaches: a heap of three beside any pair of equal heaps of three or more is a position in which the first player’s compulsion can be absorbed, and a pair that ought to vanish decides the game.

The convention changes the outcomes, not the failure #

The strict convention has a cost that is easy to mistake for the cause. Under it a lone heap of two or more is always a win — take the top coin, and the opponent has nowhere to go and loses — so single heaps are trivial, and that triviality could be suspected of producing the contradiction. The lapsing convention removes it: a lone compulsion simply lapses, and the opponent plays in the heap. That changes 7 of the 329 outcomes; it makes a heap of three and a heap of seven losses on their own; it gives 1 + 4 and 2 + 6, two pairs of unequal heaps, as losses, which no mirror explains. And it changes nothing about the failure. 1 + 1 + 3 is still a win, 2 + 2 + 3 still a loss, and no nimbers exist. The contradiction is in the compulsion, not in the convention about its edge.

Why one game survives and the other does not #

The two games share the rule and differ in one thing: whether their good answers ever wanted to be at home. Nim’s never do, so forbidding them changes nothing. Top Entails’ sometimes do. With the compulsion at home, Top Entails was a game in which entailing exchanges closed inside one heap; pointed elsewhere, the exchanges spill into the rest of the board and travel from heap to heap, and the question of who wins depends on which heaps are available to carry them. That is the condition what a component has to carry used to sort broken sums. A component that needs to know its own history can be repaired by carrying more state, as what restores the theorem did for Fibonacci Nim once the heap was not the position. A component that needs to know a fact about the rest of the board cannot. A compulsion pointing elsewhere is a fact about the rest of the board in its purest form — the next move happens in some heap other than this one — and on Top Entails it destroys the sum in exactly the way that essay predicted for such rules.

Entailing Nim is the surprising exception, and it sharpens the prediction rather than refuting it. A rule that names the rest of the board breaks a sum only if the game’s play ever needed what the rule forbids. Whether a compulsion that points elsewhere is harmless is not a property of the compulsion. It is a property of where the game’s winning replies already are, and for Nim, which every impartial game is measured against, they are always somewhere else.

How the positions were searched #

A position is a list of heaps of one game, with or without plain Nim heaps beside them, and possibly one heap the player to move is forbidden to move in. The search tries every legal move; a move that would entail marks the heap it leaves as forbidden for the reply. Under the strict convention a player forbidden from the only heap on the board has no move and loses; under the lapsing convention that player may move in it. Values are read by pairing a heap with Nim heaps up to forty. The rule for sums is tested on every sum of up to three parts drawn from heaps of one to seven of the game and Nim heaps of one to four. The search for any assignment of nimbers tries every value below 32 for each heap size from one to seven against all 329 sums of up to four heaps of the game alone, extending a partial assignment only while every sum whose heaps are all assigned agrees. The smallest contradiction was found by testing every set of one, two and three sums of up to three heaps of size at most four for an assignment.

What the search cannot show #

Nimbers are not the only kind of value. The search rules out every assignment of nimbers added by exclusive-or. A value system of another kind — values carrying a flag for whether the heap can return a compulsion, say, and a rule for sums that consults the flags — is not ruled out by anything here, and the pattern of the failures suggests what such a flag would have to record. Whether a finite one exists is the question below.

Two games and two conventions. Both games compel the reply into any other heap. A compulsion naming a particular heap — the one to the left, the largest one — is a third kind, and it would change what a pair of equal heaps can do.

The proof for entailing Nim is about Nim. It uses Bouton’s rule, and the property it rests on — the winning reply is never in the moved heap — is checked here for Nim and for nothing else. Other games whose replies never stay at home would survive the same reversal for the same reason, but which games those are is not settled here.

Still open: what a heap must say about its company #

The contradiction says a Top Entails heap pointed elsewhere cannot be summarised by one nimber. It does not say how much more a summary needs. The failures are all one kind: a pair of equal heaps that does not cancel because it can send a compulsion back. A heap of one cannot, a heap of two or more can. So the natural next measurement gives each heap two numbers — its value when it is merely present and its value as somewhere a compulsion can land — and asks whether a rule on those pairs decides every sum, the way a pass is not a move asked how much a held pass forces a component to carry. If two numbers suffice, the compulsion that points elsewhere has a theory one size larger than Nim’s; if the required summary keeps growing with the heaps, then a rule that names the rest of the board takes the sum with it, and entailing Nim survives only because Nim never needed the sum to be told.