Nimber
Nimber
Main page

Nimber

logo
Community Hub0 subscribers
Read side by side
from Wikipedia

In mathematics, the nimbers, also called Grundy numbers (not to be confused with Grundy chromatic numbers), are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

Because of the Sprague–Grundy theorem which states that every impartial game is equivalent to a Nim heap of a certain size, nimbers arise in a much larger class of impartial games. They may also occur in partisan games like Domineering.

The nimber addition and multiplication operations are associative and commutative. Each nimber is its own additive inverse. In particular for some pairs of ordinals, their nimber sum is smaller than either addend.[1] The minimum excludant operation is applied to sets of nimbers.

Definition

[edit]

As a class, nimbers are indexed by ordinal numbers, and form a subclass of surreal numbers, introduced by John Horton Conway as part of his theory of combinatorial games.[2] However, nimbers are distinct from ordinal and surreal numbers in that they follow distinct arithmetic rules, nim-addition and nim-multiplication. Other than that they are a proper class rather than a set, nimbers form a field under nim-addition and nim-multiplication.

As a set, finite nimbers can be put in one-to-one correspondence with finite ordinal numbers, which are the natural numbers. Nonetheless, their arithmetic structures are not isomorphic; nimber arithmetic fundamentally differs from ordinary arithmetic operations on natural numbers.

Nimbers are often denoted using a star notation {*0, *1, *2, ..., *ω, *(ω+1), ...}.

Uses

[edit]

Nim

[edit]

Nim is a game in which two players take turns removing objects from distinct heaps. As moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric, Nim is an impartial game. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The goal of the game is to be the player who removes the last object. The nimber of a heap is simply the number of objects in that heap. Using nim addition, one can calculate the nimber of the game as a whole. The winning strategy is to force the nimber of the game to 0 for the opponent's turn.[3]

Cram

[edit]

Cram is a game often played on a rectangular board in which players take turns placing dominoes either horizontally or vertically until no more dominoes can be placed. The first player that cannot make a move loses. As the possible moves for both players are the same, it is an impartial game and can have a nimber value. For example, any board that is an even size by an even size will have a nimber of 0. Any board that is even by odd will have a non-zero nimber. Any 2 × n board will have a nimber of 0 for all even n and a nimber of 1 for all odd n.

Northcott's game

[edit]

In Northcott's game, pegs for each player are placed along a column with a finite number of spaces. Each turn each player must move the piece up or down the column, but may not move past the other player's piece. Several columns are stacked together to add complexity. The player that can no longer make any moves loses. Unlike many other nimber related games, the number of spaces between the two tokens on each row are the sizes of the Nim heaps. If your opponent increases the number of spaces between two tokens, just decrease it on your next move. Else, play the game of Nim and make the Nim-sum of the number of spaces between the tokens on each row be 0.[4]

Hackenbush

[edit]

Hackenbush is a game invented by mathematician John Horton Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line. Players take turns removing line segments. An impartial game version, thereby a game able to be analyzed using nimbers, can be found by removing distinction from the lines, allowing either player to cut any branch. Any segments reliant on the newly removed segment in order to connect to the ground line are removed as well. In this way, each connection to the ground can be considered a nim heap with a nimber value. Additionally, all the separate connections to the ground line can also be summed for a nimber of the game state.

Addition

[edit]

Nimber addition (also known as nim-addition) can be used to calculate the size of a single nim heap equivalent to a collection of nim heaps. It is defined recursively by where the minimum excludant mex(S) of a set S of ordinals is defined to be the smallest ordinal that is not an element of S.

For finite ordinals, the nim-sum is easily evaluated on a computer by taking the bitwise exclusive or (XOR, denoted by ) of the corresponding numbers. For example, the nim-sum of 7 and 14 can be found by writing 7 as 111 and 14 as 1110; the ones place adds to 1; the twos place adds to 2, which we replace with 0; the fours place adds to 2, which we replace with 0; the eights place adds to 1. So the nim-sum is written in binary as 1001, or in decimal as 9.

This property of addition follows from the fact that both mex and XOR yield a winning strategy for Nim and there can be only one such strategy; or it can be shown directly by induction: Let α and β be two finite ordinals, and assume that the nim-sum of all pairs with one of them reduced is already defined. The only number whose XOR with α is αβ is β, and vice versa; thus αβ is excluded. On the other hand, for any ordinal γ < αβ, XORing ζ with all of α, β and γ must lead to a reduction for one of them (since the leading 1 in ζ must be present in at least one of the three); since we must have either Thus γ is included as either and hence αβ is the minimum excluded ordinal.

