The rule a smaller move breaks

Taking from several heaps at once is Moore’s generalisation of Nim: a move takes a positive amount from at most $k$ heaps rather than from one, and the position is a loss for the mover exactly when the heaps written in binary have every column summing to a multiple of $k + 1$. At $k = 1$ that is Bouton’s condition and the columns sum modulo two, which is the nim-sum.

The clause it does not touch is how much. A move may empty a heap of a thousand, and the rule’s proof leans on that: the strategy it describes needs to be able to reduce a heap to any value below it.

The rung below closed by naming the version that takes the freedom away:

Bounding the amount at m counters over at most k heaps gives a family whose k = 1 slice is an ordinary subtraction game and whose general member nobody here has evaluated, and the interesting question is whether the column condition survives at all once a move cannot empty a heap.

It does not survive, and the way it fails is worth more than the failure.

The game, and the two rules that already answer it #

A position is five heaps. A move picks at most $k$ of them and takes between one and $m$ counters from each. Normal play: whoever cannot move loses, which here means the position with every heap empty.

Two corners of the family are already settled and neither is settled by this page.

At $m$ large enough to empty the largest heap, the cap does nothing and the game is Moore’s. The column condition holds because Moore proved it holds.

At $k = 1$, a move touches one heap, so the game is the disjunctive sum of five subtraction games with subtraction set $\{1, \ldots, m\}$. A single such heap has Grundy value $n \bmod (m+1)$ — the residue is the value — and the Sprague–Grundy theorem says the sum is the nim-sum of the parts. Reducing each heap modulo $m + 1$ and taking binary columns modulo two is therefore not a repair at all; it is the theorem, written out.

That second corner is the control. The census asserts it, and a run in which the $k = 1$ rows came out anything but exact would be reporting a bug in the move generator rather than a fact about the game.

What the search is #

Nothing here is quoted. The outcome of every position is computed by the recursion the whole site runs on: a position is a loss for the mover when every legal move leads to a win for the opponent, memoised on the sorted heaps together with $k$ and $m$.

The bounded move rule is stated separately from the unbounded one rather than as a special case of it, and that is deliberate. Moore’s game is defined by a move that may empty a heap, so a cap is a change to the game rather than a parameter of it, and writing the two apart keeps that distinction where the rules are rather than where the arithmetic is.

The two are checked against each other where they must agree — a cap at or above the largest heap has to reproduce Moore’s game exactly — and that agreement is what the last section of this page measures.

The repair, and its failure #

The rule to test is the one both corners suggest. Reduce each heap modulo $m + 1$, because that is what a bounded subtraction game does to a heap; then apply Moore’s column condition to the residues, because that is what $k$ heaps at a time does to a position.

Over every position of five heaps up to nine counters — 2,002 of them — at three values of $k$ and four caps:

• $k = 1$: exact at every cap, all 2,002 positions, as it must be.
• $k = 2$: 1,603 of 2,002 at a cap of one, rising to 1,885 at a cap of four.
• $k = 3$: 1,778 rising to 1,964.

Eighty to ninety-eight per cent is the agreement rate of a rule that is wrong, not of one that is nearly right. Every rule in this subject that reads a position and guesses an outcome scores in that band, because most positions are wins and a rule that mostly says win is mostly correct.

Why nothing of that shape can work #

The interesting measurement is not the agreement rate. It is what happens when the positions are grouped by their residues.

If any rule of the form reduce each heap modulo $m+1$, then read the residues is to work, the outcome has to be a function of the residues. So group the 2,002 positions by their multiset of residues and ask whether each group has one outcome.

At $k = 1$ every group does — 6 groups at a cap of one, 126 at a cap of four, and not one of them contains both a win and a loss. At $k = 2$ and a cap of two, 15 of the 21 groups contain both.

