Taking from several heaps at once

Nim is heaps of counters and one rule: take any number from any one heap, and whoever cannot move loses. Bouton’s theorem settles it — write the heaps in binary, add each column without carrying, and the player to move has already lost exactly when every column cancels.

Now change one word. A move may take from any one to k heaps at once, any number from each, at least one counter in total. Ordinary Nim is k = 1; at k = 2 a player may empty two heaps in a turn. The heaps have stopped being separate objects that a move visits one at a time, which is the property the whole impartial theory is built on.

The answer barely moves. The columns are still where it lives, and only the divisor changes.

That is the whole of Bouton’s answer, and the rest of this essay is the same drawing with one number changed. Below the same three heaps are read again under Moore’s rule at k = 2, where a move may empty two of them, and the divisor becomes three.

The divisor that replaces the parity #

Bouton’s condition is usually stated as exclusive-or, which is doing something narrower than it looks. In each binary column the exclusive-or is zero exactly when the number of ones is even — divisible by two. Nim’s whole theory is a parity check applied column by column.

Moore’s condition is that sentence with the two replaced: the player to move loses exactly when, in every binary column, the number of ones is divisible by k + 1. At k = 1 that is Bouton, so nothing has been added to Nim and something has been added to the description of it. The two in “even” was never about binary; it was about how many heaps a move may touch.

Positions change sides in both directions. Three heaps of 5 are a win under ordinary Nim, nim-sum 5; under Moore’s rule with k = 2 they are a loss.

At three heaps and k = 2 the losing positions are exactly the eight equal triples in range — an echo of ordinary Nim on two heaps, where the losses are the equal pairs. In both cases a move touches at most k heaps out of k + 1, so one is always left behind to be copied. The echo does not survive an extra heap.

Why the divisor is k + 1 #

Half the argument is short enough to give in full, and it is the half that explains where the k + 1 comes from.

Suppose every column sum divides by k + 1, and take any legal move. It touches between one and k heaps and each of them strictly decreases. Look at the leftmost binary column in which anything changed. Every heap that changed there had that column as its own leading change, and a heap that decreases must turn a one into a zero at its leading change — so in that column ones became zeros and nothing became a one. The column sum drops by at least one and at most k, since at most k heaps moved, and a multiple of k + 1 cannot survive a drop of between 1 and k. No move from a divisible position reaches another one, and k + 1 is exactly the gap a move of k heaps cannot jump.

The other half — that every non-divisible position has a repairing move — is a greedy construction working down from the highest offending column, choosing heaps to reduce and never needing more than k of them. That is the counting half of Moore’s proof, and this site checks it rather than reproducing it.

The condition is genuinely parameterised, and raising k raises the divisor with it.

What the solver computed, and how #

The rule is easy to believe and easy to state slightly wrong, so it was not taken on trust. Separate machinery computes each outcome the hard way — enumerate every legal move, recurse, take the mex of the option values, call the position lost when that value is zero — and the column condition is evaluated independently and compared with it, position by position.

The last row is the headline: 54,264 positions of six heaps, 696 of them lost, and not one disagreement. It takes 25.4 seconds, which is why it is quoted rather than run inside a figure; the sweeps the figures run are the 120- and 330-position ones, at 3 and 40 milliseconds.

A comparison that agrees everywhere invites the suspicion that the two things compared were the same thing twice, so the same predicate was handed a wrong divisor. Read mod 2 at k = 2, the columns disagree with the search on 21 of the 120 three-heap positions, 63 of the 330 four-heap ones, 1,157 of the five-heap sweep and 4,168 of the six-heap one; read mod 4 they disagree on 7, 21, 240 and 913. Only k + 1 comes back clean.

A third check never searches the game at all. If the columns are independent, the number of ordered tuples that cannot move is a closed form: count the binary vectors of length n whose weight divides by k + 1, and raise that to the number of bits. At k = 2 with four heaps the qualifying vectors are the all-zero one and the four of weight three, so three bits predict 5³ = 125, and the search finds 125.

The lost positions, listed #

Counts can agree by accident. Lists of positions do not.

At k = 1 with three heaps up to 7 the fifteen losses are Nim’s familiar list, the equal pairs beside an empty heap together with (1,2,3), (1,4,5), (2,4,6) and their kin. At k = 2 with three heaps the eight losses are the equal triples; at k = 3 with four heaps, the equal quadruples.

At k = 2 with four heaps the pattern breaks. Fifteen positions are lost: (0,0,0,0), then (0,a,a,a) for each a up to 7, then (1,2,3,3), (1,4,5,5), (1,6,7,7), (2,4,6,6), (2,5,7,7), (3,4,7,7) — and (3,5,6,7), four different heap sizes with no repetition anywhere.

Where the search stops #

