Nim

For other uses, see Nim (disambiguation).
A rack used to play nim with heaps of size three, five, and seven.

Nim is a mathematical game of strategy in which two 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. The goal of the game is to be the player to remove the last object.

Variants of Nim have been played since ancient times.[1] The game is said to have originated in China—it closely resembles the Chinese game of "Tsyan-shizi", or "picking stones"[2]—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,[3] but the origins of the name were never fully explained. The name is probably derived from German nimm meaning "take [imperative]", or the obsolete English verb nim of the same meaning.[4]

Nim can be 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, 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 nimbers) 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 tame games can be played using the same strategy as misère nim.

A version of Nim is played—and has symbolic importance—in the French New Wave film Last Year at Marienbad (1961).[5]

At the 1940 New York World's Fair Westinghouse displayed a machine, the Nimatron, that played Nim.[6] It was also one of the first ever electronic computerized games. Ferranti built a Nim playing computer which was displayed at the Festival of Britain in 1951. In 1952 Herbert Koppel, Eugene Grant and Howard Bailer, engineers from the W. L. Maxon Corporation, developed a machine weighing 50 pounds which played Nim against a human opponent and regularly won.[7] A Nim Playing Machine has been described made from TinkerToy.[8]

Nim is a special case of a poset game where the poset consists of disjoint chains (the heaps).

Game play and illustration

The normal game is between two players and played with three heaps of any number of objects. The two players alternate taking any number of objects from any single 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 game is played between fictional players Bob and Alice who start with heaps of three, four and five objects.

Sizes of heaps  Moves
A B C
 
3 4 5           Bob   takes 2 from A
1 4 5           Alice takes 3 from C
1 4 2           Bob   takes 1 from B
1 3 2           Alice takes 1 from B
1 2 2           Bob   takes entire A heap, leaving two 2s.
0 2 2           Alice takes 1 from B
0 1 2           Bob   takes 1 from C leaving two 1s. (In misère play he would take 2 from C leaving (0, 1, 0).)
0 1 1           Alice takes 1 from B
0 0 1           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 lower positions. Only the last move changes between misere and normal play.

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

* Only valid for normal play, ** Only valid for misere. For the generalisations, n and m can be any value > 0, and they may be the same.

Mathematical theory

Nim has been mathematically solved for any number of initial heaps and objects, and 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 three, four, and five, 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 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 GF(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 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  Decimal
 
  0112    310    Heap A
  1002    410    Heap B
  1012    510    Heap C
  ---
  0102    210    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 powers of 2, cancel pairs of equal powers, and then add what's 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's 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 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 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 two or larger. 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).

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

A B C nim-sum 
 
3 4 5 0102=210   I take 2 from A, leaving a sum of 000, so I will win.
1 4 5 0002=010   You take 2 from C
1 4 3 1102=610   I take 2 from B
1 2 3 0002=010   You take 1 from C
1 2 2 0012=110   I take 1 from A
0 2 2 0002=010   You take 1 from C
0 2 1 0112=310   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 0012=110   You take 1 from C, and lose.

The previous strategy for a misère game can be easily implemented (for example in Python, below).

def nim(heaps, misere=True):
	"""Computes next move for Nim in a normal or misère (default) game, returns tuple (chosen_heap, nb_remove)"""
	X = reduce(lambda x,y: x^y, heaps)
	if X == 0: # Will lose unless all non-empty heaps have size one
		if max(heaps) > 1:
			print "You will lose :("
		for i, heap in enumerate(heaps):
			if heap > 0: # Empty any (non-empty) heap
				chosen_heap, nb_remove = i, heap
				break
	else:
		sums = [t^X < t for t in heaps]
		chosen_heap = sums.index(True)
		nb_remove = heaps[chosen_heap] - (heaps[chosen_heap]^X)
		heaps_twomore = 0
		for i, heap in enumerate(heaps):
			n = heap-nb_remove if chosen_heap == i else heap
			if n>1: heaps_twomore += 1
		# If move leaves no heap of size 2 or larger, leave an odd (misère) or even (normal) number of heaps of size 1
		if heaps_twomore == 0:
			chosen_heap = heaps.index(max(heaps))
			heaps_one = sum(t==1 for t in heaps)
			# misère (resp. normal) strategy: if it is even (resp. odd) make it odd (resp. even), else do not change
			nb_remove = heaps[chosen_heap]-1 if heaps_one%2!=misere else heaps[chosen_heap]
	return chosen_heap, nb_remove

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 nonzero. Otherwise, the second player has a winning strategy.

Proof: Notice that the nim-sum (⊕) obeys the usual associative and commutative laws of addition (+) and also satisfies an additional property, x ⊕ x = 0 (technically speaking, that the nonnegative integers under ⊕ form an Abelian group of exponent 2).

Let x1, ..., xn be the sizes of the heaps before a move, and y1, ..., yn the corresponding sizes after a move. Let s = x1 ⊕ ... ⊕ xn and t = y1 ⊕ ... ⊕ yn. If the move was in heap k, we have xi = yi for all i ≠ k, and xk > yk. By the properties of ⊕ mentioned above, we have

    t = 0 ⊕ t
      = s ⊕ s ⊕ t
      = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
      = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
      = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
      = s ⊕ xk ⊕ yk
 