The pair is as small as it could be. At $k = 2$ with a cap of one, the position 0 0 1 1 1 is a loss and 0 1 1 1 2 is a win; reduced modulo two both are 0 0 1 1 1. A heap of two and a heap of nought are the same residue and are not the same heap, because a heap of two survives a move and a heap of nought does not — and with the cap at one, surviving is the whole of what a heap does.

That rules out a family rather than a candidate. No amount of ingenuity in the reading step recovers information the reduction has thrown away. The failures of the particular column rule above are a symptom; this is the finding.

What the reduction destroys, and why $k = 1$ is exempt #

The reduction is legitimate at $k = 1$ for a reason that names exactly what goes wrong at $k = 2$.

At $k = 1$ the heap is a component of a disjunctive sum. Its Grundy value summarises it completely, because the only thing the rest of the board can ask a component is what it is worth, and two heaps with the same value are interchangeable in any sum — that is what equality in every company means and it is the content of the theorem.

At $k \ge 2$ a move reaches into two heaps at once, so the heaps are not components of a sum. There is no theorem entitling a heap to be replaced by a summary, and the census shows the entitlement is genuinely absent: a heap of two and a heap of nought behave differently in the same company, which under a disjunctive sum could not happen.

This is the same failure independence is a claim is about, arriving from the other side. There a board is split into parts and the question is whether the parts are parts; here the parts are given and the move refuses to respect them.

The heap that is not its residue #

It is worth staying with the witness for a paragraph, because the mechanism is visible in it and generalises.

With a cap of one counter, a heap of two and a heap of nought have the same residue modulo two and could hardly be more different. The empty heap is finished: nothing can be taken from it and it contributes nothing to any move for the rest of the game. The heap of two survives being moved in, and survives it twice.

In the unbounded game that difference is invisible, because a heap of two can be emptied in one move and so is one move away from nothing. The cap is what makes surviving a move a property, and it is a property no residue records.

And the number of heaps a move touches is what makes the property matter. At $k = 1$ the difference is confined to its own component and is summarised away by the component’s Grundy value; a heap of two under a cap of one has value nought, and having value nought is exactly being interchangeable with an empty heap in a sum. At $k = 2$ there is no sum, the interchange is not licensed, and the census finds it failing at the smallest position where it could.

The cap lifted #

The other way to watch the rule fail is to leave it unrepaired and lift the cap.

Moore’s condition agrees on 1,646 of the 2,002 positions at a cap of one and climbs steadily — 1,777, 1,874, 1,909, 1,931, 1,956, 1,974, 1,985 — reaching all 2,002 at a cap of nine, which is the largest heap in the census.

The climb is not a rule getting better. It is a wrong rule meeting fewer positions that expose it: as the cap rises, fewer heaps are small enough for the cap to bind on them, so fewer positions differ from the Moore position they would be if the cap were absent. The rule becomes exact at the moment the cap stops binding anywhere and not one counter earlier, which is the behaviour of a hypothesis rather than of an approximation.

That distinction matters for how the eighty-per-cent figures above should be read. A rule at 96 per cent that is 100 per cent as soon as its hypothesis holds is a rule with a precondition, not a rule with an error term.

Refuting a rule against refuting a family #

There are two things a sweep like this can establish and they are worth keeping apart, because the second is much rarer and it is what happened here.

Refuting a rule means finding a position where the stated rule gives the wrong answer. That is easy, it is what a counterexample does, and the natural response is to repair the rule — add a case, adjust a modulus, handle an exception.

Refuting a family means showing that no rule of a given shape can work, which needs a different argument: two positions that the rule’s inputs cannot tell apart and whose outcomes differ. Then every rule reading those inputs assigns them the same answer and one of the two answers is wrong, whatever the rule is.

That is what the residues do here. At $k \\ge 2$ there are positions with identical residues and different outcomes, so the residues do not determine the outcome and no function of them decides the game — not the obvious rule, not a corrected one, not one nobody has written yet.

