Nim
21885
225679017
2008-07-14T21:29:56Z
Mike.lifeguard
2467188
[[WP:UNDO|Undid]] revision 224449957 by [[Special:Contributions/83.114.77.148|83.114.77.148]] ([[User talk:83.114.77.148|talk]])
{{otheruses}}
'''Nim''' is a two-player [[mathematical game|mathematical]] [[game of strategy]] in which players take turns removing objects from distinct heaps. 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.
Variants of Nim have been played since ancient times. The game is said to have originated in [[China]] (it closely resembles the Chinese game of "Jianshizi", or "picking stones"), 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, but the origins of the name were never fully explained. The name is probably derived from [[German language|German]] ''nimm!'' meaning "take!", or the obsolete English verb ''nim'' of the same meaning. It should also be noted that turning the word ''NIM'' upside-down and backwards results in ''WIN'' (see [[Ambigram]]).
Nim is usually played as a ''[[misère]]'' game, in which the player to take the last object loses. Nim can also be played as a ''[[misère game|normal play]]'' game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.
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]]).
A version of Nim is played – and has symbolic importance– in the [[French New Wave]] film ''[[Last Year at Marienbad]]'' ([[1961]]).
==Illustration==
A normal play game may start with heaps of 3, 4 and 5 objects:
In order to win always leave an even total number of 1's, 2's, and 4's.
Sizes of heaps Moves
A B C
3 4 5 I take 2 from A
1 4 5 You take 3 from C
1 4 2 I take 1 from B
1 3 2 You take 1 from B
1 2 2 I take entire A heap leaving two 2's.
0 2 2 You take 1 from B
0 1 2 I take 1 from C leaving two 1's. (''In misère play I would take 2 from C leaving (0, 1, 0).'')
0 1 1 You take 1 from B
0 0 1 I take entire C heap and win.
== Mathematical theory ==
Nim has been mathematically solved for any number of initial heaps and objects; that is, there is an easily-calculated way to determine which player will win and what winning moves are open to that player. In a game that starts with heaps of 3, 4, and 5, the first player will win with optimal play, whether the misère or normal play convention is followed.
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, that is, the sum (in binary) neglecting all carries from one digit to another. This operation is also known as [[exclusive or]] (xor) or vector addition over [[finite field|'''GF'''(2)]]. Within [[combinatorial game theory]] it is usually called the '''nim-sum''', as will be done here. The nim-sum of ''x'' and ''y'' is written ''x'' ⊕ ''y'' to distinguish it from the ordinary sum, ''x'' + ''y''. An example of the calculation with heaps of size 3, 4, and 5 is as follows:
[[Binary numeral system|Binary]] [[Decimal]]
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's left:
3 = 0 + 2 + 1 = 2 <s>1</s> Heap A
4 = 4 + 0 + 0 = <s>4</s> Heap B
5 = 4 + 0 + 1 = <s>4</s> <s>1</s> Heap C
---
2 = 2 What's left after cancelling 1s and 4s
In normal play, the winning strategy is to finish every move with a Nim-sum of 0, which 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. Take the Nim-sum of each of the heap sizes with X, and find a heap whose size decreases. 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 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
: 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 your opponent makes, you can make the same move on the other heap, guaranteeing that you take the last object.
When played as a misère game, Nim strategy is different only when the normal play move would leave no heap of size 2 or larger. In that case, the correct move is to leave an odd number of heaps of size 1 (in normal play, the correct move would be to leave an even number of such heaps).
In a misère game with heaps of sizes 3, 4 and 5, the strategy would be applied like this:
A B C Nim-sum
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 first player has a winning strategy if and only if the nim-sum of the sizes of the heaps is nonzero. 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'' ⊕ ''x'' = 0 (technically speaking, the nonnegative integers under ⊕ form an [[Abelian group]] of [[exponent of a group|exponent]] 2).
Let ''x''<sub>1</sub>, ..., ''x<sub>n</sub>'' be the sizes of the heaps before a move, and ''y''<sub>1</sub>, ..., ''y<sub>n</sub>'' the corresponding sizes after a move. Let ''s'' = ''x''<sub>1</sub> ⊕ ... ⊕ ''x<sub>n</sub>'' and ''t'' = ''y''<sub>1</sub> ⊕ ... ⊕ ''y<sub>n</sub>''. If the move was in heap ''k'', we have ''x<sub>i</sub>'' = ''y<sub>i</sub>'' for all ''i'' ≠ ''k'', and ''x<sub>k</sub>'' > ''y<sub>k</sub>''. By the properties of ⊕ mentioned above, we have
''t'' = 0 ⊕ ''t''
= ''s'' ⊕ ''s'' ⊕ ''t''
= ''s'' ⊕ (''x''<sub>1</sub> ⊕ ... ⊕ ''x<sub>n</sub>'') ⊕ (''y''<sub>1</sub> ⊕ ... ⊕ ''y<sub>n</sub>'')
= ''s'' ⊕ (''x''<sub>1</sub> ⊕ ''y''<sub>1</sub>) ⊕ ... ⊕ (''x<sub>n</sub>'' ⊕ ''y<sub>n</sub>'')
= ''s'' ⊕ 0 ⊕ ... ⊕ 0 ⊕ (''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>'') ⊕ 0 ⊕ ... ⊕ 0
= ''s'' ⊕ ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>''
(*) ''t'' = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>''.
The theorem follows by induction on the length of the game from these two lemmata.
'''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'' = ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>'' from (*). This number is nonzero, since ''x<sub>k</sub>'' ≠ ''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>'' = ''s'' ⊕ ''x<sub>k</sub>'', we claim that ''y<sub>k</sub>'' < ''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>''k''</sup>), and any change in the remaining bits will amount to at most 2<sup>''k''</sup>−1. The first player can thus make a move by taking ''x<sub>k</sub>'' − ''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. 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.
== Other variations of the game ==
In another game which is commonly known as Nim (but is better called the [[subtraction game]] ''S''(1,2,...,''k'')), an upper bound is imposed on the number of stones that can be removed in a turn. Instead of removing arbitrarily many stones, 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 (for instance with ''k'' = 3 in the game ''Thai 21'' on [[Survivor: Thailand]], where it appeared as an Immunity Challenge).
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'' + 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 a play from a single heap of ''n'' stones, the second player can win [[if and only if|iff]]
: ''n'' ≡ 0 (mod ''k''+1) (in normal play), or
: ''n'' ≡ 1 (mod ''k''+1) (in misère play).
This follows from calculating the [[nim-sequence]] of ''S''(1,2,...,''k''),
: <math>0.123...k0123...k0123... = \dot0.123\ldots\dot{k}</math>,
from which the strategy above follows by the [[Sprague-Grundy theorem]].
In misère play with the game "21", where loss is achieved through speaking 21, only 1, 2 or 3 can be taken at once. Counting starts from 1 and switches from one player to another, and any amount of players can take part, within reason. With two players, by the above rules the way to win is to leave a multiple of k+1 (k being 3), +1 - that is, leave a multiple of 4, plus 1. Indeed any number may be chosen to start.
A further variation of Nim is where it is possible to remove stones from both rows, as long as you remove the same number of stones from each row.
A yet another variation of Nim is 'Circular Nim' where any number of pieces are placed in a circle, and 1, 2 or 3 are taken alternately between 2 players. These pieces must be touching each other in the circle, i.e. in a circle of 10:
. . . . . . . . . .
3 can first be taken
_ . . . . . . . _ _
then another 3
_ . _ _ _ . . . _ _
then 1
_ . _ _ _ . . _ _ _
but now three counters cannot be taken out at once.
In another variation of the game, a number of tokens or coins are placed on a table between the two opponents. To play this game, at each move, the player must divide a pile of tokens into two nonempty piles of different sizes. Thus, 6 tokens may be divided into piles of 5/1, 4/2 but not 3/3. The player who can no longer make a move loses the game.
== See also ==
* [[zero game]]
* [[star (game)]]
* [[fuzzy game]]
* [[solved board games]]
* [[Subtract a square]]
* [[Dr. NIM]]
* [[Nimrod (computing)]]
==References==
* 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.
* C. L. Bouton: Nim, ''a game with a complete mathematical theory'', Annals of Mathematics 3 (1901-02), 35-39.
* 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.
* Donal D. Spencer: ''Game Playing with Computers'', Hayden Book Company, Inc., 1968.
==External links==
* [http://www.games.jaxey.com/45.html Pearls Before Swine Game (NIM) ] at [[Jaxey Games]]
* [http://www.cut-the-knot.org/ctk/May2001.html The hot game of Nim] at [[cut-the-knot]]
* [http://www.worditude.com/nimb/ Nim as a web page (javascript)] Play against your PC
* [http://www.gametheory.net/games/ Play Nim online]
* [http://www.goobix.com/games/nim/ Goobix.com's Online Nim]
* [http://www.transience.com.au/pearl.html Pearls Before Swine]
* [http://acm.uva.es/p/v101/10165.html UVa Problem on Nim]
* [http://www.denkwerkzeuge.ch Nim-Game in Flash]
* [http://ia311518.us.archive.org/3/items/UltimateNimTheUseofNimbersBinaryNumbersandSubpilesintheOptimalStrategyforNim/Ultimate_Nim.pdf Ultimate Nim: The Use of Nimbers, Binary Numbers and Subpiles in the Optimal Strategy for Nim]
[[Category:Mathematical games]]
[[Category:Combinatorial game theory]]
[[Category:Recreational mathematics]]
[[Category:Articles containing proofs]]
[[de:Nim-Spiel]]
[[es:Nim]]
[[fr:Jeux de Nim]]
[[he:נים (משחק)]]
[[hu:Nim]]
[[it:Nim]]
[[ja:ニム]]
[[nl:Nim]]
[[no:Nim]]
[[pl:Nim]]
[[pt:Nim (jogo)]]
[[ru:Ним (игра)]]
[[simple:Nim]]
[[sv:Nim]]
[[fi:Nim]]
[[th:นิม]]