The patch that generalised

Taking from several heaps at once is Moore’s generalisation of Nim: a move takes a positive number of counters from between one and k heaps, and the losing positions are the ones every binary column of which sums to nought modulo k + 1. At k = 1 that is the nim-sum and the ordinary game.

The essay closed by naming the first rung above it:

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.

It takes a patch of exactly that shape, and the generalisation is forced rather than guessed.

The clause, and where it comes from #

The rule under test is two sentences:

• if some heap holds two or more counters, the mover loses exactly when every binary column sums to nought modulo k + 1;
• if every heap holds one counter, the mover loses exactly when the number of heaps is one more than a multiple of k + 1.

The second sentence is the patch, and it is not a guess. When every heap holds a single counter, taking any positive number from a heap takes the whole heap, so a move removes between one and k heaps and nothing else — the position is a subtraction game on the count of heaps with the set {1, …, k}.

That game is elementary. Under normal play the losing counts are the multiples of k + 1: leave a multiple and whatever the opponent takes, complete it back to a multiple. Under misère the losing counts are the counts one more than a multiple, by the same argument aimed one heap short.

So the clause has the same modulus that the normal-play rule already carries, and at k = 1 it reads the mover loses when the number of heaps is odd, which is Nim’s misère rule.

How little of the board it changes #

The rule is checked on every multiset of at most six heaps of at most six counters: 923 positions per value of k, solved directly by the misère recursion with no rule assumed.

The patched rule is right on all 923 at k = 1, 2 and 3 — asserted rather than reported, so a single position it missed would stop the build.

The unpatched normal-play rule is right on 917, 919 and 920. So reversing the ending changes the answer on six positions out of 923 at k = 1, four at k = 2 and three at k = 3.

Six of 923 is two thirds of one per cent. The whole of what misère play does to Moore’s Nim is a handful of positions in which every heap holds a single counter, and there are only six such positions in the sweep because a position of all ones is determined by how many heaps it has.

That is worth stating in the strong form. The two conventions differ on the six positions the clause is about and agree on the other 917, and the six are exactly the positions with no heap of two or more.

Why this game and not most games #

A patch of one clause is a piece of extraordinary luck by the standards of misère play, and it is worth saying why Moore’s Nim gets it when almost nothing else does.

The obstruction to misère analysis in general is that the outcome of a sum is not determined by the outcomes of its parts, so a game has no values and needs a quotient instead. Nim escapes because it is one of the tame games: its positions play, in a misère sum, exactly as Nim positions play, and the ending only matters at the very bottom of the game where all the heaps have shrunk to one.

Moore’s Nim inherits that for the same reason. The normal-play rule is about binary columns and the columns are unaffected by which convention is in force; what the convention decides is who wants the last counter, and wanting the last counter only changes a decision when there is exactly one counter left to want in each heap.

A game whose ending matters only at the ending is a game whose misère analysis is a boundary condition. That is the class Nim is in, and Moore’s rule turns out not to leave it.

The modulus is the same modulus #

The part of the finding worth carrying is not that a patch exists but that the patch reuses the number the game already had.

There is no reason in advance for the misère clause and the normal-play rule to share a modulus. The normal-play condition is about binary columns and the k + 1 in it comes from Moore’s argument about how many columns a move can disturb; the misère clause is about a count of heaps and its k + 1 comes from a subtraction game on the integers. Two arguments, two appearances of the same number, and no shared step.

They coincide because both are counting the same thing: how many heaps a single move can reach. Moore’s normal-play argument needs the column sums to be restorable after any move that touches at most k heaps, which is what modulo k + 1 arithmetic gives; the all-ones subtraction game needs the count of heaps to be restorable after any move that removes at most k of them, which is the same requirement one level up.

So the game has one number in it and both halves of the analysis find it. That is the sort of coincidence which, once explained, stops being one.

The same reading explains why the clause is about heaps of one rather than about heaps of any other size. A heap of two admits a move that leaves a heap of one, so a position with a heap of two still has a lever inside a single component; a position of all ones has no levers inside components at all, and every move is a decision about how many components to remove. That is the moment the game stops being about columns and starts being about a count, and it is the only such moment.

The rule that has never rejected anything #

A rule right on 923 of 923 is a rule that has not been tested, unless something has tried to break it, and two things have.

The first is the unpatched rule, run on the same positions. It is right on 917 and wrong on six, and the six are exactly the positions the clause is about — so the clause is doing work rather than restating what was already true. A patch that changed no answers would be indistinguishable from no patch at all, and the count of disagreements is the evidence that it is not.

The second is the choice of k. At k = 1 the two rules differ on six positions, at k = 2 on four and at k = 3 on three, and the falling count is itself a check: the larger k is, the more counts of heaps are already losing under both readings, so the clause has less to correct. A patch whose effect did not shrink with k would be describing something other than the all-ones boundary.

Neither of those makes the rule a theorem and together they make it a rule that has been asked to fail. The argument for it, in the second section, is short enough to be checked by hand and is the reason to believe it rather than the sweep.

What a player has to remember #

Reduced to what somebody at a table would need, the whole analysis is three lines.

Compute the column sums modulo k + 1. If they are all nought and some heap has two or more counters, the position is lost; move to make them all nought otherwise. When the position becomes all ones — and a player can see that coming — switch to counting heaps modulo k + 1 and aim to leave a count one more than a multiple.

The switch happens once, near the end, and the position at which it happens is visible. That is the whole difference from normal play, and it is the reason misère Moore’s Nim is a game somebody can actually play well rather than a game with a quotient.

