Nimber¶

Assign an impartial normal-play game position the unique Nim-heap value determined recursively by the minimum excluded values of its options and composed by nim-sum.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2376
Origin domain: mathematics
Subdomain: impartial normal play game values
Aliases: Sprague–Grundy value, Grundy value of a game, Nim value

Core Idea¶

A nimber is the canonical game value represented by a Nim heap and assigned to an impartial position under normal play. For a finite acyclic position \(G\), its value is \(g(G)=\operatorname{mex}\{g(H):H\text{ is an option of }G\}\), the least nonnegative integer absent from the option values. The Sprague–Grundy theorem states that \(G\) is equivalent, for disjunctive addition, to a Nim heap of that size. This game-theoretic Grundy value must not be confused with the accepted catalog's Grundy number of a graph, which concerns greedy vertex coloring.^[1]

Terminal positions have no options and therefore value zero. Recursive mex evaluation assigns each predecessor a nonnegative integer; value zero characterizes a previous-player win under the finite impartial normal-play assumptions, while nonzero values admit a move toward zero. For a disjunctive sum, only one component is moved per turn and the combined nimber is the bitwise exclusive-or of component values. Conway's broader theory extends nimbers beyond finite integers to ordinal-valued games and defines nimber arithmetic, but finite Sprague–Grundy evaluation is the practical core.^[2]

The theorem requires impartiality—the legal options do not depend on which player moves—and normal play, where the player unable to move loses. Partizan games need richer values; misère play alters terminal and composition rules; loopy or infinite games require additional conditions. A nimber is a value or equivalence class, not a strategy by itself, although it identifies winning moves when combined with the option graph. The word ‘Grundy’ is polysemous: graph-coloring Grundy number has a different input, recurrence, and output meaning.^[3]

Structural Signature¶

Game position. A state in an impartial perfect-information game supplies the object evaluated.
Option set. Legal followers are identical for both players and define the recursion.
Normal-play convention. Having no move means losing, fixing terminal semantics.
Acyclic foundation. Finite descent makes recursive evaluation well founded.
Minimum excluded operator. Mex selects the least value not represented among options.
Equivalent Nim heap. The resulting value denotes contextual equivalence to a single heap.
Disjunctive sum. A move changes exactly one independent component.
Nim addition. Bitwise exclusive-or composes the component values.

What It Is Not¶

Not graph-coloring Grundy number. That invariant records worst-case greedy coloring behavior on an ordered graph.
Not a mixed-strategy probability. Nimbers are exact combinatorial values, not distributions over choices.
Not a strategy by themselves. One must still locate an option producing the required new sum.
Not valid for every game. Partizan, misère, loopy, and stochastic games require different or extended semantics.
Not ordinary integer addition. Disjunctive sums compose finite nimbers by bitwise exclusive-or.
Not the mex of move labels. Mex is applied recursively to option values, not arbitrary move identifiers.

Scope of Application¶

The abstraction is literal wherever practitioners can identify the same constitutive roles, apply the same boundary tests, and obtain the same kind of output. The following habitats are uses of Nimber itself, not metaphors based only on resemblance.

Finite impartial games. Classifying positions under normal play.
Game decomposition. Evaluating independent components separately before nim-summing them.
Winning-move search. Selecting an option that changes the total nim-sum to zero.
Algorithm design. Memoizing recursive values on a directed acyclic game graph.
Game equivalence. Replacing a complicated component by its contextually equivalent Nim heap.
Transfinite game theory. Extending the nimber family to ordinal values under stronger foundations.

Clarity¶

A clear account of Nimber must preserve the recognition invariant stated in the Core Idea rather than rely on the title alone. State impartiality, normal play, and the finiteness or well-foundedness assumptions. Apply mex to already computed option nimbers and show the option set. Use nim-sum rather than ordinary addition for disjunctive components. Disambiguate game nimber from graph-coloring Grundy number at first use. These declarations are not editorial extras: each changes what observations count, which transformations are licensed, and what conclusion can be drawn. A reader should be able to reconstruct the input, the operative rule, the output, and at least one defeater from the account without consulting an implementation or guessing an unstated convention.

Manages Complexity¶

Nimber manages complexity by replacing a diffuse field of observations or possible operations with a bounded role structure: game position supplies a state in an impartial perfect-information game supplies the object evaluated.; option set supplies legal followers are identical for both players and define the recursion.; normal-play convention supplies having no move means losing, fixing terminal semantics.; acyclic foundation supplies finite descent makes recursive evaluation well founded.; minimum excluded operator supplies mex selects the least value not represented among options.. The compression is useful because it localizes disagreement. One can ask whether the input was properly formed, whether a constitutive relation held, whether an alternative explanation defeats the inference, or whether the output was overinterpreted. The same compression can mislead when its discarded detail is exactly what the decision requires. A reference-grade use therefore reports both the invariant retained and the information intentionally lost.

Abstract Reasoning¶

Model positions and legal moves as a well-founded directed game graph.
Assign value zero to every terminal position under normal play.
Evaluate predecessors after all option values are known.
Take the minimum excluded nonnegative integer at each position.
Decompose disjunctive sums into independently evaluable components.
Combine component nimbers by bitwise exclusive-or.
Find a move to total zero when the current combined value is nonzero.
Test the candidate interpretation against the nearest named confusable rather than accepting a shared surface feature.
State the conclusion at the same scope as the source conditions, and retain uncertainty or nonuniqueness where the construct does not remove it.

Knowledge Transfer¶

