Nim
|
|
- This article is about the game. For other uses: see Nim (disambiguation).
Nim is a two-player game of strategy in which players take turns removing objects from heaps, one or more objects at a time but only from a single heap. The players are forced to take at least one object, and are allowed to take the whole heap.
The name was invented by C. L. Bouton of Harvard University, who also developed the complete theory of the game about 100 years ago, but the origins of the name were never explained. The name is probably derived from German nimm! meaning "take!". Some people have noted that turning the word NIM results in WIN, but this is probably just a coincidence.
In the normal version, the player to take the last object wins; in the misère version of the game (sometimes known as Pearls Before Swine), the player to take the last object loses. It is this version that is most commonly played in practice.
In some regions, the misère version of the game is also known as last stone game. In the misère version or last stone game, the loser is forced to remove the last stone as that is the last stone left at his turn; whereas in the normal version, the winner will remove all stones in the last remaining group to win the game. Thus the normal version can be called last move game.
Nim is now used as a simple illustration of the Sprague-Grundy theorem.
A version of this game is played in Alain Resnais' movie L'année dernière à Marienbad.
| Contents |
Illustration
A typical normal game starts with heaps of 3, 4 and 5 objects:
A B C (Heaps A, B, and 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 *
0 1 1 You take 1 from B
0 0 1 I take entire C heap and win.
(* In the misère game I would take 2 from C leaving (0, 1, 0).)
Summary of theory
Nim has been mathematically solved for any number of initial heaps and objects; that is, there is a defined and guaranteed way to win for one of the players, be it the normal or misère game. In a typical misère game that starts with heaps of 3, 4, and 5, player 1 will win with optimal play.
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 carry overs.
011 Heap A in binary 100 Heap B in binary 101 Heap C in binary --- 010 The digital sum of heaps A, B, and C
Binary digital sum shall be more formally represented by a series of exclusive-or operations. This latter term will be used in the subsequent sections in describing the theory.
An equivalent procedure, which can be performed mentally, is to express the heap sizes as a sum of powers of 2, cancel pairs of equal powers, and then add what's left:
3 = 2 +1Heap A 4 =4Heap B 5 =4+1Heap C --- 2 = 2 What's left after cancelling
In the normal game, the strategy is finishing every move with a digital sum of 0, which is always possible if it is different from 0 (in the example above, it suffices taking 2 objects from heap A). If the digital sum is 0 and you must make a move, there is no way you can win the game (assuming the other player is a perfect player), you can only make random moves hoping to confuse your opponent.
For a misère game, the strategy has to be slightly altered. To win, play the game like normal until all but one of the non-empty heaps contain a single object. Then take from the heap with multiple objects to leave an odd number of single object heaps.
In a typical game (with 3 heaps of 3, 4 and 5), the strategy would be applied like this:
A B C Sum (Heaps A, B, and C)
3 4 5 010 I take 2 from A, leaving a sum of 000, so I will win.
1 4 5 000 You take 2 from C
1 4 3 110 I take 2 from B
1 2 3 000 You take 1 from C
1 2 2 001 I take 1 from A
0 2 2 000 You take 1 from C
This is where the alternate strategy kicks in.
0 2 1 010 I take the entire B heap, to leave an odd number (1) of
single object heaps.
0 0 1 000 You take 1 from C, and lose.
Trick for a set of two numbers
If Player A reduces the number set to (2, 2), there are two choices:
- Player B can make it (1, 2) and Player A will make it (1, 1).
- Player B can make it (2) and Player A will make it (0).
That is to say for either choice Player B loses the game.
Now the winning strategy is for Player A to find, (x, y), such that:
- Condition 1.1: The number set is larger than (2, 2).
- Condition 1.2: Player B cannot reduce the number set (x, y) to a winning move such as (2, 2), (1), i.e. (x, y) shall not have either number to be 1 or 2.
- Condition 1.3: It is the smallest number set satisfying the above two conditions. If it is not the smallest number set then Player B will have a chance of making a move such that the resulting number set still satisfies the above two conditions.
Then naturally after Player B’s move with (x, y), Player A has the chance to reduce the number to winning moves such as (1, 1) or (2, 2).
For example if (x, y) is (4, 2) then Player B can reduce to (2, 2) and Player A loses the game.
It is deduced that (x, y) shall be (3, 3), which satisfies all above conditions. If Player A makes the number set to be (3, 3), the following explores all possible moves of Player B:
Moves of Player B Moves of Player A Who Win (2, 3) (2, 2) Player A (2, 1) (1, 1) Player A (2) (0) Player A
It has therefore been demonstrated that (3, 3) is a winning move for Player A if he can achieve this number set.
By the same deduction method, similar conditions can be set to deduce a winning number set larger than (3, 3). It can be therefore induced that the following are winning moves in addition to (2, 2) and (3, 3):
- (4, 4)
- (5, 5)
Trick for a set of three numbers
If Player A reduces the number set to (1, 1), Player B loses the game. If Player A reduces the number set to (2, 2), Player B also loses the game as demonstrated earlier.
Now the winning strategy is for Player A to find (x, y, z), such that:
- Condition 2.1: The number set is larger than either (1, 1) or (2, 2).
- Condition 2.2: Player B does not have a chance of reducing the number set to a winning number such as (1, 1) or (2, 2), i.e. (x, y, z) shall not have two numbers identical with either sets of (1, 1) or (2, 2). For example if (x, y, z) is (1, 2, 2) then Player B can reduce to (2, 2) and Player A loses the game.
- Condition 2.3: It is the smallest number set satisfying the above two conditions.
Then naturally after Player B’s move on (x, y, z), Player A has the chance to reduce the number to winning moves such as (1, 1) or (2, 2).
It is deduced that (x, y, z) shall be (1, 2, 3), which satisfies the above three (3) conditions. If Player A’s move is (1, 2, 3), the following explores all possible moves of Player B:
Moves of Player B Moves of Player A Who Win (1, 2, 2) (2, 2) Player A (1, 2, 1) (1, 1) Player A (1, 2) (1, 1) Player A (1, 1, 3) (1, 1) Player A (1, 3) (1, 1) Player A (2, 3) (2, 2) Player A
It has therefore been demonstrated that (1, 2, 3) is a winning move for Player A.
By the same deduction method, similar conditions can be set to deduce a winning number set larger than (1, 2, 3). It can be therefore induced that the following are also winning moves:
- (1, 4, 5)
- (1, 6, 7)
- (1, 8, 9)
Summary of winning move patterns
Fairly speaking, the game shall be classified as an unfair game or a trick. A player who knows the game can set up the trick such that his opponent has lost from the start.
The trick is to remember the winning moves (number sets) below. To win the game, a player shall make the number set confirming to them. Restricted by reducing only one number at a time, his opponent will not have chance to bring the number set confirming to a smaller winning moves.
- (2, 2)
- (3, 3)
- (4, 4)
- (5, 5)
- ...
- (n, n); where n is greater than 2
Or
- (1, 0, 1)
Or
- (1, 2, 3)
- (1, 4, 5)
- (1, 6, 7)
- (1, 8, 9)
- ...
- (1, 2n, 2n + 1); where n is any whole number not smaller than 1
It is also here quoted without proof that the following number sets are also winning moves:
- (2, 0, 2)
- (2, 1, 3)
- (2, 4, 6)
- (2, 5, 7)
- (2, 8, 10)
- (2, 9, 11)
- ...
- (2, 4n, 4n+2)
- (2, 4n+1, 4n+3)
Where n is any whole number not smaller than 0. Please note that the first two rows are repeated from smaller number sets above to show the pattern. The pattern can be derived simply from such arrangement.
The list can go on.
Winning strategy for misère version
Surprisingly, changing the rule for winning as in the misère version does not make a significant change in the winning moves.
Now with the new rule, if Player A reduces the number set to (1, 1, 1) or (2, 2), Player B loses the game. Given the number set (2, 2), there are two choices for B:
- Player B can make it (1, 2) and Player A will make it (1).
- Player B can make it (2) and Player A will make it (1).
For both choices, Player A wins the game. These number sets (1, 1, 1) or (2, 2) are thus the basic winning number sets not dissimilar to (1, 1) and (2, 2) for the normal version of the game.
It can be deduced that the next winning number set is also (1, 2, 3).
In general, all winning moves for last stone game are the winning moves for last move game except that (1, 1, 1) replaces (1, 1).
Theory of winning formula
Having illustrated some of the winning tricks, the following quotes a theory by Ling Kah Jai on the winning formula for normal version or last move game played with a set of three (3) numbers (x, y, z). The theory also applies to a set of more numbers.
- Theory: If x xor y xor z = 0, then (x, y, z) is a winning move. If a number set is not a winning move then it is a losing move, i.e. the opponent has a chance to reduce it to a winning move.
xor means bitwise eXclusive OR operator (exclusive disjunction) which is explained in its own Wiki page. To carry out the mathematical evaluation, it will be easier to convert all numbers to binary numbers for performing bitwise operation.
- x xor y xor z = 0 ⇔ z = x xor y
- x xor y xor z is also represented as xor(x, y, z) here.
For example, (4, 11, 15) is (100, 1011, 1111)2
- 100 xor 1011 = 1111; therefore (4, 11, 15) is one of the winning move.
- (3, 5, 7) is (11, 101, 111)2
- 11 xor 101 = 110 <> 111; therefore (3, 5, 7) is not a winning but losing move.
It shall be noted that the quoted patterns of winning numbers in the previous section satisfy the theory.
The theory can be extended to a set of four or more numbers:
- If xor(a, b, c, d) = 0 then (a, b, c, d) is a winning move.
- If xor(a, b, c, d, e) = 0 then (a, b, c, d, e) is a winning move.
Thus the trick of winning the game is to reduce a number in the set such that the new number set conforms to the winning move.
Proof of the theory of winning formula
A set of two numbers such that x xor y = 0, i.e. x = y has been proven to be winning moves in one of the section above.
To prove the theory of winning formula, it is necessary to prove the following theories:
- Theory 1: If xor(A, B, C) = 0 and one and only one of its numbers is reduced and the number set becomes (A', B', C'), then xor(A', B', C') > 0;
- Theory 2: If xor(A', B', C') > 0, then it is possible to reduce one of its numbers such that the number set becomes (A", B", C") and xor(A", B", C") = 0.
Proof of Theory 1
- xor(A, B, C) = 0 ... (Condition 1)
- i.e. A = B xor C ... (Eqn 2)
- and B = A xor C ... (Eqn 3)
- and C = A xor B ... (Eqn 4)
The LHS of (Eqn 2) i.e. B xor C results in a unique solution A. If A is reduced, (Eqn 2) is no more true and thus Condition 1 will no more be true. By similar reasoning, if B or C is disturbed at a time, Condition 1 will also be upset and the proof is complete.
Proof of Theory 2
To prove Theory 2, it is necessary to prove in two parts:
- Theory 2a: If the numbers in the set (A', B', C') are identical, i.e. A' = B' = C' , Theory 2 holds.
- Theory 2b: If the numbers in the set (A', B', C') are not identical, Theory 2 also holds.
Proof of Theory 2a
xor(A', A', A') = (A' xor A') xor A' = A' , satisfy the condition of greater than zero.
The number set (A', A', A') can be reduced in one move to (A', A' ) whereby xor(A', A') = 0 thus completing the proof. (A', A' ) is indeed a winning move.
Proof of Theory 2b
To prove Theory 2b, it is necessary to prove the following:
- Theory 2c: If xor(A', B', C') > 0 and A', B' and C' are not all identical, then there exists one and only one a' such that: a' > b' xor c' ; where a' can be either A' , B' or C' ; and b' and c' are the remaining two numbers.
It is assumed that:
- xor(A', B', C') = D'
Operation (… and D') is called a masking function which is often used in computer programming, thus if D' = 11002, (A' and 1100) means the 3rd and 4th bits (counting from the right) of A' shall remains whereas all other (insignificant) bits shall be replaced by zeros.
- xor(A', B', C') = D'
- ⇒ xor(A' and D', B' and D', C' and D') = (D' and D') = D'
- ⇒ xor(Ar', Br', Cr') = D' ; where "Ar' = (A' and D')etc.
Expressed in another manner:
- Ar' xor Br' xor Cr' = D' > 0
If ar' is the largest number among (Ar', Br', Cr') then
- ar' > br' xor cr';
ar' can thus be reduced to ar" such that:
- ar" = br' xor cr'
Thus
- (A' and D') > (B' and D') xor (C' and D') and A' can be reduced to A" such that:
- (A" and D') = (B' and D') xor (C' and D'); and
- A" = B' xor C'
This completes the proof for Theories 2c and 2b and thus Theory 2.
Proof of the winning theory
Given that Player 2 starts with the number set (A, B, C) such that xor(A, B, C) = 0, Player 2 cannot make a move such that the resultant number set is (A', B', C') and xor(A', B', C') = 0 according to Theory 1.
However, after his move, Player 1 can revert the situation and can always make a move to (A", B", C") such that xor(A", B", C") = 0 according to Theory 2.
Thus by mathematical induction, if winning moves of (A, B, C) with small numbers satisfy xor(A, B, C) = 0, then all such possible (A, B, C) satisfying xor(A, B, C) = 0 are winning moves. The number sets (0, 1, 1), (0, 2, 2) and (0, n, n) etc are indeed winning moves. This completes the proof.
Other variation of the game
Another variation to Nim is restricting the maximum number of stones to be removed at each turn. This variation however simplifies the game to a very simple arithmetic and will not be illustrated here.
External links and references
- The hot game of Nim (http://www.cut-the-knot.org/ctk/May2001.html)
- Play Nim online (http://www.gametheory.net/html/games.html)
- Nim programs and websites (http://sjhs.freeshell.org/nim/)de:Nim-Spiel