THE FOLD / BOSS / THE FINAL BOSS / THE SPRAGUE-GRUNDY
THE SPRAGUE-GRUNDY
every impartial game is secretly a Nim heap
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Sprague–Grundy theorem is the master key to impartial games (both players share the same moves, like Nim): every position is equivalent to a single Nim heap of some size — its Grundy number (nimber). The Grundy number is the mex (minimum excludant: smallest non-negative integer not among) of the Grundy numbers of positions you can move to.
A position is a loss for the player to move iff its Grundy number is 0. And the crown jewel: the Grundy number of a sum of independent games is the XOR of the parts’ Grundy numbers — so complex games are solved by XOR-ing simple ones.
LIT verified live: a subtraction game’s Grundy values equal n mod 4, and a Nim position is losing iff the XOR of heap sizes is 0 — matching a brute-force minimax over 300 positions (window.__spraguegrundy). FIG no framing; exact game theory.
A position is a loss for the player to move iff its Grundy number is 0. And the crown jewel: the Grundy number of a sum of independent games is the XOR of the parts’ Grundy numbers — so complex games are solved by XOR-ing simple ones.
LIT verified live: a subtraction game’s Grundy values equal n mod 4, and a Nim position is losing iff the XOR of heap sizes is 0 — matching a brute-force minimax over 300 positions (window.__spraguegrundy). FIG no framing; exact game theory.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-final-boss — the fight you win by knowing the position is already lost or won. Sprague–Grundy is the boss-fight solver: reduce any game to a number. AVAN (AI) built the instrument: the mex, the Grundy recurrence, the XOR game-sum, the brute-minimax cross-check.
Credit as content: Roland Sprague (1935) and Patrick Michael Grundy (1939), independently. The weave: David names the boss; I compute Grundy numbers by mex, combine games by XOR, and confirm the win/loss verdict against exhaustive minimax.
Credit as content: Roland Sprague (1935) and Patrick Michael Grundy (1939), independently. The weave: David names the boss; I compute Grundy numbers by mex, combine games by XOR, and confirm the win/loss verdict against exhaustive minimax.
3 ONE DIMENSION
A position’s Grundy number is the mex of its successors’ Grundy numbers — the smallest non-negative integer none of the moves lead to. Grundy 0 means every move hands the opponent a winning position.
4 TWO DIMENSIONS · INTERACTIVE
A Nim position of heaps. The XOR of heap sizes is the Grundy number; zero means the player to move loses. Checked against a brute-force minimax; a subtraction game’s Grundy sequence is shown too.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: each game reduced to a single nimber, their XOR deciding the combined game.
AVAN’s addition (the inverse-companion): composition becomes XOR. A sum of games is not analysed by exploring the exponential product of their move-trees — instead each game is reduced to one number and the numbers are XOR-ed. The inverse of ‘a complex combined game’ is ‘the XOR of its parts’ nimbers.’ So game addition (played in parallel) corresponds to nimber addition (XOR), turning a search problem into arithmetic. Magenta is the exponential product game-tree you never explore; green is the XOR of small nimbers that decides it. Every impartial game is secretly Nim — and nimber addition is exactly the carry-less XOR of the nimber field.
LIT Genuine Sprague-Grundy theorem (Sprague 1935; Grundy 1939). Verified live: the mex-based Grundy recurrence gives n mod 4 for the {1,2,3} subtraction game, and for Nim the XOR of heap sizes equals 0 exactly when the position is losing under a brute-force memoized minimax, across 300 random positions (window.__spraguegrundy.subtractionGrundy && .nimXorMatchesBrute).
FIG No framing: the mex, the Grundy recurrence, the XOR game-sum, and the brute-minimax cross-check run in-browser and agree exactly. The AVAN inverse is honest — a sum of games reduces to the XOR of their nimbers rather than the exponential product of move-trees, so game addition equals nimber addition (XOR); magenta is the product game-tree, green the XOR. Ties to the-carryless-field nimbers and the-nim.
FIG No framing: the mex, the Grundy recurrence, the XOR game-sum, and the brute-minimax cross-check run in-browser and agree exactly. The AVAN inverse is honest — a sum of games reduces to the XOR of their nimbers rather than the exponential product of move-trees, so game addition equals nimber addition (XOR); magenta is the product game-tree, green the XOR. Ties to the-carryless-field nimbers and the-nim.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FINAL BOSS · David Lee Wise (ROOT0), with AVAN