Nim
E653412
Nim is a classic impartial combinatorial game of removing objects from heaps, fundamental in game theory and central to the development of the Sprague–Grundy theorem.
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
finite game
ⓘ
mathematical game ⓘ normal-play game ⓘ two-player game ⓘ |
| hasCategory | abstract strategy game ⓘ |
| hasHistoricalAnalysisBy | Charles L. Bouton NERFINISHED ⓘ |
| hasInformationStructure |
no chance moves
ⓘ
no hidden information ⓘ |
| hasKeyConcept |
Grundy numbers
NERFINISHED
ⓘ
N-positions ⓘ Nim-sum ⓘ P-positions ⓘ Sprague–Grundy theorem NERFINISHED ⓘ binary representation of heap sizes ⓘ |
| hasMathematicalProperty |
disjunctive sum of impartial games reduces to a Nim heap via Grundy numbers
ⓘ
every position has a unique Grundy number ⓘ |
| hasMoveType | removal of objects from heaps ⓘ |
| hasObjective | force opponent into a position with no legal moves under normal play ⓘ |
| hasOutcomeClass | first player win under optimal play except when initial Nim-sum is zero ⓘ |
| hasPlayerCount | 2 ⓘ |
| hasRepresentation |
heaps of tokens
ⓘ
piles of matches ⓘ rows of stones ⓘ |
| hasRule |
on each move a player chooses exactly one heap
ⓘ
on each move a player removes one or more objects from the chosen heap ⓘ two players move alternately ⓘ under normal play the player who takes the last object wins ⓘ |
| hasRuleVariant | misère play where the player who takes the last object loses ⓘ |
| hasSolutionDescribedIn | Bouton’s theorem NERFINISHED ⓘ |
| hasStrategy | optimal play is to move to a position with Nim-sum zero ⓘ |
| hasTurnStructure | sequential turns ⓘ |
| hasVariant |
Moore’s Nim
NERFINISHED
ⓘ
Turning Toads and Frogs (as a related impartial game) NERFINISHED ⓘ Wythoff Nim NERFINISHED ⓘ misère Nim NERFINISHED ⓘ |
| hasWinningCondition |
Nim-sum of heap sizes equals zero for losing positions
ⓘ
Nim-sum of heap sizes nonzero for winning positions ⓘ |
| influenced |
algorithmic game solving methods
ⓘ
the general theory of impartial games NERFINISHED ⓘ |
| isCentralTo | development of the Sprague–Grundy theorem ⓘ |
| isExampleOf |
game solvable by complete mathematical analysis
ⓘ
normal-play impartial game ⓘ |
| isFundamentalTo | combinatorial game theory ⓘ |
| isUsedAs |
canonical example in teaching combinatorial game theory
ⓘ
test case for impartial game algorithms ⓘ |
| wasSolvedIn | 1901 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.