Splitting is a move

Nim has the shortest Grundy sequence there is. A heap of $n$ is worth $\ast n$, the sequence is $0, 1, 2, 3, \dots$, and there is nothing further to say about it.

Lasker’s Nim is Nim with one extra option: a player may split a heap into two non-empty heaps instead of taking from it. The move removes no counters, cannot end the game, and hands the opponent strictly more material to work with. Every instinct says it should make the analysis worse.

It makes it better, by a little, and the little is a clause about the residue modulo four.

What a split does to a mex #

A Grundy value is a mex — the least non-negative integer missing from the values of the options — so a new kind of move changes the answer by putting new numbers into the set the mex is taken over.

The new numbers are of a kind Nim’s mex never sees. A move that takes counters leaves one smaller heap and contributes that heap’s value. A split leaves two heaps, and the value of two heaps is their nim-sum, so a split contributes an exclusive-or of two smaller entries.

That is the whole mechanism, and it is why the effect is not obviously in either direction. The splits can fill in a value that was missing, pushing the mex up; or they can add nothing new, leaving it where the taking put it. Which happens depends on the arithmetic of exclusive-or, and there is no reason in advance to expect a pattern.

The four-line formula #

$$G(n) = \begin{cases} n & n \equiv 1, 2 \pmod 4 \\ n + 1 & n \equiv 3 \pmod 4 \\ n - 1 & n \equiv 0 \pmod 4 \end{cases}$$

with $G(0) = 0$. Exact on every heap from zero to two thousand, checked against the mex loop.

Read as a permutation it is very simple indeed: the identity, with $4k-1$ and $4k$ transposed. So the sequence runs $0, 1, 2, 4, 3, 5, 6, 8, 7, \dots$ — each block of four is $n, n, n+1, n-1$ relative to the index, which is one swap per block and nothing else.

Nothing in the rule suggests four. There is no four in “take any number, or split in two”; the splitting is unrestricted, the taking is unrestricted, and the modulus arrives entirely from the interaction of exclusive-or with the sequence the recursion is building. That is the pleasure of the result and it is also its warning: a period appearing in an octal-family sequence is a thing to find, not a thing to expect.

Why splitting can only ever help by a little #

The formula is close to the identity, and it is worth asking why the perturbation is so small.

Consider a heap of $n$ under Lasker’s rule. The taking moves already contribute every value $G(0)$ through $G(n-1)$, and since the formula is a permutation of $\{0, \dots, n-1\}$ on that range, those values are exactly $0$ through $n-1$ in some order. So the mex would be $n$ if the splits contributed nothing new.

The splits can only push it up, and only by supplying $n$ itself. So $G(n)$ is either $n$ or something larger, and the measurement says it is never more than $n+1$.

That is the shape of the constraint, and the four-cycle is what satisfies it. The residues $1$ and $2$ get $n$, because no split supplies $n$ there; the residue $3$ gets $n+1$ because a split does supply $n$; and the residue $0$ then gets $n-1$, because $n-1$ has been left over by the block before.

The essay’s claim is the census, not the derivation — the counts above are computed and the paragraph just given is a sketch — and the sketch’s job is to say why the answer had to be near the identity even before anybody computed it.

Kayles, which is the same kind of game #

Kayles is a row of skittles: a player knocks down one skittle or two adjacent ones, which either shortens a row or splits it in two. In octal notation it is $\cdot 77$ — take one or two, leaving nothing, one heap, or two.

So it is a take-and-break game, exactly as Lasker’s Nim is. The difference is which half is bounded. Lasker’s bounds nothing about the taking and allows the split at no cost; Kayles bounds the taking to one or two and allows the split only as a consequence of taking.

Kayles has no closed form. Its sequence is eventually periodic with period twelve, but the periodicity does not begin until heap 71, and fourteen values lie outside the pattern altogether — at heaps $0, 3, 6, 9, 11, 15, 18, 21, 22, 28, 34, 39, 57$ and $70$.

Fourteen exceptions, the last at heap seventy, and then a period of twelve for ever afterwards. That is a settled game — a period is a proof, and once the window has been checked far enough the answer is known for every heap whatever — and it is settled in a way that admits no formula shorter than the table.

Why one of them can have a formula and the other cannot #

The essay describes the two games as differing in “which half is bounded”, and that observation turns out to decide which kind of answer each can have — not by taste, but by a counting argument.

Lasker’s taking is unbounded. From a heap of $n$ a player may reach every smaller heap, so the option values include $G(0)$ through $G(n-1)$ — all of them, at every $n$. The mex is therefore at least $n$, so the sequence grows without limit and no value can repeat while the earlier ones are still all present. A sequence that climbs like that has no window to pigeonhole and no period to find; if it has a short description at all, the description has to be a formula.

