Games - Nim

	Games - Nim

Nim is a two-player 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 Tsyanshidzi, 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 nimm! meaning "take!", or the obsolete English verb nim of the same meaning. Some people have noted that turning the word NIM upside-down and backwards results in WIN, but this is probably just a coincidence.

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 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.

A version of Nim is played in Alain Resnais's movie L'année dernière à Marienbad.

Illustration

A normal play game may start with heaps of 3, 4 and 5 objects: 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 0 2 2 You take 1 from B 0 1 2 I take 1 from C (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 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 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 Decimal 011₂ 3₁₀ Heap A 100₂ 4₁₀ Heap B 101₂ 5₁₀ Heap C --- 010₂ 2₁₀ 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 = 2 + 1 = 2 + 1 Heap A 4 = 4 = 4 Heap B 5 = 4 + 1 = 4 + 1 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, if X is the Nim-sum of all the heap sizes, take the Nim-sum of each of the heap sizes with X. 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.

[ Visit the complete Wikipedia entry for Nim ]

Games - Nim

Illustration

Mathematical theory

Searches on eBay

Related searches on eBay