There is a small honest caveat on the word visible. Seeing the switch coming means seeing that the position is about to become all ones, and a player one move away from that can see it; a player five moves away has to plan for it, and planning for it means steering the column arithmetic so that the count of heaps comes out right when the last big heap goes. That is a second-order consideration and it is the part that makes the game worth playing rather than computing.

The comparison to draw is with what misère play usually costs. Two misère outcomes are not enough is the general case, where the outcome of a sum is not a function of the outcomes of its parts and the whole apparatus of comparison collapses. Moore’s Nim pays nothing for the reversal but one clause and a moment’s attention.

What would have broken it #

It is worth being concrete about the failure the rung below was expecting, because the shape of the near-miss says what the game is doing.

The obvious way for the patch to come apart is for the boundary to be wrong. Nim’s patch switches when every heap but one has size one — all heaps but one, not all heaps — because the last big heap can be trimmed to leave whichever parity is wanted. Stated that way, the natural generalisation is all heaps but one again, and it would have been the wrong generalisation: at k = 2 a move can take from two heaps, so a single large heap is not a single lever, and the position with one large heap and several ones is already covered by the column rule.

The clause that works is the plainer one — every heap at one — and it works because the column rule is still exact right up to that point. That is not obvious in advance and it is what the sweep establishes: 917 positions with a heap of two or more, and the normal-play condition correct on all of them under the reversed ending.

So the boundary is one step later than Nim’s phrasing suggests. At k = 1 the two phrasings prescribe the same play — a position with one heap above one is where the switch is made, and the position it is made into is a position of all ones — so the difference is invisible there. At larger k the earlier phrasing has no content, because a move touching several heaps at once means a single large heap is not a single lever, and the rule that survives is the one stated at the all-ones boundary itself.

Why a misère patch generalising is unusual #

Under the misère convention almost nothing transfers, so a patch that survives being carried to a wider family is worth remarking on rather than passing over.

The standard situation is the one misère play has no negatives sets out: there is no zero, no subtraction and no comparison, so a misère result is a result about one game and stays there. Misère Nim’s own patch — treat the all-ones position specially — is usually presented exactly that way, as a quirk of Nim to be memorised.

What makes it generalise here is that it is not really a patch about Nim. It is a statement about the endgame: the positions where every heap is as small as it can be while still being a position, and where the parity of how many of them there are decides who is left without a move. That description mentions the heaps’ sizes only to say they are minimal, so it survives any change to the rules that leaves the minimal positions alone.

Moore’s rule widens what a move may touch and does not change what a minimal heap is, which is why the same clause does the same job. A rule change that altered the bottom of the game — a cap on the amount, a floor on the heap, a move that must take from every heap — would break it immediately, and would break it before it broke anything about the normal-play analysis.

That is the useful diagnostic. A misère result transfers when it is a statement about the last few moves and does not when it is a statement about values, because the last few moves are what the convention actually changes and the values are what it destroys.

What the sweep does not say #

Three limits.

Three values of k. The rule is checked at k = 1, 2 and 3, over heaps of at most six. Larger k is the same computation and a slower one, since the move list grows with the number of heaps a move may touch; nothing here says the pattern continues, and the argument for the clause says it should, since neither half of the argument mentions k except through k + 1.

Heaps of at most six, and at most six of them. That is 923 positions, and the six the clause is about are six of them because there are six counts of heaps in range. A sweep with more heaps would have more all-ones positions and the same proportion of everything else.

Nothing here computes a quotient. A tame game’s misère analysis can be stated as an outcome rule, and that is what this page has; the finer object is the misère quotient, which says how positions of the game combine in a misère sum with anything else. Whether Moore’s Nim’s quotient is Nim’s — which is what tameness at these sizes suggests — is a computation this site’s machinery could make and has not.

And the patch is a rule about outcomes, not a value theory. It says who wins. It does not give Moore’s Nim a misère value, and the reason is the standing one: misère play has no negatives, so there is no group for the values to live in. A tame game gets an outcome rule and does not thereby get an arithmetic.

The convention, named #

Misère play: the player who takes the last counter loses. A move takes a positive number of counters from each of between one and k heaps, and heaps are unordered.

Every outcome is computed by the recursion over positions, memoised on the sorted heaps, with the base case that a player facing an empty position has won — which is the misère convention stated where it belongs, at the bottom of the recursion, rather than as a flip applied to a normal-play answer. The normal-play rule is evaluated independently, from the binary columns, and the two are compared.

Where the ladder goes next #

The moores-nim anchor has two rungs to here: Moore’s rule with its proof checked over every position it claims, and the misère patch that turned out to generalise.

The four rungs above follow one question — what happens when the amount is capped as well as the number of heaps — and it takes all four to answer it.

The rule a smaller move breaks tries the obvious repair, reducing each heap modulo the cap plus one before reading the base-$(k+1)$ columns. It is exact at every cap when $k$ is one and wrong at every cap when $k$ is two or three — and the reason is stronger than a broken rule: at $k \ge 2$ the residues do not determine the outcome at all, so nothing of that shape can work.

The wider move is the easier game tests four two-part statistics and none decides, and turns up something that contradicts the premise the request was made under: a move that may reach three heaps is more predictable than one that may reach two, at every cap, on every candidate rule, and after the change in base rate is taken out.

The count of odd heaps then finds the invariant, and it is a statistic of the whole position rather than of any heap: how many heaps hold an odd number. Every all-even position is lost, at every width of move, by a restoring strategy. And the parities in size order finishes it — sort the heaps largest first, read off their parities, and that five-bit word settles the whole game at every width of move, with the losing words forming a subspace.

So the anchor ends where this page’s patch pointed: the sizes matter, and they matter only as a sorting key. Every rule that reads them as numbers fails, and the one that reads them as an order succeeds completely.