Nimber addition is associative and commutative, with 0 as the additive identity element. Moreover, a nimber is its own additive inverse.[5] It follows that αβ = 0 if and only if α = β.

Multiplication

[edit]

Nimber multiplication (nim-multiplication) is defined recursively by

Nimber multiplication is associative and commutative, with the ordinal 1 as the multiplicative identity element. Moreover, nimber multiplication distributes over nimber addition.[5]

Thus, except for the fact that nimbers form a proper class and not a set, the class of nimbers forms a ring. In fact, it even determines an algebraically closed field of characteristic 2, with the nimber multiplicative inverse of a nonzero ordinal α given by

where S is the smallest set of ordinals (nimbers) such that

  1. 0 is an element of S;
  2. if 0 < α′ < α and β' is an element of S, then is also an element of S.

For all natural numbers n, the set of nimbers less than 22n form the Galois field GF(22n) of order 22n. Therefore, the set of finite nimbers is isomorphic to the direct limit as n → ∞ of the fields GF(22n). This subfield is not algebraically closed, since no field GF(2k) with k not a power of 2 is contained in any of those fields, and therefore not in their direct limit; for instance the polynomial x3 + x + 1, which has a root in GF(23), does not have a root in the set of finite nimbers.

Just as in the case of nimber addition, there is a means of computing the nimber product of finite ordinals. This is determined by the rules that

  1. The nimber product of a Fermat 2-power (numbers of the form 22n) with a smaller number is equal to their ordinary product;
  2. The nimber square of a Fermat 2-power x is equal to 3x/2 as evaluated under the ordinary multiplication of natural numbers.

The smallest algebraically closed field of nimbers is the set of nimbers less than the ordinal ωωω, where ω is the smallest infinite ordinal. It follows that as a nimber, ωωω is transcendental over the field.[6]

Addition and multiplication tables

[edit]

The following tables exhibit addition and multiplication among the first 16 nimbers.

This subset is closed under both operations, since 16 is of the form 22n. (If you prefer simple text tables, they are here.)

Nimber addition (sequence A003987 in the OEIS)
This is also the Cayley table of Z24 – or the table of bitwise XOR operations.
The small matrices show the single digits of the binary numbers.
Nimber multiplication (sequence A051775 in the OEIS)
The nonzero elements form the Cayley table of Z15.
The small matrices are permuted binary Walsh matrices.
Nimber multiplication of powers of two (sequence A223541 in the OEIS)
Calculating the nim-products of powers of two is a decisive point in the recursive algorithm of nimber-multiplication.

See also

[edit]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia
from Grokipedia
A nimber is a fundamental concept in combinatorial game theory, representing an impartial game position that is equivalent to a single heap of size n in the game of Nim, where both players have the same available moves from any position.[1] Denoted as *n (with *0 being the terminal position with no moves), the nimber *n is recursively defined as the game whose left and right options are all smaller nimbers *0 through *n-1.[1] The integer value n associated with a nimber is known as its Grundy number (or nim-value), calculated as the minimum excludant (mex)—the smallest non-negative integer not appearing in the set of Grundy numbers of its possible successor positions—with terminal positions assigned Grundy number 0. This assignment enables the analysis of impartial games under normal play convention, where the player unable to move loses. The Sprague-Grundy theorem, independently developed by Roland Percy Sprague in 1935–1936 and Patrick Michael Grundy in 1939, asserts that every finite impartial combinatorial game is equivalent to a nimber, and the overall game's Grundy number is the bitwise XOR (exclusive or) of the Grundy numbers of its independent subgames. This theorem generalizes Charles Leonard Bouton's 1901 solution to Nim, where the winning strategy involves balancing heap sizes via XOR to achieve a zero total. In John Horton Conway's seminal framework from On Numbers and Games (1976), nimbers extend beyond mere integers to form the "field of nimbers," an algebraic structure where addition corresponds to the disjunctive sum of games (equivalent to XOR on values) and multiplication is defined recursively to yield a field of characteristic 2.[2] Nim-addition is commutative and associative, with *n + *n = *0 for all n, and the structure supports analysis of more complex impartial games.[2] These properties have influenced broader developments in game theory, including connections to surreal numbers and ordinal arithmetic.[1]