Kayles’ taking is bounded. From a heap of $n$ a player reaches only $n-1$ and $n-2$ and the splits of those, so each value depends on a fixed-width window of the sequence behind it. The values stay small — over two thousand heaps Kayles uses nine values and never exceeds eight — so the windows are drawn from a finite alphabet, there are finitely many of them, and the pigeonhole argument applies exactly as it does to a subtraction game. A period is guaranteed; a formula is not.

The two regimes look completely different on the page, and the cheapest way to see it is to draw Kayles’ sequence the same way Lasker’s was drawn.

That is the difference stated as a picture. A bounded-reach sequence has somewhere to repeat and an unbounded-reach one does not, and no amount of drawing settles either question — the strip shows the regime and the search supplies the answer.

So the two games are not two attempts at the same kind of answer, one lucky. They are in different regimes, and the regime is decided by whether a heap can reach every smaller heap. Unbounded reach forces the sequence upward and rules out periodicity; bounded reach caps it and forces periodicity. Each regime admits one shape of short description and forbids the other.

That also disposes of a tempting bad reason for Lasker’s formula. It is not that a Grundy sequence must take each value once — Kayles’ takes the same values over and over, and two heaps sharing a value is perfectly ordinary: it means the two heaps are interchangeable in any sum, which is a fact about them and not a problem. Lasker’s sequence is a permutation because its taking is unbounded, and the permutation is a consequence rather than a constraint.

And it says what to expect from a new take-and-break rule before computing anything. Ask one question: can a heap reach every smaller heap? If yes, look for a formula and do not look for a period. If no, look for a period and do not be surprised when no formula appears. Kayles’ fourteen exceptions and Lasker’s four residues are the two regimes’ characteristic answers, and neither game could have produced the other’s.

The split that changes nothing, most of the time #

The heap of twelve is representative and worth generalising from.

Six splits are available. Three of them — $2+10$, $4+8$ and $6+6$ — contribute 8, 4 and 0, every one of which the taking moves had already supplied. The other three all contribute 13, which is a value no smaller heap carries and which is above the gap: eleven is missing whatever the splits do, so the mex is eleven and the six splits between them have changed nothing.

That is the usual situation, and both halves of it matter. Exclusive-or of two entries of a near-identity sequence lands, most of the time, on something already in the list; and when it does land somewhere new, the somewhere new is usually too high to matter. Adding moves to an impartial game can only move a Grundy value upward, and only by filling the gap — a rule that adds options above the gap is invisible. So a game with a great many moves is not thereby a game with large or complicated values.

The quarter of heaps where the extra rule does earn its keep is worth drawing beside it, because it is the same figure with one number changed.

So the extra rule is almost inert. It is doing nothing at all for two residues out of four, doing exactly one thing for the third, and the fourth is the consequence of the third: a heap at residue zero finds $n-1$ already missing, because the heap before it was pushed up off that value. A rule that adds up to $\lfloor n/2 \rfloor$ options to every heap changes the answer on a quarter of them, by one.

What the two answers cost to use #

The two regimes hand a player different objects, and it is worth saying what each is like to carry, because the comparison is not the one the word “formula” suggests.

Lasker’s formula fits on a line and works at any size. A heap of a trillion is settled by a division by four and one addition. Nothing is looked up, nothing is stored, and the answer for an arbitrary heap costs the same as the answer for a heap of nine.

Kayles’ period is a table and works at any size too. Fourteen exceptions and twelve residues is twenty-six numbers, which is more than a line and is still a small piece of paper, and a heap of a trillion is settled by one division and one lookup.

So the practical difference between the two is nearly nothing, and the essay’s own point about what “solved” means is exactly right. What separates them is that one answer can be said and the other can only be shown — and a reader who takes “no closed form” to mean “expensive” has read a statement about notation as a statement about cost.

There is a real difference underneath, and it is about what each answer can be reasoned with rather than what it costs. A formula composes: it can be substituted into an argument about heaps in general, differentiated with respect to the parameter in the informal sense of asking what happens when $n$ grows, and used to prove things about the game. A table of exceptions cannot be substituted into anything — it can only be consulted, and a proof that needs to know Kayles’ value at an unspecified heap has to case-split on the residue and then on whether the heap is one of the fourteen.

That is the honest content of “quotable”. Not that the formula is faster, and not that it is more certain — both are checked to two thousand heaps here — but that one of the two can appear inside a sentence about the game and the other can only appear beside one.

The thing that is not being measured #

The three sequences cost the same to compute. Each is a mex loop over the options a rule allows, each is linear or quadratic in the heap size, and a laptop produces two thousand terms of any of them instantly.

So what differs between them is not difficulty in any sense a complexity class measures. What differs is whether the answer has a short description, and that is a property of the sequence rather than of the computation that produces it.

The distinction matters because the two are constantly confused. A game whose Grundy sequence has a formula is not an easier game to solve — the mex loop is the same loop — it is a game one can talk about without running the loop. And a game with no formula is not intractable; Kayles is completely solved, in the strong sense that the value of every heap of every size is known, and it simply takes a table of fourteen exceptions and twelve residues to say so.

