The wider move is the easier game

Moore’s Nim lets a player take from at most $k$ heaps at once, and Moore’s rule says the loser is the player facing a position whose binary columns all sum to a multiple of $k + 1$. Cap the amount as well and the rule breaks; the rung below found that it breaks in the worst way available. Two positions with the same heaps modulo the cap can have different outcomes, so no rule that reduces each heap and then reads the residues can be written, however the reading is done.

That page closed on the repair the census makes cheap:

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.

Four second parts are tried here and none of them works. And the outcome the request was hoping to distinguish is the wrong way round: $k = 3$ is the easier game.

The four second parts #

A rule of this shape sorts the 2,002 positions — five heaps of up to nine counters — into classes and answers each class with one outcome. It works when no class holds both a win and a loss. The residues alone are the rung below’s rule and they fail; each candidate here adds one number to them:

• how many heaps the cap binds on, which is the count the rung below named;
• how many heaps are not empty, which is the crudest measure of how much game is left;
• how many whole caps the heaps hold between them, the total of the quotients — the information the residues throw away;
• the largest heap, which is what a player looks at first.

Each is paired with the residues rather than used alone, because the residues are known to carry real information at $k = 1$ and the question is what has to be added to them.

The control matters more than it looks. At $k = 1$ every candidate decides every class, which is Sprague–Grundy doing the work and not the candidate; a census whose control failed would be measuring the move generator rather than the game.

None of them decides #

The rung below’s table is the thing being repaired, and it is worth having in view.

At $k = 2$ the residues alone leave 875 positions in ambiguous classes at a cap of one, 1,316 at a cap of two and 1,374 at a cap of three. Adding a second count moves those figures about and never to nought. The best of the twenty combinations tried — the residues with the largest heap, at a cap of one — leaves 370 of 2,002 positions in classes containing both outcomes.

The witness is small enough to check by hand. At $k = 2$ with a cap of one, the heaps $0\,0\,1\,1\,3$ lose for the mover and $0\,1\,1\,2\,3$ win. Modulo two both are $0\,0\,1\,1\,1$; the largest heap is 3 in both. Every quantity the rule reads is the same and the answers differ.

That is the rung below’s finding surviving one more layer. Adding a second statistic to a statistic that has already thrown the information away does not put the information back — it partitions the same classes more finely and leaves the same pairs together, because the pairs agree on the new number too.

The reach, and the surprise #

The prediction was a rule right at $k = 2$ and wrong at $k = 3$, on the reasoning that a move touching more heaps is a harder game. Not one of the fifteen comparisons goes that way. Every rule at every cap is more nearly right at $k = 3$ than at $k = 2$: 13,782 ambiguous positions across the five rules and three caps at $k = 2$, and 3,609 at $k = 3$.

That is a sharp enough reversal to be suspicious of, and there is an obvious way for it to be an artefact.

Whether it is only the base rate #

Losses get rarer as the reach widens. At $k = 2$ with a cap of one, 364 of the 2,002 positions are losses for the mover; at $k = 3$ with a cap of three, 63 are. A game with few losses is a game where a class is unlikely to contain one, so any partition looks better — and a rule that ignores the position entirely and always says the mover wins scores 81.8 per cent at the first of those settings and 96.9 per cent at the second.

So accuracy is the wrong instrument, and the right one is the lift: how much of the distance between the do-nothing baseline and perfection a rule actually covers.

Adjusted this way the reading survives. The mean lift across the fifteen settings is 31 per cent at $k = 2$ and 55 per cent at $k = 3$, and 14 of the 15 individual pairs improve. The single exception is the residues with the largest heap at a cap of one, where the lift falls from 52.2 to 51.2 — a difference of one point, and it is reported rather than explained.

The count of hidden losses says the same thing more concretely. At $k = 2$ the best rule buries 181 of the 364 losses inside mixed classes — half the positions a player most needs to recognise. At $k = 3$ the best rule buries 42 of 63.

Why more reach is less game #

The mechanism is not mysterious once the loss counts are on the table, and it is worth separating from the statistics.

A larger $k$ means more moves from every position, so more positions have a move to a loss, so losses are rarer and further apart. In the extreme, a move that may take from every heap at once turns the game into one where nearly every position is a win in one move and the losing positions are a thin, highly structured set. Structure is exactly what a rule can catch.

The cap works the other way. It stops a move from clearing a heap, so a position that ought to be an easy win becomes a slow one, and the outcome comes to depend on parities several moves deep. The rung below’s title is right and this page sharpens it: the difficulty here belongs to the cap and not to the reach, and widening the reach undoes part of what the cap did.

That inverts the intuition the request was built on, and the intuition is one worth naming because it is common. A game where a move can do more is a harder game sounds obviously true and is a claim about the branching factor, which is about the cost of a search. It says nothing about whether the answer has a description — and here the two run in opposite directions: the game with more moves per position is the one whose losing positions are easier to describe.

What the ambiguity is made of #

One more cut through the same data says where the difficulty sits, and it is not spread evenly.

At $k = 2$ with a cap of one, the residues alone form six classes and two of them are mixed — but those two hold 875 of the 2,002 positions between them. The failure is not a scattering of awkward cases at the edge of the census; it is two enormous classes, each containing hundreds of wins and dozens of losses, and every candidate second part is an attempt to cut those two classes up.

Adding the largest heap cuts them into 46 classes of which four are mixed, holding 370 positions. That is real progress and it is progress of the wrong kind: the classes multiply faster than the ambiguity falls, and a rule with 46 classes that still cannot answer 370 positions is closer to a lookup table than to a condition. Pushed to its limit this is how every such attempt ends — a partition fine enough to decide everything is a partition with one position in each class, which is the search written out.

