View source for Nim

{{Short description|Game of strategy}}

{{about|the mathematical game of strategy|the programming language|Nim (programming language)|other uses|Nim (disambiguation)}}

{{Infobox game
| name = Nim
| image = NimGame.svg
| caption = Matches set up in rows for a game of Nim. Players take turns to choose a row and remove any number of matches from it.
| years = 
| genre =  {{ubl|[[Mathematical game]]|[[abstract strategy game]]}}
| players = 2
| setup_time = 
| playing_time = 
| random_chance = None
| skills = 
}}

'''Nim''' is a [[mathematical game|mathematical]] [[combinatorial game]] in which two players take turns removing (or "nimming") objects from distinct heaps or piles. 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 or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

Nim is fundamental to the [[Sprague–Grundy theorem]], which essentially says that every [[impartial game]] is equivalent to a nim game with a single pile.

==History==
Variants of nim have been played since ancient times.<ref>
{{citation
 | last = Jorgensen | first = Anker Helms
 | doi = 10.1109/MAHC.2009.41
 | issue = 3
 | journal = IEEE Annals of the History of Computing
 | mr = 2767447
 | quote = The two-person mathematical game nim, which many believe originated in China, is probably one of the oldest games in the world.
 | pages = 44–53
 | title = Context and driving forces in the development of the early computer game Nimbi
 | url = http://muse.jhu.edu/journals/ieee_annals_of_the_history_of_computing/v031/31.3.jorgensen.html
 | volume = 31
 | year = 2009| bibcode = 2009IAHC...31c..44J
 | s2cid = 2833693
| url-access = subscription
 }}</ref> The game is said to have originated in [[China]]—it closely resembles the Chinese game of {{Transliteration|zh|jiǎn-shízǐ}} ({{lang|zh|捡石子}}), or "picking stones"<ref>
{{citation
 | last = Yaglom | first = I. M. | author-link = Isaak Yaglom
 | editor-last = Tabachnikov | editor-first = Serge |editor-link=Sergei Tabachnikov
 | contribution = Two games with matchsticks
 | isbn = 9780821821718
 | pages = 1–8
 | publisher = [[American Mathematical Society]]
 | series = Mathematical world
 | title = Kvant Selecta: Combinatorics, I, Volume 1
 | url = https://books.google.com/books?id=yID37VIW-t8C&pg=PA1
  |access-date=
 | volume = 17
 | year = 2001
}}</ref>—but the origin is uncertain; the earliest European references to nim are from the beginning of the 16th century. Its current name was coined by [[Charles L. Bouton]] of [[Harvard University]], who also developed the complete theory of the game in 1901,<ref>
{{citation
 | last = Bouton | first = C. L. | author-link = Charles L. Bouton
 | doi = 10.2307/1967631
 | issue = 14
 | journal = [[Annals of Mathematics]]
 | pages = 35–39
 | title = Nim, ''a game with a complete mathematical theory''
 | volume = 3
 | year = 1901–1902| jstor = 1967631
}}</ref> but the origins of the name were never fully explained. The ''[[Oxford English Dictionary]]'' derives the name from the German verb {{lang|de|[[wikt:nimm|nimm]]}}, meaning "take".

