One value more than Nim

A move that must be answered put a crack in the foundation that every argument about sums rests on. In Top Entails a player may take the top coin of a heap, and then the opponent must move in that same heap; or split a heap in two, which compels nothing. The independence the disjunctive sum rests on — a move in one part leaves the others alone and the reply may go anywhere — is exactly what an entailing move denies. Run the ordinary theory anyway, give each heap the Grundy value the mex rule computes when the compulsion is ignored, and the nim-sum misreads nine of thirty-six two-heap positions. Two heaps of two, which any impartial game the ordinary theory covers would call a second-player win, are a first-player win.

That essay found the rule Top Entails alone obeys — an even heap wins for whoever moves, and otherwise the heaps of one decide by parity — and named the obvious next question: a value system in which loony is a first-class citizen, and a decomposition theorem that survives compulsion. The rule it found might have been a fact about one game. It is the first instance of a theory, and the theory is small.

A value read off the heap itself #

The ordinary theory gives a heap a value by recursion: the mex of its options’ values. That recursion is what the compulsion breaks, because an option in which the opponent is compelled is not a position the ordinary theory has a value for. So the value here is read another way, one that makes no assumption about how the game is built: put the heap beside a Nim heap and see who wins.

If some Nim heap of size $k$ makes the pair a loss for the player to move, the heap behaves like $∗k$ against Nim, and $∗k$ is its value — that is the test the Sprague–Grundy theorem would apply to any impartial position, since $G + ∗k$ is a loss exactly when $G$ equals $∗k$. If no Nim heap makes the pair a loss — if the player to move wins beside every Nim heap tried — then the heap is worth nothing a nimber can be. It is loony, the name Winning Ways gives to a position that wins for the mover in any company.

Two games are valued this way. Top Entails is as before. The second, entailing Nim, is Nim with one clause added: take any number of counters from a heap, and a take of exactly one counter that leaves the heap non-empty compels the reply in that heap. It is a different game with a different compulsion and the same question.

The hero table is the answer, and it is the same shape for both. Every even heap is loony. Every odd heap is a nimber. In Top Entails a heap of one is worth ∗ and every larger odd heap is worth nought; in entailing Nim an odd heap of $h$ is worth $∗\tfrac{h+1}{2}$ — a heap of seven is worth ∗4, a heap of eleven ∗6.

One rule for every sum #

Values are only worth having if they add, which is the whole content of Nim and the nim-sum for ordinary impartial games. The rule is the obvious one, with loony given the only reading it can have: a sum with any loony part is a win for the player to move; otherwise it is a win exactly when the nim-sum of the parts’ values is not nought.

Every position here is solved outright by searching the game — each compulsion honoured, each reply made where it must be — and compared with what the rule predicts from the parts’ values alone. Top Entails heaps beside Nim heaps: 1,322 sums, no error. Entailing Nim beside Nim: 1,322, no error. The two entailing games and Nim mixed in one sum: 1,372, no error. Four thousand and sixteen positions, with heaps up to seven and up to five parts, and the parts’ values decide every one of them.

A position read with the rule shows how little it asks. Take Top Entails heaps of three and five, a Nim heap of one and an entailing Nim heap of seven. The values are nought, nought, ∗ and ∗4; nothing is loony, and the nim-sum is ∗5, so the player to move wins. The rule also says how: change one part so the nim-sum becomes nought, and the part to change is the entailing Nim heap, from ∗4 to ∗. The heap of seven worth ∗ is a heap of one, so the winning move is to take six counters — a take of more than one, which compels nothing. The search confirms that the position after that move is a loss for the opponent. The natural-looking alternative, taking one counter from the heap of seven, compels the opponent to reply in a heap of six, and the search says the opponent then wins: the move leaves an even heap, loony, and hands over the pass. Removing the Nim heap instead leaves nought, nought and ∗4, and the opponent wins that too.

That is a decomposition theorem surviving compulsion, in the form the earlier essay asked for. The compulsion does reach across the sum — it names the component the reply must go in — and yet a component can still be summarised by one value, provided the list of values has one element more than Nim’s.

The nine, repaired #

The failure that started the question is worth seeing repaired, because the repair is so local.

The ordinary Grundy values of Top Entails heaps one to six are 1, 2, 0, 2, 0, 2. The values read off the heaps are ∗, loony, 0, loony, 0, loony. They agree on every odd heap. Every disagreement is an even heap, where the ordinary theory says ∗2 and the heap behaves like nothing any nimber can be: two heaps of two have ordinary values 2 and 2, nim-sum nought, predicted a second-player win — and each is loony, so the mover wins. The nine wrong predictions are exactly the pairs in which an even heap’s ∗2 happens to cancel against something.

So the ordinary theory was not wrong about most of the game. It was wrong about one class of heap, in one consistent way, and the correction is to take those heaps out of the nimbers altogether.

A loony heap is a pass #

Why an even heap wins for the mover in any company is visible in one line of play.

Beside a Nim heap of any size, the mover takes the top coin of the heap of two, leaving a heap of one — and the opponent must move in that heap, so takes its last coin. The heap is gone, the Nim heap is untouched, and it is the first player’s turn again. Two moves were made and the rest of the board did not change: the first player has passed. And a player who can pass whenever they like wins any sum of ordinary games — faced with a losing position they pass, faced with a winning one they play it. That is what loony means, and the compulsion is what buys it: an entailing move is an offer the opponent cannot refuse, and here the offer costs the opponent a turn.

Beside nothing at all the pass is useless — there is nothing to pass back to — and the heap of two wins another way, by splitting into two heaps of one. It is loony because it wins in every company; the move that wins it changes with the company.

