Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 15 minutes | Coding time: 6 minutes
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 who removes the last object.
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, where the player taking the last object wins. This is called normal play because the last move is a winning move in most games; Nim is usually played so that the last move loses.
Sample Gameplay
Consider two players, Alice and Bob playing the game of Nim:
Two players: Alice and Bob
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.
0 0 0 Game ends. Bob wins
Algorithm
The Game of Nim has been mathematically solved for any number of piles and heaps.
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).
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. In Python, XOR is denoted by ^ operator.
Truth table of the XOR or Nim-sum operation:
Output is 1 if there are odd number of ones in the input
0 if there are even number of ones in the input
Consider it for 2 inputs:
Input_1 Input_2 Output
0 0 0
0 1 1
1 0 1
1 1 0
Binary Decimal
011 3 Heap A
100 4 Heap B
101 5 Heap C
010 2 nim-sum of the above heaps (3^4^5)
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.
A Sample gameplay for better understanding of the situation :
A B C nim-sum
3 4 5 010=2 I take 2 from A, leaving a sum of 000, so I will win.
1 4 5 000=0 You take 2 from C
1 4 3 110=6 I take 2 from B
1 2 3 000=0 You take 1 from C
1 2 2 001=1 I take 1 from A
0 2 2 000=0 You take 1 from C
0 2 1 011=3 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=1 You take 1 from C, and lose.
Complexity
- For Next Optimal Move: O(N)
- For Winner Prediction: O( Nmoves_left)
Implementations
- Python: Next Move
- Python: Win or Lose
Python: Next Move
def nim_sum(objectList, heaps):
nim = 0
# Calculate nim sum for all elements in the objectList
for i in objectList:
nim = nim ^ i
print("The nim sum is {}.".format(nim))
# Determine how many objects to remove from which heap
objects_to_remove = max(objectList) - nim
objects_to_remove = abs(objects_to_remove)
# Logic for certain configurations on determining how many objects to remove from which heap
# "objectList.index(max(objectList))+ 1 )" determines the index in objectList at which the biggest
# heap of objects exists.
if (nim > 0) and (len(objectList) > 2) and (nim != max(objectList)) and (nim != 1):
print("Pick {} objects from heap {}".format(objects_to_remove, objectList.index(max(objectList)) + 1))
break
if (nim > 0) and (len(objectList) > 2) and (nim == max(objectList)) and (nim != 1):
print("Pick {} objects from heap {}.".format(nim, objectList.index(max(objectList)) + 1))
break
if nim > 0 and len(objectList) <= 2 and (objects_to_remove != 0):
print("Pick {} objects from heap {}".format(objects_to_remove, objectList.index(max(objectList)) + 1))
break
if nim > 0 and len(objectList) <= 2 and (objects_to_remove == 0):
print("Pick {} objects from heap {}".format(nim, objectList.index(max(objectList)) + 1))
break
elif (nim == 1) and (len(objectList) <= 2):
print("Pick {} objects from heap {}".format(nim, objectList.index(max(objectList)) + 1))
break
if (nim == 1) and (nim == max(objectList)) and (nim != 0) and (len(objectList) > 2):
print("Pick {} objects from heap {}".format(nim, objectList.index(max(objectList)) + 1))
break
if nim == 0:
print("Pick all objects from heap {}.".format(objectList.index(max(objectList)) + 1))
break
def get_next_optimum(heaps):
'''
Heaps should be in dictionary format where
key : heap number, value : number of objects
Example:
{
1:3,
2:4,
3:5
}
Maximum 5 heaps allowed with maximum 8 objects each
'''
objects = list(heaps.values())
heapKeys = list(heaps.keys())
print (" Your game board looks like this ")
print ("-"*30)
for i in range(len(heapKeys)):
print("Heap {} : {}".format(i + 1, "|" * objects[i]))
print ("-"*30)
nim_sum(objects, heapKeys)
Python: Winner Prediction
import functools
MISERE = 'misere'
NORMAL = 'normal'
def nim(heaps, game_type):
"""
Computes next move for Nim, for both game types normal and misere.
Assumption : Both players involved would play without making mistakes.
if there is a winning move:
return tuple(heap_index, amount_to_remove)
else:
return "You will lose :("
"""
print(game_type, heaps, end=' ')
is_misere = game_type == MISERE
endgame_reached = False
count_non_0_1 = sum(1 for x in heaps if x > 1)
endgame_reached = (count_non_0_1 <= 1)
# nim sum will give the correct end-game move for normal play but
# misere requires the last move be forced onto the opponent
if is_misere and endgame_reached:
moves_left = sum(1 for x in heaps if x > 0)
is_odd = (moves_left % 2 == 1)
sizeof_max = max(heaps)
index_of_max = heaps.index(sizeof_max)
if sizeof_max == 1 and is_odd:
return "You will lose :("
# reduce the game to an odd number of 1's
return index_of_max, sizeof_max - int(is_odd)
nim_sum = functools.reduce(lambda x, y: x ^ y, heaps)
if nim_sum == 0:
return "You will lose :("
# Calc which move to make
for index, heap in enumerate(heaps):
target_size = heap ^ nim_sum
if target_size < heap:
amount_to_remove = heap - target_size
return index, amount_to_remove
if __name__ == "__main__":
import doctest
doctest.testmod()
Applications and Variations
The Implementations mentioned above are more or loss limited to the classical game of Nim with decent amount of heaps but, like every game, Variations exist for it and a few of them are as mentioned :
- 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.
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 Subtraction 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 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),
from which the strategy above follows by the Sprague–Grundy theorem.
An interesting game for you to try and test this variation!
- Greedy Nim
Greedy Nim is a variation where the players are restricted to choosing stones from only the largest pile. 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. - Fibonacci Nim
Fibonacci nim is a mathematical game, a variant of the game of nim. The game was first described by Michael J. Whinihan in 1963, who credits its invention to Robert E. Gaskell. It is called Fibonacci nim because the Fibonacci numbers feature heavily in its analysis.
This game is played by two players, who alternate removing coins or other counters from a pile of coins. On the first move, a player is not allowed to take all of the coins, and on each subsequent move, the number of coins removed can be any number that is at most twice the previous move. According to the normal play convention, the player who takes the last coin wins.
Question
Game of Nim is solved by which theory?
Are the middle game semantics for misère and normal gameplay different for nim?
Further Reading
- For reading more detailed reading on Nim Game and related Theory:Reaserch Paper by MIT
