THE SPRAGUE-GRUNDY — a dart

THE SPRAGUE-GRUNDY every impartial game is a nim-heap

The astonishing theorem of combinatorial game theory: every impartial game under normal play is equivalent to a single nim-heap. Its size is the position’s Grundy number — the mex (minimum excludant) of the Grundy numbers of the positions you can move to. A sum of games is won exactly like nim: XOR the Grundy numbers, non-zero means the mover wins. One theorem collapses a universe of games onto nim.

THE TECHNIQUE grundy(p) = mex of successors' grundy

The demo computes the Grundy numbers of the subtraction game {1,2,3} and shows they are k mod 4: live demo

HISTORY & CREDIT Sprague 1935 · Grundy 1939

“Sprague-Grundy solves all two-player games.” — only impartial games (same moves for both) under normal play; partisan games need surreal numbers, misère play differs. cited

mex · the smallest non-negative integer NOT among the successors’ Grundy values.
the heap · a position of Grundy number g plays exactly like a nim-heap of size g.
1935/39 · R. Sprague and P. M. Grundy found it independently.

A whole game, weighed as one number. theorem

RECOMMEND FOR I-13 the grundy values, on the compiler

On i-13, mex(0,1,2)=3 and the subtraction-game Grundy values are periodic (k mod 4):

$ i13 run gm_sprague-grundy.i13 RUN OK · 5784 step(s) · call depth 8 mex_012 = 3 grundy 0..6 = 0 1 2 3 0 1 2 -- k mod 4 periodic = 1

Recommend as a NULL — a theorem (B39). The Grundy number is forall-pinned by the game graph; every correct solver returns the same value (WITNESSED). The nim-equivalence is a fact, not a same-function difference. NULL — every impartial game is a nim-heap.