The strict upward abstraction is Evaluation. Nimber instantiates Evaluation because it maps each eligible game position to a contextually meaningful value that predicts outcome class and composes across independent subgames. Within impartial normal play game values, the full mechanism transfers literally when the same roles and boundary tests recur. Beyond that domain, only the parent-level skeleton should travel. Reusing the label Nimber after removing its constitutive vocabulary would hide a change of mechanism behind an analogy. The honest transfer rule is therefore two-stage: recognize the domain-specific pattern first, then lift only the parent relation that remains invariant under a substrate change.

Examples¶

Canonical¶

A position has options with nimbers \(0\), \(1\), and \(3\). Its nimber is \(\operatorname{mex}\{0,1,3\}=2\). If it is added to an independent position of nimber \(5\), the sum has value \(2\oplus5=7\), not seven because ordinary addition happened to agree, but because binary exclusive-or determines the disjunctive sum. A winning analysis then searches for a move that makes the total zero.

Mapped back: input and conventions → constitutive role test → bounded output → explicit interpretation and defeater check.

Applied / In Practice¶

Consider a subtraction game in which a heap can lose one or two counters. Values repeat \(0,1,2,0,1,2,\ldots\) by mex recursion. Two independent heaps are solved by xor of their values. If the rule is changed to misère play, the same terminal convention no longer holds and the ordinary Sprague–Grundy conclusion cannot simply be reused.

Mapped back: field observation or problem → candidate recognition → confusable and limit checks → appropriately scoped conclusion.

Structural Tensions¶

T1: Value versus strategy. The nimber classifies a position but does not name the concrete move automatically. Diagnostic: Which legal option sends the total nim-sum to zero?
T2: Local recursion versus global equivalence. Mex uses immediate options yet yields equivalence in every disjunctive context. Diagnostic: Are the game and sum operations within the theorem's assumptions?
T3: Ordinary number versus nim arithmetic. Finite nimbers are written as integers but addition differs. Diagnostic: Is the operation numeric addition, nim-sum, or nim multiplication?
T4: Normal play versus misère play. Changing the losing convention changes composition near terminal positions. Diagnostic: Who wins when no move is available?
T5: Game Grundy value versus graph Grundy number. The names overlap while their structures do not. Diagnostic: Is the input a game-option graph or an ordered vertex-coloring problem?
T6: Autonomous value versus Evaluation. Evaluation is broad; nimbers fix impartial options, mex, and contextual equivalence. Diagnostic: Would the method remain recognizable without normal-play game semantics and nim-sum?

Structural–Framed Character¶

Nimbers are formal and structural: their values follow from game options and play convention, with no evaluative or institutional judgment. The five framing criteria point in a consistent direction. Evaluative weight is limited to whether the defining conditions are met, not whether the outcome is desirable. Human practice matters to the extent that experts choose conventions, instruments, or reporting thresholds, but those choices do not make every verdict arbitrary. Institutional history explains the name and standard use; it does not replace the recognition rule. The operative vocabulary travels within the home field and closely adjacent subfields, while transfer farther away requires translation to the parent prime. Thus recognition remains disciplined even where interpretation is defeasible.

Structural Core vs. Domain Accent¶

What is skeletal. Nimber instantiates Evaluation because it maps each eligible game position to a contextually meaningful value that predicts outcome class and composes across independent subgames. This is the part that can be expressed without the candidate's specialist nouns.

What is domain-bound. The domain accent is an impartial normal-play game graph, mex recursion, equivalence to Nim heaps, disjunctive sum, and xor arithmetic. Remove those elements and the result is no longer Nimber; it is only the parent relation or a loose analogy.

Why this does not clear the prime bar. The name does not recur with unchanged diagnostics across three independent domains. What transfers is already represented by prime:evaluation. The candidate remains autonomous because its in-domain recognition rule, failure modes, and consequences are stable, but its vocabulary and interventions do not float free of the home substrate.

Nimber instantiates Evaluation because it maps each eligible game position to a contextually meaningful value that predicts outcome class and composes across independent subgames.

The prospective workspace queue contains one strict upward edge to prime:evaluation. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Nimber Domain-specific

Parents (1) — more general patterns this builds on

Nimber is a kind of Evaluation Prime

Nimber instantiates Evaluation because it maps each eligible game position to a contextually meaningful value that predicts outcome class and composes across independent subgames.

Hierarchy path (1) — routes to 1 parentless root

Nimber → Evaluation → Comparison → Self Checking

Neighborhood in Abstraction Space¶

Nimber sits in a sparse region of the domain-specific corpus (88^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Strategic Games & Temporal Logic (8 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Grundy number of a graph. A greedy-coloring invariant already represented in the catalog under the same surname.
Nim-sum. The addition operation on nimbers, not the value object itself.
Sprague–Grundy theorem. The equivalence theorem that justifies nimber evaluation.
Minimax value. Handles broader adversarial payoff trees and need not use impartial mex recursion.
Outcome class. Only win/loss information; nimbers preserve how components combine.
Surreal number. A different class within Conway's games; nimbers have distinct arithmetic and order behavior.

References¶

[1] Sprague, Roland P. (1935–1936). ‘Über mathematische Kampfspiele.’ Tohoku Mathematical Journal 41: 438–444. registry ↩

[2] Grundy, Patrick M. (1939). ‘Mathematics and Games.’ Eureka 2: 6–8. registry ↩

[3] Conway, John H. (2001). On Numbers and Games, 2^nd ed. A K Peters. ISBN 978-1-56881-127-7. registry ↩