Grundy value — where it appears
Named by 90 essays across 7 fields — each of them below, with the objects they name alongside it.
Misère play
Change one word — the player who cannot move wins — and the games are identical, the strategies are not, and almost every theorem of the normal-play theory stops being true. It is the cheapest possible modification and the most expensive.
Every impartial game is a Nim heap
Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.
The theorem that needed none of the theory
Bouton solved Nim completely in 1901, with an argument that mentions no value, no sum of games and no Grundy number, because none of the three existed. The argument is two closure properties and it is airtight — and run on any other game it fails at the step that does the work.
Grundy sequences, and where they stop being predictable
Computing one Grundy value is a mex. Computing all of them produces a sequence, and the sequences do something nobody has fully explained — most of them eventually repeat, some of them take thousands of terms to start, and for a few nobody knows whether they ever do.
What survives misère play
Misère play destroys the value theory, and something much smaller grows back. Fix one game, look only at sums of its own positions, and the classes that behave alike form a monoid — computed here, and larger than the normal-play answer every time.
The game with the shortest rule is the hard one
Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.
Outcomes do not add
Knowing who wins each part of a position tells almost nothing about who wins the whole. Counted over every sum of two values born by day two, six of the outcome table's ten entries are settled and four are not — and every settled one is settled by the order rather than by anything about outcomes. Two first-player wins reach all four classes between them.
Two people, four years apart, one theorem
Roland Sprague proved it in 1935 and Patrick Michael Grundy proved it in 1939, neither knowing of the other. That looks like coincidence until the alternatives are examined — and the rule they both reached turns out to be the only one that can work at all.
A golden ratio thirty years early
Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.
A chess problem that turned out to be an octal game
Dawson posed it in 1934 as a puzzle about pawns. It is the octal game ·137, its Grundy sequence is eventually periodic with period 34 from heap 52 — and the word doing the work in that sentence is eventually, because five values below the start disagree with their repeats and always will.
The move that gives counters back
Poker Nim adds one rule to Nim — a player may put counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. The winner is decided by exactly the same nim-sum, and the reason is the single most useful idea in the whole reduction apparatus.
The sequence nobody has settled
Guy and Smith surveyed the octal games by hand in 1956 and conjectured that every finite one is eventually periodic. Seventy years and a great deal more arithmetic later, some of them have settled and some have not — and the evidence for the conjecture is entirely that nobody has found a counterexample they were looking for.
A row of coins is already a sum
Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.
Squash every loop to a point
Colour every Hackenbush edge green and the game becomes impartial, so the whole picture is worth a single Nim heap. Two principles find which one without playing anything — fuse the cycles, then run one pass up the tree — and a nine-vertex lattice that costs 1,283 positions to solve costs twelve steps to read.
Nim is easy, in binary
Three heaps of a thousand counters take thirty bits to write down and three thousand counters to lay out. The nim-sum does three exclusive-ors either way. Whether that counts as fast depends entirely on which of the two numbers the work is compared against.
Take one, three or four
A heap and a list of legal takes. It is the smallest interesting impartial game there is, and the only family in the subject where eventual periodicity is not observed, not conjectured, but guaranteed — with a bound on when it must appear.
"Hopeless" was a claim about a method
Misère analysis was declared intractable in the 1970s, and the verdict was correct about what was being attempted. Quotients did not refute it thirty years later — they changed the question from a value per position to a monoid per universe, and the computed sizes show why the first question has no good answer.
Tame and wild
The genus is a Grundy value with a tail — the misère values of the position with 0, 1, 2, … heaps of ∗2 added — and a game is tame when its symbols are the ones Nim heaps have. Computed here for seven games over heaps 1 to 14: Kayles goes wild at heap 5, Dawson's chess at heap 9, the octal game ·6 at heap 7, and heaps 3 and 11 of Dawson's chess are both worth ∗2 under normal play with only one of them tame.
The nimbers multiply
Nim-addition is exclusive-or and everybody meets it first. There is also a multiplication, defined by the same take-the-least-value-not-forced manoeuvre as the mex — and it makes the nimbers below sixteen a field, with every axiom checked here and an inverse for every non-zero value.
Where the impartial theory stops
Sprague–Grundy gives every impartial position one number, and the number is complete. The moment the two players have different moves no number works at all — not a harder one to compute, none — and three positions here are compared against every nimber to show it.
The digits say which move wins
Wythoff's cold positions are usually given as a pair of golden-ratio formulas. Written in Fibonacci base they are a statement about digits instead — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — and a rule about digits answers a question about a heap of a trillion.
The tartan theorem
The nimbers are a field, with a multiplication defined by a mex-style rule that looks like an algebraist's amusement. Lay two coin-turning games on a grid and the Grundy value of each square is the nimber product of its two coordinates — which is the point at which the multiplication stops being a curiosity and starts computing answers.
Two misère outcomes are not enough
Knowing who wins each part does not say who wins the sum. Over 676 sums built from a pool of twenty-six positions, nine of the sixteen pairs of outcome classes settle the answer under normal play and not one of the sixteen settles it under misère — and the nine that work are theorems about a value being zero, which is exactly the thing misère play does not have.
A move that must be answered
Every argument on this site about sums assumes the parts are independent: a move in one leaves the others alone, and the reply may go anywhere. Top Entails denies it — take the top coin of a heap and the opponent must answer in that heap. The nim-sum then misreads 9 of 36 two-heap positions, and two heaps of two coins are a first-player win, which no impartial game the theory covers can be.
The losing positions are a code
Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.
Four values, and the sequence is settled for ever
The Grundy values of a subtraction game repeat with period 7, and proving it needs a window of exactly four of them — one for each size of move the game allows. Everything past the window follows by induction. A finite computation has settled a claim about every heap there will ever be.
The period is small and the proof does not say so
Every subtraction game repeats eventually — that is a theorem, and its proof gives a bound of sixteen thousand for a three-move set. Over 112 sets the longest period measured is twenty-two. The proof and the fact are four orders of magnitude apart, and the rule of thumb that closes the gap is broken by one set in the sweep.
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.
What a tame heap may be replaced by
Calling a heap tame is only worth anything because a tame heap can be swapped for a Nim position with the same genus in any misère sum. The swap is not always a single heap: Kayles' heap of eight is worth ∗ under normal play and carries the genus of 2 + 3, and substituting ∗ instead gets three of the twenty-eight Kayles pairs wrong.
Cram
Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.
The cost is in the closure, not in the positions
Under normal play, Dawson's chess needs four classes for every heap up to twelve, because its Grundy values stay at three or below there. Under misère play the same game needs six, then twelve, and the number rises with the universe rather than with the position — which is a different kind of expense entirely.
A token on a graph
Geography is an impartial game whose position is a vertex and a history, so a ten-vertex graph has ten thousand states rather than ten. Take the arrows off and the same game is decided by a maximum matching — first player wins exactly when every maximum matching covers the start, verified on 41 vertices across eight graphs. One word in the rules separates a polynomial criterion from a PSPACE-complete problem.
A pass is not a move
Put a single pass token on a Nim board and one clause decides everything. If it may be taken at any time — including as the move that ends the game — the value of the whole is the nim-sum with a one added, in all 120 positions swept: the pass is a heap of one. Forbid it as the final move and the value stops being a function of the nim-sum at all, and 3 and 1 + 2 come apart.
The code names the move
If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.
When the nested sum only sees the value
The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.
No two heaps alike
Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.
The values that keep arriving
A Grundy sequence that repeats uses finitely many values and stops needing new ones. Six thousand heaps into ·007 the count of distinct values is 187 and still climbing, and the share of heaps carrying something outside the twenty-two commonest rises from 32% in the first thousand to 85% in the sixth. The rare values a periodicity argument needs to thin out are getting commoner.
Splitting is a move
Add to Nim a move that removes nothing — break a heap in two — and the Grundy sequence gets simpler, not harder. Lasker's Nim has a closed form with one clause per residue modulo four, exact on all 2,001 heaps checked: the identity with every fourth pair transposed. Kayles is the same kind of game with the taking bounded instead of the splitting, and it has no closed form at all, settling into a period of twelve only from heap 71 with fourteen values outside it for ever.
The heap is not the position
Fibonacci Nim bounds a move by twice the previous move, which puts the state outside the board: a heap of six with a cap of two and a heap of six with a cap of five are different games. So there is nothing to add and no Grundy value to compute — and the game is completely solved anyway. The opener loses on exactly the nine Fibonacci numbers up to 120, and the smallest term of the Zeckendorf numeral is a winning move in all 110 winnable heaps.
Two players, two lists
Give each player their own list of how many counters they may take and the impartial theory stops applying. What survives is the outcome: it settles into a repeat, for every pair of lists, and that is a theorem. What does not survive is the value — on four of six pairs swept it has no repeat inside sixty heaps, and the birthdays are still climbing at the edge of the window.
A period with a constant added
An octal code says what a player may do when removing k counters, in three bits; a hexadecimal code adds a fourth — leave three heaps — and the digits run to fifteen. Over twenty-two codes swept to six hundred heaps, five hexadecimal ones repeat with a fixed amount added each time round and no octal one does. Their values climb for ever and never repeat, so a search that looks only for repetition reports them unsettled.
How long it lasts
Move in every component at once and the game ends the moment any one of them does. Grundy values say nothing about that game; what decides it is the remoteness, a second number computed from the same tree that measures how long a component can be made to last. Over 2,268 positions the rule is right every time, and the two numbers determine each other in neither direction.
The genus of a sum
A genus symbol is meant to be carried one per heap, so that a solver never has to look at the heap again. That is a claim that the pair of symbols determines the sum's, and across nine games and 405 pairs it holds without exception — while the bases alone determine it in only 38 of 50 cases and the superscripts alone in 70 of 74. Both halves of the symbol are load-bearing, and two wild heaps can add to a tame sum.
What a component has to carry
Three impartial games on this site break the sum, and they break it for the same reason: a component cannot say what its own legal moves are. Measured with one instrument — one number per part, exclusive-ored — the failure rate runs from a quarter to nearly half, against a control where the same recipe is a theorem and is never wrong.
The number nobody needs
The compound theory carries a third quantity — the suspense number — computed by the remoteness recursion with both preferences reversed, for the compound that stops as soon as any component stops. It governs that compound correctly. So does remoteness, so does the plain Grundy value, and the shortening does not change the winner on any of 1,176 positions.
Where the nimbers run out
A single End-Nim heap is a Nim heap and every palindromic row is worth a nimber, so the impartial theory looks as though it might get a long way into a partizan game. It gets one row in thirteen. Five nimbers occur in five and a half thousand rows, the palindromes account for two fifths of them, and the rows worth something else run to 2,693 distinct values.
A compound of two different games
Every rule the compound theory has survives mixing exactly — the minimum-remoteness rule is right on all 5,184 mixed pairs and all 7,560 triples — and the reason is not that the rules are strong. It is that each of them reads one number per component, and a number does not remember which ruleset produced it. The thing mixing damages is the shortcut a reader carries instead.
Looking for the symmetry
Answering every move with its mirror image wins Cram on a board with both sides even, which is the argument everybody meets. Asked of every connected shape of at most eight squares instead of of thirteen rectangles, it wins twelve — and accounts for a sixth of the second-player wins there are, because 852 of the 1,042 shapes have no symmetry to answer with in the first place.
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.
What restores the theorem
Fibonacci Nim breaks the recipe every impartial game is supposed to obey: one number per heap, exclusive-ored, gets a quarter of two-heap sums wrong. Index the recursion on the pair of heap size and cap instead and the recipe is exact on every pair and every triple — and the number a heap of nine carries turns out to be five rather than one.
The rule the symbols follow
Two genus symbols make a third by three lines and no lookup table: the base exclusive-ors, the sum is fickle only when every component is, and the symbol follows. Checked on 252 pairs across nine games it is right on 238 — and the fourteen failures are exactly the fourteen pairs with a wild heap in them, which is the boundary the genus is defined up to arriving as a measurement.
The rows that are their own mirror
Four hundred and ten End-Nim rows are worth nimbers and 168 of them are palindromes, so a condition covering the other 242 was outstanding. It is that the row is equal to its own negative — and on this game that condition is not merely sufficient but exact, which is more than the group law promises and is a fact about End-Nim rather than about games.
The symmetry one move away
A pairing argument proves the second player wins and names no move to do it with. Asked of every shape of up to eight squares it settles twelve boards. Asked one move later — can the first player reach a position a half-turn pairs? — it settles 288, and which boards those are is decided by parity before anything about their outline is looked at.
A code that climbs by three
Five hexadecimal codes were known to repeat with a constant added, and every one of the five constants was a power of two — either a fact about exclusive-or or a coincidence over five cases. Sweeping all 255 two-digit codes settles it: seventy-one climb, seventy of them by 1, 2, 4 or 16, and one by three. The exception is ·3f, whose values are 3⌊n/6⌋ + (n mod 3) on every heap to twelve hundred.
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.
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.
The third digit
The rung below found 71 of the 255 two-digit hexadecimal codes repeating with a constant added rather than exactly, and asked whether the same share holds one digit wider. It rises. Of the 4,095 three-digit codes, 1,433 climb and 617 repeat exactly — seven in ten of the settled ones — so a saltus is the ordinary way a hexadecimal game settles and the exact repetition the octal survey was built to find is the special case.
A check in front of a search
The rung below found a pairing one move away on 288 of the 767 even first-player shapes, and asked what a solver that tested for one before recursing would save on a real game. On an even Cram board it saves nearly the whole search — a 4 × 5 board takes 17,348 node expansions without the check and one with it — and the depth profile shows why that number flatters: the check settles every winning position at the opening and at the last two moves, and about one in ten in between.
A function with no formula
The rung below's composition rule is exact on tame pairs and wrong on all fourteen wild ones, which looked like an exact boundary. Two heaps further it is wrong on 34 of 35 and right on one — Kayles' five and nine — so the boundary was a boundary of the pool. What survives is stronger and stranger: the pair of symbols still determines the sum on the wild side, and no rule of that shape describes it.
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.
The only way to split into three
Nineteen three-digit hexadecimal codes climb by three, and the rung below asked whether they share a form and what digits they have in common. The digits are exact: on eighteen of them the only way to split a heap into three is by taking exactly three counters, and taking three counters can do nothing else. The form is not shared — the eighteen carry four distinct sequences, and exactly one of the four counts in base three.
The wild side does not close
The rung below asked for the wild composition table and for two things about it: whether the wild genus symbols form a small closed set, and whether that set is a misère quotient in disguise. Building the table needed a wider sweep — nine counters a heap gives a diagonal rather than a table — and both answers are no. Not one of the twelve entries is a symbol any wild heap carries, and two wild heaps added together are tame two thirds of the time.
Two counters, and one displaced term
The rung below found four Grundy sequences in the odd-saltus class and asked which term each displaces and whether the digits predict it. They do — but there are two base-three counters and not one, chosen by whether a heap of one can be taken away. And there are three sequences rather than four: the fourth is the third with three isolated values, and was counted separately because its period had not settled.
A pairing that is not a symmetry
Every pairing strategy this ladder has found is a rigid motion of the square, and the requirement mentions no geometry at all. Searching all 8.8 million fixed-point-free involutions instead of the eight maps more than doubles what a pairing explains — and the smallest new one turns out to be a reflection with its two fixed squares swapped.
The quantity that carried nothing
The rung below proposed predicting a pre-period's length from the saltus and the period. The saltus correlates with it at −0.03, which is nothing; the period correlates at 0.77 with a coefficient of one, so a pre-period is about one period long. The digit that predicts whether there is one predicts nothing at all about how long.
The dual was the value table
A coin-turning game's losing rows form a linear code, and a code has a dual that nothing in the game appeared to read. It reads it constantly: the dual is spanned by the bit-planes of the Grundy values — the parity checks are the value table stood on end — and on Mock Turtles over eight coins the losing rows are exactly the span of the table that decides them.
One proof, and one wrong lemma
Two measured identities were left for a proof: the move rule by induction, the gap condition from the reply bound. The induction is exact on 31,731 heaps at eight factors. The reply bound holds at c = 2 and on one index pair in twenty-seven at c = 3 — and the inequality that does the work is a third one nobody proposed.
The pairing the formula hides
Welter's closed form sums a function over every pair of coins and needs an extra term when the count is odd, which the rung below called a surprise. Read as a matching it is not: an odd number of coins cannot be paired, the left-over coin contributes its own square, and some matching gives the value on every position measured.
A set with three descriptions, and a function with none
Wythoff's cold positions can be written three ways that share no arithmetic — an irrational constant, a greedy rule, a condition on Fibonacci digits — and all three are exact. The same game's Grundy values have no closed form at all. Both facts are about one table, and the gap between them is the subject.
Closing the wild side
The twenty-two wild genus symbols are not closed under addition, and the rung below offered two answers: a monoid nobody had guessed, or no algebra at any size. Neither. Five of the six games with wild heaps close at three or four heaps, with closures of two to five symbols, and the sixth is still growing.
Three bits of rule
An octal code is three bits a digit. The Grundy sequence it determines costs anywhere from one bit to a hundred and thirty-six — a factor of two hundred and seventy-two across rules that differ by a single digit — or it cannot be written down at all. Of four properties of the rule table tested against that, exactly one holds on every code that never settles: whether a move may leave two non-empty heaps. It is necessary, it is not sufficient, and nine codes carry it and produce answers smaller than their own rules.
Four hundred and seventy steps
The tartan theorem replaces a search with a multiplication. Measured on every grid a brute-force solve can reach, the two agree on all of them — and the ratio doubles with every square added. On the 8 × 8 grid the theorem is normally drawn at, the search would have to value eighteen quintillion arrangements; the theorem needs twenty-six different nimber products, and computing all of them by the rule that defines them looks at four hundred and seventy pairs.
What the arithmetic cost in 1956
The rung below ends by respecting a hand computation without pricing it. Priced in the operations a person actually performs, ·137's certificate is 7,919 of them — and the same sweep says ·47's is sixty-three times that, that a splitting move is what makes the cost quadratic, and that seventeen of sixty-four codes have no certificate at any price.
The convention Dawson actually used
Dawson published his puzzle as a problem where running out of moves loses you the game, and every compact result about ·137 is about the other convention. Under his own, nine values become a classification that doubles the moment a wild heap enters the range, and a heap stops carrying a number at all.
Three complete solutions in nine years
Bouton in 1901, Wythoff in 1907, Moore in 1910 — three airtight solutions of three games, all published before there was any theory of games at all. Asked about each other's games they all fail, and two of them fail by being wrong while one fails by having no form for the question. Only the last kind of failure decides anything.
A set with a short description
Bouton's argument is a closure argument about a set, and every impartial game has such a set — its own losing positions. So the method is complete and proves nothing. What made 1901 a theorem is that his set had a description shorter than the game, and swept over fifty-six subtraction games, exactly seven have one of his kind.
The sentence that solved the other convention
Bouton's paper solves misère Nim too, in one line, and it is the only misère result in the subject that fits on one. Transplanted the way the normal criterion is, it fails differently — the normal one calls losses wins and never the reverse, and this one errs in both directions on every game tried, because the clause it adds is about counters rather than about moves.
The capture that has to be made
Dawson's chess is quoted as the octal game ·137, and the step from a pawn diagram to a row of counters has been taken on trust. Searched as a chess position, the diagram agrees with ·137 on every board from one file to twelve, under both endings, and every exchange it can start is an odd number of moves that lands on one of ·137's options. The whole reduction rests on one rule of the diagram that the octal code never mentions: a capture, when one is available, must be made. Make it optional and the winner changes on two, three, six and seven files.
A wall the pawns cannot cross and the rule can
Two rows of Dawson's diagram separated by a file with no pawn on it: 1,616 moves were examined and not one crosses the gap. With captures optional the rows add on every diagram checked. With captures compulsory they do not, because the compulsion is a rule about the whole board — and the game that is a sum is the one ·137 does not describe.
A difference the rows cannot predict
The diagrams that are not the sum of their rows have been counted and never priced. Priced over 50 diagrams and 63,408,981 positions, the difference takes three values and is a function of nothing a reader can see: seven diagrams whose rows are worth ∗ and ∗ split five to two on it, the third value arrives only at the ninth file, and the one rule that survives is a parity — all twenty-one diagrams of three, five and seven rows add, and every failure carries an even number of rows.
A coin with three strings is worth something
Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.
The step nobody took for thirty-four years
Bouton's criterion is that the heap sizes exclusive-or to nothing. The 1935 theorem is that the heap Grundy values do. The exclusive-or is the same operation in both and it is his, so the whole of the intervening thirty-four years is one substitution — and run over eight games and 672 positions, the substituted criterion is exact on every one while the original is exact on Nim and nowhere else.
The picture Bouton's proof leaves behind
His argument is two closure properties of one set, and the Sprague–Grundy theorem is the same two sentences with nought replaced by a variable — checked here on five games and every value in range, with no move staying inside a class and no class failing to be reachable from above. What the argument also leaves behind is a picture in which the values descend, and that is false: 99 of 444 moves here raise a value, and none of them is in Nim.
The proof is sixteen cells
Lasker's Nim has a four-clause formula that was checked on two thousand heaps and never proved. The proof fits in a four-by-four table: the last two bits of a split's value are fixed by the last two bits of its parts, so no split can land in its own heap's class — except at 3 mod 4, where it lands exactly on the one value the takes leave missing and pushes the answer up by one.
One split is enough
A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.
The formula is a limit
Cap the take in Lasker's Nim at k counters and the game is a finite rule table, 4.33…3, whose Grundy sequence repeats with period k + 1 rounded up to even and follows Lasker's formula until the cap bites. The formula is what those periods converge to. And the same column of codes, with a free split in front, holds Kayles itself: the rule 4.4 on a heap of n + 1 is Kayles on a row of n.
Three heaps and a pass
Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.
What a component would have to carry
For a held pass to be decided by a summary of each component, the summary must separate every pair of components some company tells apart. The Grundy value does not — Nim 1 and Kayles 8 are equal games that a held pass separates beside a single Nim heap of two. Nor does the Grundy value with the component's own held-pass value: Kayles 3 and Kayles 6 agree on both and are split by a company of two Nim heaps. Over twenty-four components, fifteen classes against fourteen pairs, and the gap widens as the pool grows.
A misère sum is searched, not added
Under normal play the outcome of a sum of heaps is a nim-sum of numbers already known: twenty stored values decide every sum of Dawson's chess with heaps up to nine, however many heaps it has. Under misère play each sum is a new position to search. One outcome costs six positions for a single heap, two hundred for four heaps and over five thousand for eight, and a table of every eight-heap outcome costs a hundred thousand. The misère quotient is the only thing that brings the price back down.
A staircase, not a slope
With the misère closure cut forty-fold, Dawson's chess can be classified at heaps far beyond nine. The count of classes is a staircase: six from heap three to eight, twelve from nine to twelve, seventeen from thirteen to sixteen. Normal play steps once in that range, from four to eight at heap thirteen, where a Grundy value of four first appears. Misère play steps there too, and once more at heap nine, where normal play does not move at all — the first wild heap. Heaps eleven, fifteen and sixteen are also wild and move nothing.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchImpartialNimOctal gameMexNim-sumDisjunctive sumNormal playCounterexamplePeriodicityEnumerationSprague–Grundy