So the right response is not to repair anything. A repaired rule reading the same inputs is refuted by the same pair of positions before it is written, and the sweeps above are wasted effort on any candidate of that shape. What has to change is the input: some quantity outside the residues, which the rungs above go looking for and eventually find in a parity statistic over the whole position.

The general instruction is worth taking away. Before repairing a rule, check whether its inputs separate the cases — because if they do not, every repair fails identically and the search should move one level up rather than one step sideways.

What is left, and what it would take #

The negative result is sharp and it leaves the positive question open in a well-defined place.

The outcome of a bounded Moore position is a function of the heaps, obviously, and the census computes it by search. What it is not a function of is the residues, so any solution has to look at the heaps themselves — and the natural next candidate is a two-part statistic: the residues together with something recording which heaps are small enough for the cap to bind.

The witness above suggests the shape. 0 0 1 1 1 and 0 1 1 1 2 differ in that the first has two dead heaps and the second has one dead heap and one heap the cap binds on. A statistic that counted heaps by residue and by whether they exceed the cap would separate them. Whether such a thing composes into a condition is not something 2,002 positions can settle, and it is what the rung above is.

What the census does not say #

Four limits.

Five heaps, nine counters. The sweep is 2,002 positions and the failures are found in the first handful of them, so the negative result is not delicate. What a small board cannot say is whether the proportion of split residue classes means anything — it moves from 71 per cent to 34 per cent as the cap rises at $k = 2$, and that movement is about how many positions the cap binds on rather than about the game.

Three values of $k$ and four caps. The pattern is uniform across the twelve rows and there is no reason to expect $k = 4$ to behave differently, but no reason is not a check, and $k$ beyond the number of heaps is a degenerate game where every heap may be touched.

One convention. All of this is normal play. Misère bounded Moore is a different game, and the rung below is the essay about what the misère convention costs Moore’s rule — where the answer is a one-line patch and would not be one here.

The contrast is the reason both rungs sit on one anchor. A change to the ending moves a handful of positions and is patched by naming them; a change to the move removes the hypothesis the rule was proved under, and no clause reaches it. Misère play is where that distinction is set out in general.

And the negative result is about a shape, not about difficulty. No function of the residues does not mean no rule. It means the reduction that works at $k = 1$ is not available, which is a statement about one route rather than about the destination.

The convention, named #

Normal play throughout: the player who cannot move loses. Every position is a multiset of heap sizes, empty heaps kept, and positions equal up to reordering are one position.

Moore’s $\mathrm{Nim}_k$ permits a move to take a positive amount from between one and $k$ heaps. The bounded game additionally caps each of those amounts at $m$; a move must still take at least one counter from each heap it touches, so a move touching two heaps takes between two and $2m$ counters in total.

The column condition writes every heap in binary, sums each column over the heaps as ordinary integers, and asks whether every column sum is divisible by $k + 1$. At $k = 1$ that is the nim-sum being nought, and the phrase a carry would ruin it in the figure is the whole reason the columns are summed separately.

Where the ladder goes next #

The moores-nim anchor has three rungs: Moore’s rule with its proof checked over every position it claims, the same game under the misère convention, and now the same game with the amount bounded, where the rule does not merely need patching.

The rung above is the two-part statistic. The census has, for every position, the residues, the count of heaps the cap binds on, and the true outcome, so testing a candidate is a filter over data already in hand rather than a new search. The interesting outcome is a rule that works at $k = 2$ and fails at $k = 3$, because that would say the difficulty is about the number of heaps a move reaches and not about the cap.

Two neighbours are worth the trip. Every impartial game is a Nim heap is the theorem that makes the $k = 1$ row a foregone conclusion, and reading it beside this page shows exactly which of its hypotheses a two-heap move removes. And where the impartial theory stops is the general account of what one number per position can carry, of which this is a small and unusually clean example: the number is right, the position is not a component, and the theorem was never about games like this one.