The exhaustive search has a ceiling, and the largest sweep that finished is the six-heap one above. The next attempted — k = 2, five heaps of at most 31 — was abandoned unfinished after 500 seconds, because move enumeration costs roughly maxHeap^k per position: raising the ceiling on heap size is far more expensive than adding a heap.

So the claim is exactly what was run, and it is not claimed that the rule has been verified for arbitrarily many heaps or arbitrarily large ones. The general statement is Moore’s theorem; this is evidence for it.

The rule decides the outcome and gives no value #

Here is what makes Moore’s Nim worth an essay rather than a footnote, and it is rarer than a reader would guess. Sprague–Grundy applies: Moore’s Nim is impartial, under normal play, with no infinite plays, so every position has a Grundy value, got as the mex of its options’ values, and that value is a nimber. The theorem is not in question. The question is whether the columns give it, as they do in Nim, where they spell the value out in binary.

They do not. Over the 330 positions of four heaps at k = 2 the column condition gets the outcome right 330 times out of 330; reading those same column sums as the digits of a base-3 number gets the value right on 42. At k = 3 the analogous reading is right on 17 of 330, and ordinary exclusive-or manages 19 of 330 and 25 of 330.

The failure is immediate rather than subtle. The first position that is not all zeros already breaks it: at k = 2 the heaps (0, 0, 2) are worth ∗2 while the base-3 reading says 3, and (0, 0, 4) are worth ∗4 while the reading says 9. At k = 3, (0, 0, 0, 4) is worth ∗4 and the base-4 reading says 16.

Where a Moore value actually comes from is the ordinary recursion and nothing else. Take (1, 1, 1) at k = 2: two distinct options exist — clear one heap, or clear two — worth ∗1 and ∗2, and the smallest non-negative integer missing from {1, 2} is 0, so the position is worth 0. Nothing in that computation reads a column, and the columns cannot be made to imitate it. The clearest demonstration is a position whose value is larger than any heap in it.

The cause is structural, and it is what Moore’s rule quietly costs. A Moore position is not a disjunctive sum of its heaps. In Nim a move happens in exactly one heap, the heaps are independent components, and the value of the whole is the nim-sum of the parts. Under Moore’s rule one move reaches into several heaps at once, which is exactly the hypothesis a disjunctive sum needs and this game does not have.

The numbers say it without any theory. Two heaps as one Moore position at k = 2, against the same two heaps as separate Moore games combined with a nim-sum:

Not close, and not wrong in a patterned way that some correction might repair.

What is lost is only the last step. In a game whose heaps are independent — an ordinary subtraction game, say, where a heap of 11 under take 1, 4 or 5 has options of 10, 7 and 6 worth 0, 3 and 2, so the mex makes it ∗1 — the nimber is not merely a label for the outcome. It is a substitution: a component of value ∗1 plays exactly like a Nim heap of one inside any sum, and that is what makes the theory compositional. All of that survives into Moore’s Nim except the sum, and without a sum a nimber has nothing to be substituted into.

So Moore’s Nim sits somewhere unusual: a complete, cheap, exact rule for the outcome of every position, and no usable value for the theory of sums. Where the impartial theory stops is about the partizan case, in which no nimber fits at all; this is the milder disease, in which nimbers exist and no formula produces them.

One measurement makes it concrete. Over the 120 three-heap positions with heaps up to 7 at k = 2 the largest Grundy value is 19, and at four heaps it is 25, where ordinary Nim never exceeds 7 — values running past the largest heap present, which rules out any formula that merely rearranges the heaps’ binary digits.

When there are no more heaps than k #

Exhaustive search did turn up one clean formula, in the corner where the game degenerates. When there are no more heaps than k, the Grundy value is the plain arithmetic sum of the heap sizes. Checked exhaustively: at k = 2 over the 7 one-heap and 28 two-heap positions with heaps up to 6; at k = 3 over the 7, 28 and 84 positions with one, two and three heaps; at k = 4 over 7, 28, 84 and 210 positions with up to four heaps.

The reason is short. With n ≤ k a move may reduce every heap at once, so every componentwise-smaller position is an option, every total from 0 to Σ − 1 is reachable, and the mex of {0, 1, …, Σ − 1} is Σ. The column rule agrees from the other side: no column sum can reach k + 1 without being zero, so the only divisible position is the empty one.

The claim dies the moment there is one heap more than k, and loudly rather than by drifting: at k = 2 with three heaps, (1, 1, 1) is worth 0 while its arithmetic sum is 3. That rejection is what makes the verification worth anything, since a predicate that has never refused a case has not been tested.

Set the two ends together and the family comes into focus. At k = 1 the value is the exclusive-or of the heaps; at k ≥ n it is their ordinary sum. Moore’s Nim interpolates between the two most familiar ways of combining a list of numbers, and strictly between them it is neither: at k = 2 with three heaps, exclusive-or is right on 15 of 120 positions and the base-3 reading on 14.