(*) t = s ⊕ xk ⊕ yk.

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 vacuously true (and the first player loses the normal play game by definition). Otherwise, any move in heap k will produce t = xk ⊕ yk from (*). This number is nonzero, since xk ≠ yk.

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 dth bit of xk is also nonzero. (Such a k must exist, since otherwise the dth bit of s would be 0.) Then letting yk = s ⊕ xk, we claim that yk < xk: all bits to the left of d are the same in xk and yk, bit d decreases from 1 to 0 (decreasing the value by 2d), and any change in the remaining bits will amount to at most 2d−1. The first player can thus make a move by taking xk − yk objects from heap k, then

t = s ⊕ xk ⊕ yk           (by (*))
  = s ⊕ xk ⊕ (s ⊕ xk)
  = 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, 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

Dividing natural number

Give any natural number n, the two people can divide n by a prime power ( A000961) which is a factor of n (except 1), the person who gets 1 wins (or loses).

If n=2^{a_1}3^{a_2}5^{a_3}7^{a_4} \cdots p_k^{a_k}, where p_k is the k-th prime, then it is a Nim game with k groups of stones, and the r-th groups has a_r stones.

If the divisor changes to "a power of squarefree numbers" ( A072774) except 1, it is Wythoff's game.

The divisor can also change to "a divisor of m" for fixed m, where m is a divisor of n. (m should be divisible by all of the prime factors of n and should be less than n)

Of course, you can choose a set of allowed divisors. For example, {2, 3, 4, 12, 15, 20, 24, 25, 30, 32, 36}.

The subtraction game S(1, 2, . . ., k)

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.

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 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 (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 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 ideal play from a single heap of n objects, the second player can win if and only if

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),

0.123\ldots k0123\ldots k0123\dots = \dot0.123\ldots\dot{k}, \,

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

The 21 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 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 where the first player opens with "1", they start with a losing move.

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

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

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 alternatively 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 reached 89, the opponent has lost (he can only tell 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', where 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 where the players are restricted to choosing stones from only the largest pile.[9] It is a finite impartial game. Greedy Nim Misère has the same rules as Greedy Nim, but here the last player able to make a move loses

Let the largest number of stones in a pile be m, the second largest number of stones in a pile be n. Let pm be the number of piles having m stones, pn be the number of piles having n stones. Then there is a theorem that game positions with pm even are P positions. [10] This theorem can be shown by considering the positions where pm is odd. If pm is larger than 1, all stones may be removed from this pile to reduce pm by 1 and the new pm will be even. If pm = 1 (i.e. the largest heap is unique), there are two cases:

Thus there exists a move to a state where pm is even. Conversely, if pm is even, if any move is possible (pm ≠ 0) then it must take the game to a state where pm is odd. The final position of the game is even (pm = 0). Hence each position of the game with pm even must be a P position.

Index-k Nim

A generalization of multi-heap Nim was called "Nim{}_k" or "index-k Nim by E. H. Moore,[11] 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 + 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 + 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 where the two players first construct the game of Nim. Given n stones and s empty piles, the players alternate turns placing exactly one stone into a pile of their choice.[12] 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).

See also

References

  1. ↑ Jorgensen, Anker Helms (2009), "Context and driving forces in the development of the early computer game Nimbi", IEEE Annals of the History of Computing 31 (3): 44–53, doi:10.1109/MAHC.2009.41, MR 2767447, The two-person mathematical game Nim, which many believe originated in China, is probably one of the oldest games in the world.
  2. ↑ Yaglom, I. M. (2001), "Two games with matchsticks", in Tabachnikov, Serge, Kvant Selecta: Combinatorics, I, Volume 1, Mathematical world 17, American Mathematical Society, pp. 1–8, ISBN 9780821821718.
  3. ↑ Bouton, C. L. (1901–1902), "Nim, a game with a complete mathematical theory", Annals of Mathematics 3 (14): 35–39, doi:10.2307/1967631..
  4. ↑ Morrissette (1968) attributes this theory to Bushaw, D. W. (October 1966), "On the name and history of nim", Washington Mathematics 11: 52–55.
  5. ↑ Morrissette, Bruce (1968), "Games and game structures in Robbe-Grillet", Yale French Studies 41: 159–167, doi:10.2307/2929672. Morrissette writes that Alain Robbe-Grillet, one of the screenwriters for the film, "thought he had invented" the game.
  6. ↑ Flesch, Rudolf (1951). The Art of Clear Thinking. New York: Harper and Brothers Publishers. p. 3.
  7. ↑ Grant, Eugene F.; Lardner, Rex (August 2, 1952). "The Talk of the Town – It". The New Yorker.
  8. ↑ Cohen, Harvey A. "How to Construct NIM Playing Machine" (PDF).
  9. ↑ --- (2001). Winning Ways for your Mathematical Plays. 4 vols. (2nd ed.). A K Peters Ltd.; vol. 1. ISBN 1-56881-130-6.; vol. 2. ISBN 1-56881-142-X.; vol. 3. ISBN 1-56881-143-8.; vol. 4. ISBN 1-56881-144-6..
  10. ↑ M H Albert, R. J. Nowakowski (2004). "Nim Restrictions" (PDF). Integers: Electronic Journal of Combinatorial Number Theory 4.G01 (2004): G01: 2.
  11. ↑ Moore, E. H. A Generalization of the Game Called Nim. Annals of Mathematics 11 (3), 1910, pp. 93–94
  12. ↑ Larsson, Urban; Heubach, Silvia; Dufour, Matthieu; Duchêne, Eric. "Building Nim". arXiv.org.

Additional reading

External links

Wikimedia Commons has media related to Nim.
This article is issued from Wikipedia - version of the Friday, April 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.