Fundamentals

Definition

In combinatorial game theory, particularly for impartial games under normal play (where the last player to move wins), a nimber is the value assigned to a single game position, equivalent to the size of the Nim heap that the position matches in strategic value; this value is a non-negative integer denoted *n.[3] The term "nimber" was introduced by John H. Conway to describe these values, distinguishing them as the basic units in the algebra of impartial games.[1] Formally, the nimber of a position $ G $, written $ *G $, is defined recursively as the minimum excludant (mex) of the nimbers of all positions reachable from $ G $ in one legal move:
G= mex{HH is an option of G}, *G = \ mex \{ *H \mid H \text{ is an option of } G \},
where the mex of a set $ S $ of non-negative integers is the smallest non-negative integer absent from $ S $. This definition originates from early work on assigning numerical equivalents to game positions to determine winning strategies.[3] A terminal position, which offers no legal moves, has an empty set of options, so its nimber is $ mex(\emptyset) = 0 $. To illustrate, consider a single heap in the game of Nim, where a player may remove any positive number of objects from the heap. A heap of size 0 is terminal and thus has nimber *0 = 0. A heap of size 1 allows a move only to the size-0 heap (*0 = 0), so its nimber is mex{0} = 1. A heap of size 2 allows moves to size 1 (*1 = 1) or size 0 (*0 = 0), yielding mex{0, 1} = 2. By induction, a Nim heap of size $ k $ has nimber *k = k.[4] Nimers, while consisting of the non-negative integers, must be distinguished from ordinary ordinal numbers or other game values such as surreal numbers, as the former equip the integers with non-standard addition (exclusive or) and multiplication operations that form an algebra suited to game disjunctions, rather than the usual arithmetic.

Relation to Grundy Numbers