The quotient rule is the clearest case. Adding the total of the quotients at $k = 2$ and a cap of three makes 476 classes out of 56, and still leaves 79 of them mixed. More than eight times as many classes, and more mixed ones than the rule started with.

What a per-heap rule can and cannot see #

The four repairs refused here have a common shape, and stating it says what a fifth would have to avoid.

Every one of them reads the heaps and computes something from each of them separately — a residue, a bounded digit, a truncated binary column — and then combines the per-heap answers. That is the form Bouton’s rule has for ordinary Nim, and it is what makes the rule usable: a component states a number and the numbers are combined.

A rule of that form cannot distinguish two positions with the same multiset of per-heap answers. So the whole family is refuted at once by exhibiting two positions whose heaps agree under every per-heap reading anybody would write down and whose outcomes differ — which is what the census is doing when it reports a rule ambiguous rather than wrong.

That reframes the failure and it points somewhere specific. What a rule of this shape is blind to is anything about the position as a whole: how many heaps there are, how they compare with one another, how many of them share a property. Moore’s rule at $k$ is itself of the per-heap kind — it adds the heaps in base $k+1$ without carrying — and the bounded game breaks it, so the bounded game is asking for information the unbounded one did not need.

The direction that has not been tried here is therefore a statistic of the position rather than of a heap, and the reason it has not been tried is that no rule in the impartial literature has that shape. Bouton’s is per-heap, Sprague–Grundy’s is per-component by construction, and the whole apparatus is built to make a position the sum of its parts. A game where the answer is not a function of the parts’ answers is a game outside the apparatus, and the four failures above are what that looks like from inside.

What is left after this #

Nothing of the shape reduce, count, decide is going to work at $k \ge 2$, and this page has now spent four candidate second parts establishing that. It is worth saying plainly what that leaves.

The Grundy values are not the obstacle. They exist and are computed here; what does not exist is a description of them in terms of the heaps’ residues. Where the impartial theory stops is the general form of this — every impartial game has a Grundy value, and having one is not the same as having a formula for one.

A weaker question is still open and is worth stating. Every rule here is asked to decide — to have no mixed class at all. A rule that decided nine tenths of the positions and said look further on the rest would be worth having, and would be a different object: a filter, in the sense the pairing check is a filter for Cram. The best rule at $k = 2$ is exactly that with the wrong numbers attached, since it leaves 370 positions to the search and hides half the losses among them.

And the honest description of the bounded game is a search. The rung below and this one together rule out the family of rules anybody would try; they do not rule out a rule of some other shape, and no argument here says one cannot exist. What can be said is that it will not be read off the heaps one at a time, because the counterexample pairs agree on every per-heap statistic tried.

What the census does not say #

Four limits.

Five heaps of nine. The sweep is 2,002 positions and the whole census is a claim about them. A rule failing here fails, which is the direction that generalises; the reversal between $k = 2$ and $k = 3$ is a measurement on one population and could look different with twenty heaps, where the losses would be rarer still.

Four second parts is not every second part. Statistic is a word with no boundary, and a candidate built from something other than a per-heap count — the number of distinct heap sizes, say, or a weighted column sum — is untested here. The counterexample pairs are the thing to test any new candidate against, and they are two positions rather than a theorem.

A majority answer is not a rule. The accuracies above are computed by giving every class its commoner outcome, which requires knowing the answers first. They are an upper bound on what a rule of that shape could score and not a rule anybody could use.

And the caps are small. One, two and three, against heaps of up to nine. A cap of eight on heaps of nine barely binds, and the cap lifted is where the game returns to Moore’s — so the ambiguity measured here is the ambiguity of a strongly-binding cap.

The convention, named #

Normal play: the player who cannot move loses. A position is a multiset of heap sizes, since neither the order of the heaps nor which is which affects anything.

$k$ is how many heaps one move may take from and $m$ is the largest amount it may take from any one of them; a move must take at least one counter from at least one heap. The residues are the heaps modulo $m + 1$, which is what a bounded subtraction game’s Grundy values are at $k = 1$.

A rule decides when every class it forms carries a single outcome. That is a weaker demand than getting the answer right — it does not ask which outcome the class gets, only that the class has one — and it is the demand a rule of this shape has to meet before its reading can even be discussed.

One line is worth carrying. A game with more moves per position is not a harder game to describe — it is a game with fewer losing positions, and losing positions are what a description has to catch. The branching factor prices the search and says nothing about the answer.

Where the ladder goes next #

The moores-nim anchor has four rungs to here: Moore’s rule with its proof checked over every position it claims, the same game under the misère convention, the same game with the amount bounded, and now the family of repairs for that, tested and refused.

The rung above asks this page’s own closing question — what the 364 losing positions have in common as a set — and the answer is the shape this ladder had stopped expecting. The count of odd heaps finds an 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; the count settles every position at one heap a move and at four, and a little over half at two.

That is the Bouton shape at last — a property of the position that the moves respect, rather than a rule for reading the heaps — and the two-thirds it leaves unsettled at $k = 2$ is what the rung above that finishes.

The parities in size order finishes it, and the mechanism is worth knowing because it is not the one the sizes were expected to supply. The heap sizes do settle the remaining classes, and only through the order they put the parities in: sort the heaps largest first, read off their parities as a five-bit word, and that word settles the whole game at every width of move — with the losing words forming a subspace.

So the invariant the anchor was looking for exists, it is a parity statistic, and the sizes enter it only as a sorting key. Every rule this page tries and refuses reads the heaps as numbers, which is exactly the information the answer discards.

Two neighbours are worth the trip. The theorem that needed none of the theory is where an invariant of exactly this kind is set out and verified over every position it claims. And the period is small and the proof does not say so is the other place on this site where a guaranteed structure and a usable description come apart.