At the [[1939 New York World's Fair]], [[Westinghouse Electric (1886)|Westinghouse]] displayed a machine, the [[Nimatron]], that played nim.<ref>{{cite book|last=Flesch|first=Rudolf|title=The Art of Clear Thinking|year=1951|publisher=Harper and Brothers Publishers|location=New York|page=3}}</ref> From May&nbsp;11 to October&nbsp;27, 1940, only a few people were able to beat the machine in that six-month period; if they did, they were presented with a coin that said "Nim Champ".<ref>{{Cite web |last=Kellem |first=Betsy |date=2022-03-01 |title=The Nimatron |url=https://daily.jstor.org/the-nimatron/ |url-status=live |archive-url=https://web.archive.org/web/20230628121301/https://daily.jstor.org/the-nimatron/ |archive-date=2023-06-28 |access-date=2023-06-28 |website=JSTOR Daily}}</ref> It was also one of the first-ever electronic computerized games. [[Ferranti]] built a [[Nimrod (computer)|nim-playing computer]] which was displayed at the [[Festival of Britain]] in 1951. In 1952, Herbert Koppel, Eugene Grant and Howard Baller, engineers from the W. L. Maxson Corporation, developed a machine weighing {{convert|50|lbs|kg|order=flip}} which played nim against a human opponent and regularly won.<ref>{{Cite news |url=http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053 |title=The Talk of the Town – It |first1=Eugene F. |last1=Grant |first2=Rex |last2=Lardner |date=August 2, 1952 |newspaper=[[The New Yorker]]}}</ref> A nim playing machine has been described made from [[tinkertoy]]s.<ref>{{cite web|url = http://harveycohen.net/papers/80-Nim_Playing_Machine.pdf|title=How to Construct NIM Playing Machine | first=Harvey A. | last=Cohen}}</ref>

The game of nim was the subject of [[Martin Gardner]]'s February 1958 [[Mathematical Games column]] in ''[[Scientific American]]''. A version of nim is played—and has symbolic importance—in the [[French New Wave]] film ''[[Last Year at Marienbad]]'' (1961).<ref>
{{citation
 | last = Morrissette | first = Bruce
 | doi = 10.2307/2929672
 | journal = Yale French Studies
 | pages = 159–167
 | title = Games and game structures in Robbe-Grillet
 | issue = 41
 | year = 1968| jstor = 2929672
}}. Morrissette writes that [[Alain Robbe-Grillet]], one of the screenwriters for the film, "thought he had invented" the game.</ref>

== Game play and illustration ==
Nim is typically played as a [[misère game]], in which the player to take the last object loses. Nim can also be played as a "normal play" game whereby the player taking the last object wins.  In either normal play or a misère game, when there is exactly one heap with at least two objects, the player who takes next can easily win. If this removes either all or all but one objects from the heap that has two or more, then no heaps will have more than one object, so the players are forced to alternate removing exactly one object until the game ends. If the player leaves an even number of non-zero heaps (as the player would do in normal play), the player takes last; if the player leaves an odd number of heaps (as the player would do in misère play), then the other player takes last.

The normal game is between two players and is played with three heaps of any number of objects. The two players alternate taking any number of objects from any one of the heaps. The goal is to be the last to take an object. In misère play, the goal is instead to ensure that the opponent is forced to take the last remaining object.

The following example of a normal game is played between fictional players [[Bob and Alice]], who start with heaps of three, four and five objects.

{| class="wikitable"
|-
!Heap A
!Heap B
!Heap C
!Move
|-
| 3 || 4 || 5 || Game begins
|-
| 1 || 4 || 5 || Bob takes 2 from A
|-
| 1 || 4 || 2 || Alice takes 3 from C
|-
| 1 || 3 || 2 || Bob takes 1 from B
|-
| 1 || 2 || 2 || Alice takes 1 from B
|-
| 0 || 2 || 2 || Bob takes entire A heap, leaving two 2s
|-
| 0 || 1 || 2 || Alice takes 1 from B
|-
| 0 || 1 || 1 || Bob takes 1 from C leaving two 1s. (''In misère play he would take 2 from C leaving [0, 1, 0]'')
|-
| 0 || 0 || 1 || Alice takes 1 from B
|-
| 0 || 0 || 0 || Bob takes entire C heap and wins
|}

== Winning positions ==
The practical strategy to win at the game of nim is for a player to get the other into one of the following positions, and every successive turn afterwards they should be able to make one of the smaller positions. Only the last move changes between misère and normal play.

{| class="wikitable"
|-
!2 heaps
!3 heaps
!4 heaps
|-
|1 1 *
|1 1 1 **
|1 1 1 1 *
|-
|2 2
|1 2 3
|1 1 n n
|-
|3 3
|1 4 5
|1 2 4 7
|-
|4 4
|1 6 7
|1 2 5 6
|-
|5 5
|1 8 9
|1 3 4 6
|-
|6 6 
|2 4 6
|1 3 5 7
|-
|7 7
|2 5 7
|2 3 4 5
|-
|8 8
|3 4 7
|2 3 6 7
|-
|9 9
|3 5 6
|2 3 8 9
|-
|n n
|4 8 12
|4 5 6 7
|-
|
|4 9 13
|4 5 8 9
|-
|
|5 8 13
|''n'' ''n'' ''m'' ''m''
|-
|
|5 9 12
|''n'' ''n'' ''n'' ''n''
|-
| colspan = "3" | * Only valid for normal play.<br/>** Only valid for misère.

|}

For the generalisations, ''n'' and ''m'' can be any value >&nbsp;0, and they may be the same.

== Mathematical theory ==
Normal-play nim (or more precisely the system of [[nimber]]s) is fundamental to the [[Sprague–Grundy theorem]], which essentially says that in normal play every [[impartial game]] is equivalent to a nim heap that yields the same outcome when played in parallel with other normal play impartial games (see [[disjunctive sum]]).

While all normal-play impartial games can be assigned a nim value, that is not the case under the misère convention. Only [[Genus theory#Tame|tame games]] can be played using the same strategy as misère nim.

Nim is a special case of a [[poset game]] where the [[poset]] consists of disjoint [[Total order|chains]] (the heaps).

The evolution graph of the game of nim with three heaps is the same as three branches of the evolution graph of the [[Ulam–Warburton automaton]].<ref>{{cite arXiv |eprint=1405.5942|last1=Khovanova|first1=Tanya|last2=Xiong|first2=Joshua|title=Nim Fractals|class=math.CO|year=2014}}</ref>

Nim has been mathematically [[solved game|solved]] for any number of initial heaps and objects, and there is an easily calculated way to determine which player will win and which winning moves are open to that player.

The key to the theory of the game is the [[Binary numeral system|binary]] [[digital sum in base b|digital sum]] of the heap sizes, i.e., the sum (in binary), neglecting all carries from one digit to another. This operation is also known as "[[bitwise xor]]" or "vector addition over [[finite field|'''GF'''(2)]]" (bitwise addition modulo 2). Within [[combinatorial game theory]] it is usually called the '''nim-sum''', as it will be called here. The nim-sum of ''x'' and ''y'' is written {{nowrap|''x'' ⊕ ''y''}} to distinguish it from the ordinary sum, {{nowrap|''x'' + ''y''}}. An example of the calculation with heaps of size 3, 4, and 5 is as follows:

 [[Binary numeral system|Binary]] [[Decimal]]
 &nbsp;
   011<sub>2</sub>    3<sub>10</sub>    Heap A
   100<sub>2</sub>    4<sub>10</sub>    Heap B
   101<sub>2</sub>    5<sub>10</sub>    Heap C
   ---
   010<sub>2</sub>    2<sub>10</sub>    The nim-sum of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2

An equivalent procedure, which is often easier to perform mentally, is to express the heap sizes as sums of distinct [[Exponentiation|powers]] of 2, cancel pairs of equal powers, and then add what is left:

 3 = 0 + 2 + 1 =     2   1      Heap A
 4 = 4 + 0 + 0 = 4              Heap B
 5 = 4 + 0 + 1 = 4       1      Heap C
 --------------------------------------------------------------------
 2 =                 2          What is left after canceling 1s and 4s

In normal play, the winning strategy is to finish every move with a nim-sum of 0. This is always possible if the nim-sum is not zero before the move. If the nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the nim-sum of all the heap sizes. Find a heap where the nim-sum of X and heap-size is less than the heap-size; the winning strategy is to play in such a heap, reducing that heap to the nim-sum of its original size with X. In the example above, taking the nim-sum of the sizes is {{nowrap|1=''X'' = 3 ⊕ 4 ⊕ 5 = 2}}. The nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are
: ''A'' ⊕ ''X'' = 3 ⊕ 2 = 1      [Since (011) ⊕ (010) = 001 ]
: ''B'' ⊕ ''X'' = 4 ⊕ 2 = 6
: ''C'' ⊕ ''X'' = 5 ⊕ 2 = 7
The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects).

As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make the heaps equal. After that, no matter what move the opponent makes, the player can make the same move on the other heap, guaranteeing that they take the last object.

When played as a misère game, nim strategy is different only when the normal play move would leave only heaps of size one. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps).

These strategies for normal play and a misère game are the same until the number of heaps with at least two objects is exactly equal to one. At that point, the next player removes either all objects (or all but one) from the heap that has two or more, so no heaps will have more than one object (in other words, so all remaining heaps have exactly one object each), so the players are forced to alternate removing exactly one object until the game ends. In normal play, the player leaves an even number of non-zero heaps, so the same player takes last; in misère play, the player leaves an odd number of non-zero heaps, so the other player takes last.

In a misère game with heaps of sizes three, four and five, the strategy would be applied like this:

{| class="wikitable"
! A !! B !! C !! Nim-sum !! Move
|-
| 3 || 4 || 5 || 010<sub>2</sub>=2<sub>10</sub> || I take 2 from A, leaving a sum of 000, so I will win.
|-
| 1 || 4 || 5 || 000<sub>2</sub>=0<sub>10</sub> || You take 2 from C
|-
| 1 || 4 || 3 || 110<sub>2</sub>=6<sub>10</sub> || I take 2 from B
|-
| 1 || 2 || 3 || 000<sub>2</sub>=0<sub>10</sub> || You take 1 from C
|-
| 1 || 2 || 2 || 001<sub>2</sub>=1<sub>10</sub> || I take 1 from A
|-
| 0 || 2 || 2 || 000<sub>2</sub>=0<sub>10</sub> || You take 1 from C
|- 
| 0 || 2 || 1 || 011<sub>2</sub>=3<sub>10</sub> || The normal play strategy would be to take 1 from B, leaving an even number (2) heaps of size 1.  For misère play, I take the entire B heap, to leave an odd number (1) of heaps of size 1.
|-
| 0 || 0 || 1 || 001<sub>2</sub>=1<sub>10</sub> || You take 1 from C, and lose.
|}

== Proof of the winning formula ==

The soundness of the optimal strategy described above was demonstrated by C. Bouton.

'''Theorem'''. In a normal nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is not zero. Otherwise, the second player has a winning strategy.

''Proof:'' Notice that the nim-sum (⊕) obeys the usual [[associativity|associative]] and [[commutativity|commutative]] laws of addition (+) and also satisfies an additional property, ''x''&nbsp;⊕&nbsp;''x''&nbsp;=&nbsp;0.

Let {{nowrap|''x''<sub>1</sub>, ..., ''x<sub>n</sub>''}} be the sizes of the heaps before a move, and ''y''<sub>1</sub>,&nbsp;...,&nbsp;''y<sub>n</sub>'' the corresponding sizes after a move. Let ''s''&nbsp;=&nbsp;''x''<sub>1</sub>&nbsp;⊕&nbsp;...&nbsp;⊕&nbsp;''x<sub>n</sub>'' and ''t''&nbsp;=&nbsp;''y''<sub>1</sub>&nbsp;⊕&nbsp;...&nbsp;⊕&nbsp;''y<sub>n</sub>''. If the move was in heap ''k'', we have ''x<sub>i</sub>''&nbsp;=&nbsp;''y<sub>i</sub>'' for all {{nowrap|''i'' ≠ ''k''}}, and ''x<sub>k</sub>''&nbsp;>&nbsp;''y<sub>k</sub>''. By the properties of ⊕ mentioned above, we have

<math display=block>
\begin{align}
t & = 0 \oplus t \\
& = s \oplus s \oplus t \\
& = s \oplus (x_1 \oplus \cdots \oplus x_n) \oplus (y_1 \oplus \cdots \oplus y_n) \\
& = s \oplus (x_1 \oplus y_1) \oplus \cdots \oplus (x_n \oplus y_n) \\
& = s \oplus 0 \oplus \cdots \oplus 0 \oplus (x_k \oplus y_k) \oplus 0 \oplus \cdots \oplus 0 \\
& = s \oplus x_k \oplus y_k \\[10pt]
(*) \quad t & = s \oplus x_k \oplus y_k
\end{align}
</math>

That is, to update the total nim sum <math> s </math> after updating the <math> x_k </math> heap, we need to cancel it from <math> s </math> by nim summing with <math> x_k </math>, and then nim sum in <math> y_k </math>.

The theorem follows by induction on the length of the game from these two lemmas.

'''Lemma 1'''. If ''s'' = 0, then ''t'' ≠ 0 no matter what move is made.

''Proof:'' If there is no possible move, then the lemma is [[vacuous truth|vacuously true]] (and the first player loses the normal play game by definition). Otherwise, any move in heap ''k'' will produce ''t''&nbsp;=&nbsp;''x<sub>k</sub>''&nbsp;⊕&nbsp;''y<sub>k</sub>'' from (*). This number is nonzero, since ''x<sub>k</sub>''&nbsp;≠&nbsp;''y<sub>k</sub>''.

'''Lemma 2'''. If ''s'' ≠ 0, it is possible to make a move so that ''t'' = 0.

''Proof:'' Let ''d'' be the position of the leftmost (most significant) nonzero bit in the binary representation of ''s'', and choose ''k'' such that the ''d''th bit of ''x<sub>k</sub>'' is also nonzero. (Such a ''k'' must exist, since otherwise the ''d''th bit of ''s'' would be 0.)
Then letting ''y<sub>k</sub>''&nbsp;=&nbsp;''s''&nbsp;⊕&nbsp;''x<sub>k</sub>'', we claim that ''y<sub>k</sub>''&nbsp;<&nbsp;''x<sub>k</sub>'': all bits to the left of ''d'' are the same in ''x<sub>k</sub>'' and ''y<sub>k</sub>'', bit ''d'' decreases from 1 to 0 (decreasing the value by 2<sup>''d''</sup>), and any change in the remaining bits will amount to at most 2<sup>''d''</sup>−1. The first player can thus make a move by taking ''x<sub>k</sub>''&nbsp;−&nbsp;''y<sub>k</sub>'' objects from heap ''k'', then
 ''t'' = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>''           (by (*))
   = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ (''s'' ⊕ ''x<sub>k</sub>'')
   = 0.

The modification for misère play is demonstrated by noting that the modification first arises in a position that has only one heap of size 2 or more. Notice that in such a position ''s'' ≠ 0, and therefore this situation has to arise when it is the turn of the player following the winning strategy. The normal play strategy is for the player to reduce this to size 0 or 1, leaving an even number of heaps with size 1, and the misère strategy is to do the opposite. From that point on, all moves are forced.

== Variations ==

=== The subtraction game ===
<imagemap>
File:Subtraction_game_SMIL.svg|thumb|Interactive subtraction game: Players take turns removing 1, 2 or 3 objects from an initial pool of 21 objects. The player taking the last object wins.
default [http://upload.wikimedia.org/wikipedia/commons/4/4d/Subtraction_game_SMIL.svg]
</imagemap>
In another game which is commonly known as nim (but is better called the [[subtraction game]]), an upper bound is imposed on the number of objects that can be removed in a turn. Instead of removing arbitrarily many objects, a player can only remove 1 or 2 or ... or ''k'' at a time. This game is commonly played in practice with only one heap.

Bouton's analysis carries over easily to the general multiple-heap version of this game. The only difference is that as a first step, before computing the nim-sums we must reduce the sizes of the heaps [[modular arithmetic|modulo]] ''k''&nbsp;+&nbsp;1. If this makes all the heaps of size zero (in misère play), the winning move is to take ''k'' objects from one of the heaps. In particular, in ideal play from a single heap of ''n'' objects, the second player can win [[if and only if]]

* ''0''&nbsp;=&nbsp;n&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (in normal play), or
* ''1''&nbsp;=&nbsp;n&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (in misère play).

This follows from calculating the [[nim-sequence]] of ''S''(1, 2, ..., ''k''),

<math display="block">0.123\ldots k0123\ldots k0123\ldots = \dot0.123\ldots\dot{k}, </math>

from which the strategy above follows by the [[Sprague–Grundy theorem]].

=== The 21 game ===
{{See also|21 (drinking game)}}
The game "21" is played as a misère game with any number of players who take turns saying a number. The first player says "1" and each player in turn increases the number by 1, 2, or 3, but may not exceed 21; the player forced to say "21" loses. This can be modeled as a subtraction game with a heap of {{nowrap|21 − ''n''}} objects. The winning strategy for the two-player version of this game is to always say a multiple of 4; it is then guaranteed that the other player will ultimately have to say 21; so in the standard version, wherein the first player opens with "1", they start with a losing move.

The 21 game can also be played with different numbers, e.g., "Add at most 5; lose on 34".

A sample game of 21 in which the second player follows the winning strategy:

{| class="wikitable"
! Player !! Number
|-
| 1 || 1
|-
| 2 || 4
|-
| 1 || 5, 6 or 7
|-
| 2 || 8
|-
| 1 || 9, 10 or 11
|-
| 2 || 12
|-
| 1 || 13, 14 or 15
|-
| 2 || 16
|-
| 1 || 17, 18 or 19
|-
| 2 || 20
|-
| 1 || 21
|}

=== The 100 game ===
A similar version is the "100 game": Two players start from 0 and alternately add a number from 1 to 10 to the sum. The player who reaches 100 wins. The winning strategy is to reach a number in which the digits are subsequent (e.g., 01, 12, 23, 34,...) and control the game by jumping through all the numbers of this sequence. Once a player reaches 89, the opponent can only choose numbers from 90 to 99, and the next answer can in any case be 100.

=== A multiple-heap rule ===

{{See also|Wythoff's game}}
In another variation of nim, besides removing any number of objects from a single heap, one is permitted to remove the same number of objects from each heap.

=== Circular nim ===

{{See also|Kayles}}
Yet another variation of nim is "circular nim", wherein any number of objects are placed in a circle and two players alternately remove one, two or three adjacent objects. For example, starting with a circle of ten objects,

 . . . . . . . . . .

three objects are taken in the first move

 _ . . . . . . . _ _

then another three

 _ . _ _ _ . . . _ _

then one

 _ . _ _ _ . . _ _ _

but then three objects cannot be taken out in one move.

=== Grundy's game ===

In [[Grundy's game]], another variation of nim, a number of objects are placed in an initial heap and two players alternately divide a heap into two nonempty heaps of different sizes. Thus, six objects may be divided into piles of 5+1 or 4+2, but not 3+3. Grundy's game can be played as either misère or normal play.

=== Greedy nim ===

Greedy nim is a variation wherein the players are restricted to choosing stones from only the largest pile.<ref name="Greedy Nim">{{cite book | title=Winning Ways for your Mathematical Plays | edition=2nd | publisher=A K Peters Ltd | year=2001 | volume=4 vols.}};
* {{cite book|title=vol. 1|isbn=978-1-56881-130-7|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}};
* {{cite book|title=vol. 2|isbn=978-1-56881-142-0|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; 
* {{cite book|title=vol. 3|isbn=978-1-56881-143-7|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; 
* {{cite book|title=vol. 4|isbn=978-1-56881-144-4|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2004-06-15}}
</ref> It is a finite [[impartial game]]. Greedy nim misère has the same rules as greedy nim, but the last player able to make a move loses.

Let the largest number of stones in a pile be ''m'' and the second largest number of stones in a pile be ''n''. Let ''p''<sub>''m''</sub> be the number of piles having ''m'' stones and ''p''<sub>''n''</sub> be the number of piles having ''n'' stones. Then there is a theorem that game positions with ''p''<sub>''m''</sub> even are ''P'' positions.<ref name="Nim restrictions">
{{cite journal
| first1 = M. H.
| last1 = Albert
| first2 = R. J.
| last2 = Nowakowski
| title = Nim Restrictions
| year= 2004
| journal= Integers
| page = 2
| url= http://www.emis.de/journals/INTEGERS/papers/eg1/eg1.pdf   |access-date=
|volume=4  | article-number= G01
|zbl= 1081.91005
}}</ref> This theorem can be shown by considering the positions where ''p''<sub>''m''</sub> is odd. If ''p''<sub>''m''</sub> is larger than 1, all stones may be removed from this pile to reduce ''p''<sub>''m''</sub> by 1 and the new ''p''<sub>''m''</sub> will be even. If ''p''<sub>''m''</sub> = 1 (i.e., the largest heap is unique), there are two cases:
* If ''p''<sub>''n''</sub> is odd, the size of the largest heap is reduced to ''n'' (so now the new ''p''<sub>''m''</sub> is even).
* If ''p''<sub>''n''</sub> is even, the largest heap is removed entirely, leaving an even number of largest heaps.
Thus, there exists a move to a state where ''p''<sub>''m''</sub> is even. Conversely, if ''p''<sub>''m''</sub> is even, if any move is possible (''p''<sub>''m''</sub> ≠ 0), then it must take the game to a state where ''p''<sub>''m''</sub> is odd. The final position of the game is even (''p''<sub>''m''</sub> = 0). Hence, each position of the game with ''p''<sub>''m''</sub> even must be a ''P'' position.

=== Index-''k'' nim ===

A generalization of multi-heap nim was called "nim<math>{}_k</math>" or "index-''k''" nim by [[E. H. Moore]],<ref>{{cite journal | last=Moore | first=E. H. | title=A Generalization of the Game Called Nim | journal=Annals of Mathematics | publisher=[Annals of Mathematics, Trustees of Princeton University on Behalf of the Annals of Mathematics, Mathematics Department, Princeton University] | volume=11 | issue=3 | year=1910 |doi= 10.2307/1967321 | jstor=1967321 | pages=93–94 | url=http://www.jstor.org/stable/1967321 | access-date=| url-access=subscription }}</ref> who analyzed it in 1910. In index-''k'' nim, instead of removing objects from only one heap, players can remove objects from at least one but up to ''k'' different heaps. The number of elements that may be removed from each heap may be either arbitrary or limited to at most ''r'' elements, like in the "subtraction game" above.

The winning strategy is as follows: Like in ordinary multi-heap nim, one considers the binary representation of the heap sizes (or heap sizes modulo ''r''&nbsp;+&nbsp;1). In ordinary nim one forms the XOR-sum (or sum modulo 2) of each binary digit, and the winning strategy is to make each XOR sum zero. In the generalization to index-''k'' nim, one forms the sum of each binary digit modulo ''k''&nbsp;+&nbsp;1.

Again, the winning strategy is to move such that this sum is zero for every digit. Indeed, the value thus computed is zero for the final position, and given a configuration of heaps for which this value is zero, any change of at most ''k'' heaps will make the value non-zero. Conversely, given a configuration with non-zero value, one can always take from at most ''k'' heaps, carefully chosen, so that the value will become zero.

=== Building nim ===

Building nim is a variant of nim wherein the two players first construct the game of nim. Given ''n'' stones and ''s'' empty piles, the players, alternating turns, place exactly one stone into a pile of their choice.<ref>{{cite arXiv|last1=Larsson|first1=Urban|last2=Heubach|first2=Silvia|author2-link= Silvia Heubach |last3=Dufour|first3=Matthieu|last4=Duchêne|first4=Eric|title=Building Nim|eprint=1502.04068|class=cs.DM|year=2015}}</ref> Once all the stones are placed, a game of Nim begins, starting with the next player that would move. This game is denoted ''BN(n,s)''.

=== Higher-dimensional nim ===

''n''-d nim is played on a <math>k_1\times\dots\times k_n</math> board, whereon any number of continuous pieces can be removed from any hyper-row. The starting position is usually the full board, but other options are allowed.<ref>{{cite web|url=http://poj.org/problem?id=1021 |title=1021 - 2D-Nim |publisher=Poj.org |access-date=2019-01-09}}</ref>

=== Graph nim ===

The starting board is a disconnected graph, and players take turns to remove adjacent vertices.<ref>{{Cite thesis |last=Erickson |first=Lindsay Anne |date=2011 |title=The Game of Nim on Graphs |url=https://library.ndsu.edu/ir/handle/10365/32839 |type= PhD thesis |series= Mathematics Doctoral Work |publisher=North Dakota State University |language=en |hdl= 10365/32839}}</ref>

=== Candy nim ===

Candy nim is a version of normal-play nim in which players try to achieve two goals at the same time: taking the last object (in this case, candy) and taking the maximum number of candies by the end of the game.<ref>{{Cite arXiv|last=Rubinstein-Salzedo|first=Simon|date=18 May 2018|title=P Play in Candy Nim|class=math.CO |eprint=1805.07019}}</ref>

== See also ==
{{colbegin}}
* ''[[Android Nim]]''
* [[Chomp]]
* [[Dr. NIM]]
* [[Fibonacci nim]]
* [[Fuzzy game]]
* [[Hackenbush]]
* [[Notakto]]
* [[Octal games]]
* [[Raymond Redheffer]]
* [[Scarney]]
* [[Star (game theory)]]
* [[Subtract a square]]
* [[Tri-nim]]
* [[Turing Tumble]]
* [[Zero game]]
{{colend}}

== References ==
{{reflist}}

== Further reading ==
* W. W. Rouse Ball: ''Mathematical Recreations and Essays'', The Macmillan Company, 1947.
* John D. Beasley: ''The Mathematics of Games'', Oxford University Press, 1989.
* Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy: ''[[Winning Ways for your Mathematical Plays]]'', Academic Press, Inc., 1982.
* [[Manfred Eigen]] and [[Ruthild Winkler]]: ''Laws of the Game'', Princeton University Press, 1981.
* Walter R. Fuchs: ''Computers: Information Theory and Cybernetics'', Rupert Hart-Davis Educational Publications, 1971.
* G. H. Hardy and E. M. Wright: ''An Introduction to the Theory of Numbers'', Oxford University Press, 1979.
* Edward Kasner and James Newman: ''[[Mathematics and the Imagination]]'', Simon and Schuster, 1940.
* M. Kaitchik: ''Mathematical Recreations'', W. W. Norton, 1942.
* Donald D. Spencer: ''Game Playing with Computers'', Hayden Book Company, Inc., 1968.

== External links ==
{{commons category}}
* "[http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053 50-pound computer plays Nim]" – ''[[The New Yorker]]'' - "Talk of the Town" August, 1952 {{subscription required}}
* [https://web.archive.org/web/20080820154432/http://www.cut-the-knot.org/ctk/May2001.html The hot game of Nim] – Nim theory and connections with other games at [[cut-the-knot]]
* [http://www.cut-the-knot.org/nim_st.shtml Nim] and 2-dimensional [http://www.cut-the-knot.org/Games/SuperNim/SNim.shtml SuperNim] at [[cut-the-knot]]

{{Authority control}}

[[Category:Mathematical games]]
[[Category:Combinatorial game theory]]
[[Category:Articles containing proofs]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Solved games]]

[[cs:Rozšířená forma#NIM]]