Entailing Nim’s even heaps are loony by the identical exchange. From a heap of two, take one counter: the heap is left with one, the take was of exactly one, so the opponent is compelled into it and must take the last counter, and the move comes back. From a heap of four the same take leaves three and compels a reply there, and it is the winning move beside every Nim heap from two upward; beside a Nim heap of one a plain take of three wins instead, and beside nothing the whole heap does. Two different rules, one mechanism, which is why the two columns of the hero table go loony on exactly the same heaps.

A larger even heap works the same way with a longer tail. Taking the top coin of a heap of four leaves a heap of three and compels the reply there; whatever the opponent does inside it, the position after is one the mover wins, whatever the Nim heap beside it. The even heaps are loony for one reason: each offers its owner a compelled exchange that returns the move.

Why a compulsion can be summarised at all #

It is worth asking why any of this works, because the essay before this one gave a good reason to expect it not to. An entailing move reaches across the sum and constrains the reply, and the whole disjunctive theory is built on replies being free.

The reason is where the constraint lands. The compelled reply must be made in the component just moved in, so the entailing move and its reply happen inside one component, one after the other, and the rest of the board sees neither. Viewed from outside, the pair is a single event in that component after which the same player is to move — a double move that stays at home. Everything else about the component is ordinary: its non-entailing moves are moves like any other, and they hand the turn over as usual.

So an entailing component is an ordinary component with an extra kind of option: an option that keeps the move. A component in which that option can be used to profit — where the compelled exchange leaves the component no worse for its owner — is a component that offers a pass, and a pass beats everything ordinary; those are the loony ones. A component in which every such exchange costs its owner is an ordinary component in effect, and the mex of its other options is its value. The compulsion never reaches the rest of the board, which is why the rest of the board can be summarised as usual, and why the whole sum needs only one value more than Nim.

It also explains the one surprise in the two-heap table: that in Top Entails the ordinary theory, run with the compulsion ignored, was right about every odd heap. There every option of an odd heap past one leaves an even heap, so the ordinary mex and the loony rule both see no option worth counting and both say nought. In entailing Nim the ordinary theory is wrong about the odd heaps too — it says a heap of seven is ∗7, and it is ∗4 — because there an odd heap has options to even heaps that the ordinary mex counts and the loony rule leaves out. The ordinary theory’s error is always the same error: counting a move that hands over the pass as if it were a move.

What the odd heaps are worth, and why #

The odd heaps carry nimbers, and the nimbers have a pattern with a reason behind it.

In entailing Nim an odd heap of $h$ is worth $∗\tfrac{h+1}{2}$. That is exactly what the mex rule gives if every option that leaves an even heap is left out of the count: the remaining options are the odd heaps below $h$, worth ∗1 up to $∗\tfrac{h-1}{2}$, and the empty heap, worth nought, and their mex is $\tfrac{h+1}{2}$. In Top Entails, every move from an odd heap past one leaves an even heap somewhere — taking the top coin leaves one, and splitting an odd heap always makes an even part — so the same rule leaves no options at all and the value is nought. Only the heap of one, whose top coin empties it, escapes, and it is worth ∗.

So there is a rule for the values too, and it is Nim’s rule with one exclusion: a move to a loony position does not count. That is intelligible. A move that leaves a loony heap on the board hands the opponent the pass, and a player who has the pass wins; such a move is never the answer to anything, so the value has no need to account for it. The word comes from Dots and Boxes, where the game in every exercise book is played on the same structure: a move that offers a long chain is loony, because the opponent can take all but two boxes and hand back the move, keeping control, and four boxes for every chain after the first is the price that control commands. The chains decide it meets the same exclusion in the counting, where a move that offers a chain is a move the opponent can turn into a free tempo, and a player counting chains simply does not consider it.

How the positions were searched #

A position is a list of heaps, each marked with its game — Top Entails, entailing Nim or Nim — together with the heap the player to move is compelled into, if any. The search tries every legal move, with the moves restricted to the compelled heap when there is one, and a take that empties a heap compels nothing, the convention a move that must be answered adopts. A heap’s value is read by pairing it with Nim heaps from nothing up to sixteen, which is far past the largest nimber any heap here reaches. The rule is then tested only on free positions, where no compulsion is pending, because those are the positions a value describes.

What the tables cannot show #

Two entailing games are two. Both compel the reply in the component just moved in, and both have the pass structure that makes even heaps loony. An entailing game in which the compelled reply could go somewhere else — in a named other component, say — is a different kind of compulsion, and nothing here says the two-element extension survives it.

The values are read against Nim. A heap’s value is defined as the Nim heap it balances, and the rule is tested in sums of entailing heaps and Nim heaps. A value read against Nim that failed in company with some other ordinary game would be a value that happens to agree with Nim, not a value; the mixed sums here include only these three games.

And positions in mid-compulsion have no value here. The rule describes free positions. A position in which the mover is compelled into a heap is a different object — its outcome depends on that heap alone — and the theory as stated says nothing about it.

Still open: a compulsion that points elsewhere #

Both games here compel the reply in the same heap, which is what lets an even heap buy a pass: the compelled exchange stays inside the heap and returns the move. The next question is a compulsion that points elsewhere — a move in one component that compels the reply in a different one, as a move in one region of a board can force an answer in another. There the pass may be available to the wrong player, and the natural first measurement is the same one: read each component’s value off its pairing with Nim heaps, and test the rule on sums. If a two-element extension still decides them, loony is a general feature of compulsion; if it fails, the failure will say which part of the pass the theory depended on. What a component has to carry asked the parallel question for a held pass, and found that no short summary sufficed.