Moores-nim — the series · Combinatorial Game Theory

Moore's Nim with k = 2: the columns, divided by 3. The heap sizes in binary, with each column added as an ordinary sum rather than exclusive-or. In Moore's Nim a move may take from as many as k heaps at once, and the position is lost for the player to move exactly when every column sum is divisible by k + 1. Ordinary Nim is k = 1, where divisible by two means an even number of ones — the same picture with a different divisor.

Taking from several heaps at once

Moore's Nim lets a move take from as many as k heaps at a time, and the losing positions are still read off the binary columns — divisible by k + 1 rather than by two. The rule agrees with exhaustive search over 54,264 positions and never disagrees, and it decides every outcome while supplying no value at all: reading the same columns as a base-3 number gets the Grundy value right on 42 of 330 positions.

part 1 · impartial

Moore’s rule, reversed. Moore’s Nim under the misère convention at three values of k, with the normal-play rule and the same rule plus a clause about heaps of one. The patch is the one Nim takes, with the modulus the normal-play rule already carries, and it is right on every position swept.

The patch that generalised

Misère Nim takes a one-line patch: play the normal-play strategy until every heap holds a single counter, then invert. Moore's Nim, where a move may take from up to k heaps at once, takes exactly the same patch with exactly the same modulus — and the two rules disagree on six positions out of 923.

part 2 · impartial

The rule a smaller move breaks

Moore's Nim lets a player take from at most k heaps, and its winning condition is the binary columns summed modulo k + 1. Cap the amount as well and the obvious repair — reduce each heap modulo the cap plus one, then read the columns — is exact at every cap when k is one and wrong at every cap when k is two or three. The reason is stronger than a broken rule: at k ≥ 2 the residues do not determine the outcome at all, so nothing of that shape can work.

part 3 · impartial

Four second parts, and none of them enough. The residues paired with each of four further counts, at three caps, with a move taking from two heaps. Every pairing leaves classes containing both a win and a loss.

The wider move is the easier game

An earlier essay ruled out every rule that reduces the heaps and reads the residues, and asked for a two-part statistic: the residues plus one more count. Four second parts are tested here and none of them decides. What turns up instead contradicts the premise the request was made under — a move that may reach three heaps is more predictable than one that may reach two, on every cap, every candidate rule, and after the change in the base rate is taken out.

part 4 · impartial

Sorted by how many heaps are odd. The 2,002 positions of the census grouped by how many of their heaps hold an odd number of counters. Four of the six groups are entirely lost or entirely won.

The count of odd heaps

The rung below refused a family of two-part rules for bounded Moore's Nim and asked what the 364 losing positions have in common as a set. They have an invariant, and it is a statistic of the whole position rather than of a 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 count settles every position at one heap a move and at four, and a little over half at two.

part 5 · impartial

Thirty-two words, four of them lost. Every position of five heaps grouped by the parities of its heaps in decreasing order of size. Each word is uniform, and four of the thirty-two are losing.

The parities, in size order

The rung below settled four of six parity classes in bounded Moore's Nim and asked whether the sizes pick out the losing positions in the two it could not. They do — but only through the order they put the parities in. 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.

part 6 · impartial

Four conditions. The four linear conditions whose kernels are the losing sets, with the cases each covers.

The parameter was the difference

The losing words of bounded Moore's Nim form a linear subspace and no map was known whose kernel they are. The equations exist, four conditions cover all thirteen cases at three to six heaps, and they are indexed not by the heap count but by the heaps less the width of a move — which turns the failure at six heaps into a prediction about seven.

part 7 · impartial

Five of six. The six predictions made for seven heaps by the difference reading, each scored against the sweep that was declined at the time.

The family with two witnesses

Six predictions about seven heaps were written down and deliberately not run. Five of them held. The one that broke is the condition that had been checked against two cases when it was proposed — the fewest of the four — and at seven heaps it does not merely give the wrong answer, it asks a question the parity word has stopped being able to answer.

part 8 · impartial