The Sprague-Grundy theorem asserts that, under normal play convention where the last player to move wins, every impartial combinatorial game is equivalent to a single Nim heap whose size equals the game's Grundy number, or nimber, denoted *G for game G.[5] This equivalence allows any such game to be analyzed as if it were a Nim position, with the nimber capturing the game's strategic value.[6] The theorem extends naturally to sums of impartial games under the disjunctive sum operation, where a move consists of selecting one component game and making a legal move within it, leaving the others unchanged. The nimber of the sum G + H is then the bitwise exclusive-or (XOR) of the individual nimbers, *G \oplus *H.[6] This operation ensures that the overall position is a second-player win if and only if the XOR of all component nimbers is zero, mirroring the winning condition in Nim.[5] The foundational ideas trace back to Charles Bouton's 1901 analysis of Nim, where he established that the winning strategy involves balancing pile sizes via their binary digital sums, equivalent to XOR.[4] Bouton introduced this for Nim specifically, but the concept was generalized independently by Roland Sprague in 1935–1936 and Patrick M. Grundy in 1939 to arbitrary impartial games.[4] Nimbers thus serve as the algebraic "numbers" structuring the theory of impartial games under normal play, with the disjunctive sum corresponding to XOR addition in the nimber algebra.[6] A brief proof sketch for the XOR property proceeds as follows: the options from G + H are positions of the form G' + H (where G' is an option of G) or G + H' (where H' is an option of H). The nimbers of these are *G' \oplus *H and *G \oplus *H', respectively. By the definition of nimber as the minimum excludant (mex) of the nimbers of its options, the set of reachable nimbers from G + H is the union of { *G' \oplus *H \mid G' \text{ option of } G } and { *G \oplus *H' \mid H' \text{ option of } H }. Since the mex of *G's options excludes *G and similarly for *H, this union excludes precisely *G \oplus *H from all possible nonnegative integers, yielding mex = *G \oplus *H.[6]

Operations

Addition

In combinatorial game theory, the addition of two nimbers, denoted m+n*m + *n, is defined recursively as the nimber assigned to the disjunctive sum of the impartial games corresponding to m*m and n*n. Specifically, it is the minimum excludant (mex) of the set of nimbers of all possible moves from that sum:
m+n= mex({m+nm is an option of m}{m+nn is an option of n}). *m + *n = \ mex \left( \{ *m' + *n \mid *m' \text{ is an option of } *m \} \cup \{ *m + *n' \mid *n' \text{ is an option of } *n \} \right).
This operation simplifies to the bitwise exclusive or (XOR) of the binary representations of the non-negative integers mm and nn, denoted mnm \oplus n. The XOR operation endows the set of nimbers with an abelian group structure under addition. It is commutative, so m+n=n+m*m + *n = *n + *m, and associative, so (m+n)+p=m+(n+p)(*m + *n) + *p = *m + (*n + *p). The nimber 00 serves as the identity element, satisfying m+0=m*m + 0 = *m, and each nimber is its own inverse, since m+m=0*m + *m = 0. These properties arise directly from the corresponding algebraic traits of XOR on binary numbers. In the context of impartial games, nimber addition corresponds to the disjunctive sum of game positions G+HG + H, where a move consists of selecting one component and moving within it. The nimber of this sum is the XOR of the individual nimbers: (G+H)=GH* (G + H) = *G \oplus *H. This equivalence holds by the Sprague-Grundy theorem, which assigns nimbers as Grundy numbers to impartial games. The use of XOR traces back to the strategy for the game of Nim, where independent heaps behave as disjunctive sums, and the overall position is winning if the XOR of heap sizes is nonzero.[7] For small nimbers, the addition table under XOR is as follows:
+0123
00123
11032
22301
33210
For example, 11=01 \oplus 1 = 0 and 12=31 \oplus 2 = 3. This table illustrates the self-inverse property and the cyclic behavior for low values.

Multiplication

In combinatorial game theory, nimber multiplication, denoted $ *m \times *n $, is defined recursively as the minimum excluded value (mex) of the set consisting of all nim-additions (exclusive or) of the form $ (*i \times *n) \oplus (*m \times *j) \oplus (*i \times *j) $, where $ *i $ ranges over the options of $ *m $ (i.e., all nimbers less than $ *m $) and $ *j $ over the options of $ *n $ (all nimbers less than $ *n $).[8] This operation corresponds to the nimber of the selective compound of two impartial games, in which a player may move in the first component, the second, or both simultaneously. In practice, nimber multiplication for finite values is often computed using binary digital representations or precomputed tables, as the recursive definition builds upon smaller products.[8] Nimber multiplication is commutative ($ *m \times *n = *n \times *m )andassociative() and associative ( (*m \times *n) \times *p = *m \times (*n \times *p) ),anditdistributesovernimberaddition(), and it distributes over nimber addition ( (*m \oplus *n) \times *p = (*m \times *p) \oplus (*n \times *p) $). The nimber $ *0 $ acts as a multiplicative absorber ($ *0 \times *n = *0 $), while $ *1 $ serves as the multiplicative identity ($ *1 \times *n = *n $).[8] This multiplication was developed by John H. Conway as part of his broader framework for analyzing games through numbers, initially presented in his 1976 monograph On Numbers and Games, where it applies to partizan games but restricts naturally to the impartial case for nimbers.[8] For example, the product $ *2 \times *3 = *1 $, which arises from applying the mex formula to the relevant lower products: the set of values excludes 0, 2, and 3, yielding 1 as the minimum excluded nimber.[8] This illustrates how multiplication captures the strategic interaction in selective compounds, distinct from the disjunctive sum underlying nimber addition. Nimber multiplication embeds the nimbers as a subclass within the surreal numbers, specifically the ordinals equipped with these operations form the structure $ \mathbf{On}_2 $, a proper subfield of the surreals dedicated to impartial games.[8]

Examples and Tables

Addition and Multiplication Tables

Nimber addition, denoted as ⊕, corresponds to the bitwise exclusive-or (XOR) operation on the binary representations of the nimbers. This operation is associative, commutative, and every nimber is its own inverse (i.e., *n ⊕ *n = *0). The table below presents the results for nimbers from 0 to 7.
01234567
001234567
110325476
223016745
332107654
445670123
554761032
667452301
776543210
[6] Nimber multiplication, denoted as ⊗, is defined recursively as the minimum excludant (mex) of the set { G' ⊗ H ⊕ G ⊗ H' ⊕ G' ⊗ H' \mid G' \text{ is an option of } G, H' \text{ is an option of } H }, where options of *n are *0 through *(n-1). The nimbers {*0, *1, ..., *(2^{2^k} - 1)} form a finite field under these operations, isomorphic to GF(2^{2^k}). For example, up to *3 (k=1) and *15 (k=2). The table below gives the multiplication results for nimbers from 0 to 7 (note: some products exceed 7).
01234567
000000000
101234567
20231810119
3031212151314
404812621410
505101527813
606111314853
707914101334
[9] To extend these tables to higher nimbers, compute each entry using the recursive mex definition, evaluating the XOR sums of all relevant subproducts from lower nimbers until the smallest unused value is found. For instance, *2 ⊗ *2 = mex{0, 1, 2} = 3.[9]

Nim Examples

In the game of Nim under the normal play convention, where the player making the last move wins, each heap of size $ k $ has nimber $ k $. This direct isomorphism follows from the Sprague-Grundy theorem, as the possible moves from such a heap lead to positions with nimbers 0 through $ k-1 $, so the mex is $ k $.[10] For a single heap of size 3, the nimber is 3, a nonzero value indicating a first-player win; the optimal move is to remove all three stones, leaving nimber 0.[11] In a position with heaps of sizes 1, 2, and 3, the overall nimber is the bitwise XOR of the individual nimbers: $ 1 \oplus 2 \oplus 3 = 0 $, a losing position for the first player under optimal play, as any move leaves a nonzero XOR that the second player can correct.[10] The core strategy in Nim relies on nimbers to identify winning moves: from a position with nonzero total XOR, a player can always reduce one heap to make the new XOR zero. For example, consider heaps of sizes 1 and 3, with nimber $ 1 \oplus 3 = 2 \neq 0 .Thefirstplayerwinsbyremovingtwostonesfromthesize3heap,leavingheapsof1and1(. The first player wins by removing two stones from the size-3 heap, leaving heaps of 1 and 1 ( 1 \oplus 1 = 0 $); the second player then faces a symmetric position and cannot avoid leaving a nonzero XOR.[11] Nimber computations apply directly to normal-play Nim but require adjustment for the misère variant, where the last move loses. In misère Nim, players follow the normal XOR strategy until all remaining heaps have size at most 1, at which point the winner is the one facing an even number of size-1 heaps (contrasting the normal-play case).[10]

Applications

Standard Nim

Standard Nim is a classic impartial combinatorial game played by two players with multiple heaps of stones or counters. On each turn, a player selects a single heap and removes any positive number of objects from it, with at least one object required to be taken. The game proceeds under normal play convention, where the player who takes the last object wins.[12] Although variants of the game existed in ancient China and Europe as early as the 15th century, Charles L. Bouton formalized its rules and provided a complete mathematical analysis in his 1901 paper, naming it "Nim" after the German word for "take."[4][13] Bouton's analysis implicitly introduced the concept of nimbers through the use of binary representations of heap sizes, establishing that the game's outcome depends on the "binary digital sum"—equivalent to the bitwise XOR operation—of the heap sizes. A position is winning for the current player if this XOR is non-zero, as they can always make a move to a position where the XOR is zero, forcing the opponent into a losing position. Conversely, if the initial XOR is zero, the position is losing under optimal play, as any move will result in a non-zero XOR, allowing the opponent to respond by restoring it to zero. This strategy guarantees a win for the first player in non-zero XOR positions and for the second player otherwise.[4] In the framework of combinatorial game theory, each single-heap Nim position of size $ n $ has a nimber (or Grundy number) equal to $ n $, reflecting the mex of the nimbers of its options (heaps of sizes 0 through $ n-1 $, with nimber 0). The multi-heap game is the disjunctive sum of these single-heap games, where the overall nimber is the XOR of the individual heap nimbers, determining the game's value and equivalence to a single Nim heap of that nimber size.[10][6] This equivalence underpins the XOR strategy and extends Bouton's original theorems, proving that optimal play always leads to safe (zero-nimber) positions until the end.[4]

Domineering and Cram

Domineering is a partizan combinatorial game played on a grid where Left places vertical dominoes and Right places horizontal ones, covering two adjacent squares under normal play convention (last player to move wins).[14] Although inherently partizan, nimbers arise in impartial subsets of positions where available moves are symmetric, allowing analysis via Sprague-Grundy theorem for those normal play subgames.[15] Computations from endgame databases reveal nimbers up to *3 in such subsets; for instance, the smallest position with nimber *2 spans 11 squares, constructed by combining simpler impartial components via nim-addition (*1 + *1 = *0, but specific bridges yield *2), while *3 appears in 14-square configurations by adding a *1 to a *2 position.[15] These nimbers highlight the impartial aspects within Domineering's partizan framework, though full evaluation requires recursive mex calculations over subpositions rather than direct heap equivalences.[15] Cram serves as the impartial variant of Domineering, restricted to square or rectangular grids where both players may place either horizontal or vertical dominoes, making all moves available symmetrically.[16] As an impartial game, Cram positions are fully characterized by nimbers under normal play, computed recursively as the mex of the nimbers of all possible moves.[17] For small boards, explicit values include the 1×1 grid with nimber *0 (no legal moves, a terminal loss) and the 2×2 grid with *1 (a single move to two isolated *0 positions, yielding mex{*0} = *1).[17] Unlike Nim heaps, where nimbers directly correspond to heap sizes, Cram nimbers demand disjunctive sums over board decompositions, leading to intricate patterns; for example, outcomes for even-by-even rectangles favor the second player, while odd-by-odd boards require deeper recursion.[16] Research on Cram nimbers involves building endgame databases via alpha-beta search, covering all positions up to 6×6 boards and select larger ones like 3×21 (first-player win, nimber *n ≠ 0).[17] These tables demonstrate growing complexity, with 3×3 requiring evaluation of 7 nodes and 3×5 needing 254, but coverage remains incomplete for boards beyond 30 squares due to exponential state spaces in older analyses.[17] Heuristics and partitioning reduce computation, yet full nimber tables for arbitrary sizes elude closed forms, underscoring the challenges in tiling-based impartial games.[17]

Other Impartial Games

In impartial games beyond standard Nim, nimbers provide a means to assign Grundy values to positions, enabling the analysis of sums via XOR. One such game is subtract-a-square, a subtraction game where a player removes a positive square number (1, 4, 9, ...) of objects from a single heap.[18] The nimber for a heap of size nn, denoted g(n)g(n), is computed recursively as the minimum excludant (mex) of the nimbers of positions reachable in one move: g(n)=\mex{g(nk2)k1,k2n}g(n) = \mex \{ g(n - k^2) \mid k \geq 1, k^2 \leq n \}, with g(0)=0g(0) = 0.[18] These nimbers are not strictly periodic but can be efficiently computed up to large nn using algorithms like divide-and-conquer in O(nlog2n)O(n \log^2 n) time, revealing sparse "cold" positions (nimber 0) whose density approaches zero.[18] Another example is impartial (green or grey) Hackenbush, played on graphs where players alternately remove an edge (and any disconnected parts), with all edges accessible to both players.[19] Nimbers for positions are assigned via the Sprague-Grundy theorem, treating the graph as a sum of components. For a simple stalk—a path graph of edges grounded at one end—a single edge has nimber 1, as its only move leads to the empty position with nimber 0, so g=\mex{0}=1g = \mex\{0\} = 1.[19] For a stalk of two edges, moves lead to a single edge (nimber 1) or empty (0), yielding g=\mex{0,1}=2g = \mex\{0, 1\} = 2. In more complex graphs, such as a tree with branches, nimbers are found by XORing component values; for instance, a position equivalent to two disjoint single edges has nimber 11=01 \oplus 1 = 0, indicating a second-player win.[19] Games like Dawson's Chess and Kayles, which involve removing pawns or pins from chains, also rely on precomputed nimbers for linear positions. In Kayles, players knock down one or two adjacent pins in a row, and nimbers for a chain of length nn (denoted g(n)g(n)) form a sequence that is eventually periodic with period 12, as tabulated in seminal analyses; for example, g(0)=0g(0)=0, g(1)=1g(1)=1, g(2)=2g(2)=2, g(3)=3g(3)=3, up to larger values computed via mex over subchains.[20] These precomputations, detailed in Berlekamp, Conway, and Guy's foundational work, allow solving sums of such games by XORing nimbers.[20] Nimbers extend to computational tools for broader impartial game analysis. Software like CGSuite implements algorithms to compute and manipulate nimbers for custom rulesets, including graph games and subtraction variants, facilitating exact solutions for positions up to exponential complexity.[21]
User Avatar
No comments yet.