What “solved” means is the essay about that gap in general. Lasker’s Nim and Kayles are both solved and only one of them can be quoted.

What the sequence does not say #

A Grundy value is a value in a sum. Every claim here is about the value of a single heap, and the reason a value is worth having is Sprague–Grundy: a position with several heaps is worth the nim-sum of the heaps’ values, and a player wins by moving to nim-sum zero. The formula is therefore a complete strategy for Lasker’s Nim on any number of heaps, which is what a closed form buys.

The convention is normal play. Under misère play none of this survives: the values stop composing, the theory has to be rebuilt, and Lasker’s Nim’s misère analysis is a different and much longer story with a quotient in it.

The formula was checked, not proved. Two thousand heaps is a large window and a window is not a proof. What makes the claim safe is that a proof exists in the literature and this site’s job here is the check; a claim of this shape supported by a window alone would be exactly the situation the sequences nobody has settled is about.

Who found it, and when #

Emanuel Lasker was world chess champion for twenty-seven years and wrote a book on board games in 1931 in which the variation appears. He gave the rule and, as far as the record goes, the analysis; the game has carried his name since.

That is a striking date. The Sprague–Grundy theorem was published in 1935 and 1939 — two people, four years apart — so Lasker’s Nim predates the theory that makes its Grundy sequence a meaningful object at all. What Lasker had was Bouton’s 1902 analysis of Nim and a variation on it, and the question he could ask was who wins, not what a heap is worth.

Kayles is older still as a game and its analysis is much later. Dudeney and Loyd both posed it as a puzzle around 1900; the Grundy sequence, the period of twelve and the fourteen exceptions come out of the Guy and Smith survey of 1956 and the computing that followed it. The distance between “here is a game” and “here is its sequence” is half a century, and the sequence needed a machine.

Both games as sums #

The reason to want the sequence at all is that it turns a board into arithmetic.

A Lasker’s Nim position with heaps $7 + 12 + 5$ is worth $G(7) \oplus G(12) \oplus G(5) = 8 \oplus 11 \oplus 5 = 6$, so the mover wins, and the winning move is whichever one takes the total to zero.

The arithmetic is the ordinary one: three heaps become three numbers, the numbers are added in binary without carrying, and a non-zero total names the winner. What the closed form buys is only that the three numbers can be written down without running a search — the exclusive or would be the same either way, and a player who had memorised the sequence to twenty would be exactly as well off on a position of that size.

Kayles supports the same arithmetic and needs the table. That is the practical difference between the two and it is smaller than it sounds: a table of fourteen exceptions and twelve residues fits on a card, and a player carrying it is as well equipped as a player carrying Lasker’s formula.

Where the difference bites is in reasoning about the family rather than in playing. A closed form can be substituted into an argument; a table cannot. So the questions one can ask about Lasker’s Nim — which sums are lost, how the values distribute, what happens if the rule is perturbed — have answers reachable by algebra, and the corresponding questions about Kayles need another computation each time.

The rule table, and the digit that has nowhere to go #

Octal notation names a take-and-break game by a string of digits, one per number of counters removed. The digit $d_k$ is a sum of three bits: the heap may be taken entirely, or $k$ may be taken leaving one heap, or $k$ may be taken and the rest split in two.

Nim is $\cdot 333\dots$; Kayles is $\cdot 77$; Dawson’s chess is $\cdot 137$. The notation is what makes the family countable and it is how the unsolved cases were found — a survey of codes rather than a survey of games.

Lasker’s Nim does not fit in it. The move that splits without removing anything is $k = 0$, which is the digit before the point, and the conventional octal string starts at $k = 1$. Written in full the game is $4 \cdot 3333\dots$ — a leading $4$, meaning remove nothing and split in two, followed by all threes.

That is a notational accident with a consequence. The great octal surveys sweep the digits after the point, so a game with a leading digit is outside the swept family by construction, and the several hundred codes anybody has computed do not include it. The column is not hard; it is simply not where the search has been.

Where the ladder goes next #

The first rung out is the proof of the formula, which is an induction on the residue with the exclusive-or arithmetic done explicitly, and which this essay has only sketched.

The second is the family. Lasker’s Nim is the octal-family game with a digit before the point — the digit describing what may be done when zero counters are removed — and that whole column of the family is unexplored here. Allowing a split only into equal halves, or only of heaps above a size, gives games with the same flavour and unknown sequences.

And the third is the question the three games together pose and none of them answers: what property of a rule table predicts whether its sequence has a formula? Kayles is $\cdot 77$ and has none; Lasker’s is a $4$ before the point and has one; Dawson’s chess is $\cdot 137$ and has a period of thirty-four with a handful of exceptions. Nothing about the digits sorts them, and the Guy and Smith conjecture is the closest anybody has come to a statement of the general shape — and it is a conjecture about whether a period exists at all, which is a much weaker property than having a formula.