A Game You Never Lose

Nim Game! What is Nim?

Nim is a very simple game, played between two players. There are no special pieces of equipment needed to play this game. You only need some coins, stones, sticks or marbles, etc. to arrange few heaps.

Heaps of coins

Before we talk about the game rules here are some facts about the history of the game.

• The name Nim was given by mathematics professor Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901.
• The origin of the game is uncertain and the earliest European references to Nim are from the beginning of the 16th century.
• This game is very similar to the Chinese game 捡石子 jiǎn-shízi (picking stones) and there is an African variant of the game called tiouk tiouk.

The Nimatron at the New York World’s Fair

Nim was one of the first-ever electronic computerized games.

In 1940 Westinghouse Electric Corporation introduces the machine Nimatron, which played Nim. Only a few people were able to beat the machine in that six-week period and winners were presented with a coin that said Nim Champ.

In 1951 Ferranti International plc built a Nim playing computer.

That’s all I’m going to tell you about the history of the game.

Let’s see how to play Nim

The only rule is “The player must take at least one piece from a selected heap on his or her turn”.  So, you have to select one heap and then need to move out at least one piece from the heap. If you want, you can move out all the pieces in that heap.

Before you play the game you need to know one more thing. There are two types of plays when deciding who is going to win the game.

1. 1. 1. Normal play
      2. Misère play

In the Normal play, the winner is the player making the last move. The loser is the player unable to do a move. But you can play the game in the other way as the player who had to make the last move is the loser. This is called misère play.

Watch below 1 min video of a normal Nim game played between Chanaka and Dishan.

Let’s play the game

Click the button below to play the game and try to figure out some strategies.

Now you know the game better. But what about the strategies? It’s a little clear that if there is a winning strategy then it depends on who is going to start the game first, and also the initial configuration of the heaps.

Let’s discuss the math behind Nim.

You may not believe if I said that this game has been mathematically solved for any initial configuration. The theory of the Nim game was discovered by mathematics professor Charles Bouton. He found a simple method to calculate the winning moves for any number of heaps and objects.

The wonderful fact is that the theory is based on binary numbers. The player always maintains the Nim-sum of heap sizes equals to 0 in his moves is guaranteed to win.

Let’s try to understand Nim-sum

Nim-sum is another name for binary digital sum and is also known as bitwise xor.

The nim-sum of x and y is written as x ⊕ y because it’s not the ordinary sum x + y.

The below table simply explains how this operation works.

As you all know, computers are binary machines, and everything including storing, operating, processing are 0s and 1s. So, the nim sum is not all about winning a game. Actually, it rules the world. Therefore understanding Nim-sum is important.

Below is a simple way to calculate a Nim sum of a set of heaps.

1. Consider 3 heaps with coin count of each heap is 3, 4, and 5.
2. Write object counts as the sum of powers of 2.
   • 3 = 2¹ + 2⁰ =2 + 1
   • 4 = 2² = 4
   • 5 = 2² + 2⁰ = 4 +1
3. Write the binary sum of the object counts using the above results
   • 3 ⊕ 4 ⊕ 5 = (2+1) ⊕ (4) ⊕ (4+1)
4. Cut and remove the equal pairs as much as possible.
   • 3 ⊕ 4 ⊕ 5 = (2+1) ⊕ (4) ⊕ (4+1) = 2
5. So, the Nim sum is 2.

Some examples to understand more…

• 3 ⊕ 7 ⊕ 2 = (2+1) ⊕ (4+2+1) ⊕ (2)    = 6
• 15 ⊕ 15 = (8+4+2+1) ⊕ (8+4+2+1)     = 0
• 25 ⊕ 30 = (16+8+1) ⊕ (16+8+4+2)     = 7

Now you know the Nim sum. 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. So, you need to always maintain the Nim-sum of zero in order to win the game.

See below example steps of a Nim game of 3 heaps A, B, and C.

If the game is Normal play then you can take 1 from B and win the game.

If the game is Misère play then you can take 2 from B and win the game.

In the above example, you make the Nim sum to zero and take the game to a winning position in each step. The strategy to win the game is for a player to force the other player into one of the winning positions. Only the last move changes between misery and normal play.

The below table shows some winning positions for Nim games of 2, 3, and 4 heaps.

Where n and m are any integers greater than zero

If you are interested you can implement a program to play the nim game. Below is the function to calculate the nim-sum written in C language.

// heaps[] is the array that contains heap sizes
// n is the heap count.
// ^ is the Bitwise exclusive OR operator. 

int calculateNimSum(int piles[], int n) {
 int i, nimsum = piles[0];
 for (i=1; i<n; i++)
  nimsum = nimsum ^ piles[i];
 return(nimsum); 
}

Other than the normal play and the misère, there are a lot of variations of Nim like,

• Graph Nim
• Candy Nim
• Building Nim
• Greedy Nim
• Circular Nim
• Fibonacci Nim

There are no major differences in the rules for those variations. From the above variations, Fibonacci Nim is played based on the Fibonacci numbers. If you are interested in Fibonacci, please refer to my previous article in the link below.

The Mysterious Number of Beauty

References

https://en.wikipedia.org/wiki/Nim

https://plus.maths.org/content/play-win-nim

https://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/

https://en.wikipedia.org/wiki/Fibonacci_nim

https://www.transum.org/Software/Nim/