Two ways of adding moves to Nim #

The useful comparison is one essay away. Poker Nim also adds a move to Nim — a player may put counters back onto a heap from a private reserve — and it changes nothing: the nim-sum still decides the game, because a move that hands counters back is answered by taking them off again, leaving the position identical and the opponent’s reserve one poorer.

Two rules, both fairly described as “Nim with more moves”, landing as far apart as they could. Poker Nim’s addition is reversible, so canonical form discards it; Moore’s destroys the independence of the components, which is what the whole nim-sum apparatus rests on. The question to ask of a new rule is not how large the change looks but whether a move still lives inside one component.

Who found it, and when #

Eliakim Hastings Moore published the generalisation in the Annals of Mathematics in 1910, eight years after Bouton’s paper in the same journal had settled ordinary Nim. It is an early instance of the move this subject makes constantly: take a solved game, find the parameter hidden inside the solution, and turn it.

What he found is sharper than a generalisation for its own sake. Bouton’s rule looks like a fact about binary arithmetic; Moore’s version shows that the algebra is incidental and that the two in it counts heaps per move. Nim’s solution had a free parameter nobody could see while it was set to one.

The rest stayed open far longer. The outcome rule was complete in 1910; the Grundy function the measurements above keep failing to find a formula for was still being worked on seventy years later, by Jenkyns and Mayberry, in a paper whose title advertises the difficulty rather than a closed form. The distance between “solved” in the outcome sense and in the value sense is what three different claims are all called solved is about, and this is one of the cleanest specimens of it.

What the picture cannot show #

Every figure here draws one position — heap sizes, binary rows, column sums, verdict — and what one drawing cannot show is the quantifier. The claim is about every position in a range — that no move from a divisible position reaches another, and that every non-divisible position has a repairing move. Those are statements about the move graph, and even the 330-position sweep has far too many edges for a page. The figures compensate by printing the sweep as text: positions swept, disagreements found, and the counts for the two neighbouring divisors beside them, so the promise is falsifiable at a glance. It is a promise rather than a picture.

The second invisible thing is the value. Every column figure prints the position’s nimber in its footer and says the columns did not produce it: 3, 5, 6 at k = 2 shows three column sums of 2 and a verdict of “wins”, while the ∗14 comes from a mex over 50 options whose values run from 0 to 13, and no arrangement of the drawn digits yields 14. One frame carrying both, with only one of them derived from the drawing, is the honest version of this essay’s finding.

The convention, named #

Normal play throughout. Whoever cannot move loses, and every outcome, Grundy value and table entry above is computed under it. No sweep here was run under anything but normal play. Misère Moore’s Nim is a different game with the same rules and nothing above says a word about it; misère play changes Nim’s own answer, and there is no reason to assume the k + 1 condition survives intact.

Three conventions about the move rule matter as much, because changing any of them changes the answers.

A move takes from between one and k heaps and must remove at least one counter overall. Taking nothing from every heap is not a move, so a player who is stuck really is stuck — which is what makes the game finite and gives the recursion its bottom.

The amounts taken from different heaps are independent, and unbounded. A move may take one counter from one heap and all of another, which is why enumeration costs maxHeap^k per position.

Heaps are unordered. Every sweep above walks sorted positions, so (1, 2, 3) and (3, 2, 1) are one position, while the closed form predicts 125 ordered tuples where the sorted list has 15 entries. Confusing the two is the easiest arithmetic mistake available here.

Where the ladder goes next #

Three further rungs stand open on this anchor, and the machinery above can be pointed at each.

Misère Moore’s Nim. Ordinary Nim’s misère rule is a one-line patch — play the normal-play strategy until all heaps but one have size one, then invert — and the question is whether the k + 1 condition takes a patch of that shape or comes apart. The apparatus is the misère quotient, and what a next essay needs exists here already: a search evaluator that can be re-run under the misère convention, and a candidate rule to test against it.

Moore’s rule under a bound on the total taken. Moore bounds the number of heaps a move may touch and leaves the amount free. Bounding the amount too — at most m counters over at most k heaps — gives a family whose k = 1 slice is an ordinary subtraction game with a periodic Grundy sequence, and whether the column rule degrades into periodicity or is replaced outright has a small enough search space to settle.

Which take-away rules have column invariants at all. The widest of the three. Both games here have a condition of the form “read the heaps in binary and check every column against a fixed modulus”, and what that requires of a move rule is not obvious. Touching at most k heaps and only decreasing them is sufficient, by the argument in this essay’s second section; whether it is necessary is unknown here, and the way to attack it is to enumerate small rules, sweep small positions, and look for the ones some modulus fits.

Two neighbouring questions belong elsewhere: whether Nim-like tameness survives the extra move is for the genus, in tame and wild, and whether compounds of Moore positions have predictable outcomes belongs with two misère outcomes are not enough.