Combinatorial Game Theory | Game of Nim

The Game of Nim is basically an algorithmic problem with the following rules:

Given a number of pile containing coins or stones. There are two players playing the game, and in each move, a player removes any number of coins from any particular pile. The player, who cannot make a move loses the game, or in other words, the player who takes the last stone wins.

The turns of both the players keeps on alternating after each valid move.

Still confused about the problem statement..!?

Let us understand it by taking a simple example:

Example 1:
Initially we have 3 piles with following number of coins in each pile, and two players A & B,
3 4 5
We assume that first move is made by A
- A takes 2 from 1st pile
1 4 5
- B takes 3 from 3rd pile
1 4 2
- A takes 1 from 2nd pile
1 3 2
- B takes 1 from 2nd pile
1 2 2
- A takes 1 from 1st pile
0 2 2
- B takes 1 from 2nd pile
0 1 2
- A takes 1 from 3rd pile
0 1 1
- B takes 1 from 2nd pile
0 0 1
- A takes 1 from 3rd pile
0 0 0
- B cannot make any further move
Hence, A won the match.
Note that A made the first move
Does that mean that A was an expert in the game, or got the benefit of making the first move? Let us take another example, where B makes the first move.

Example 2:
Initially we have 3 piles with following number of coins in each pile, and two players A & B,
3 4 5
We assume that first move is made by B
- B takes 2 from 1st pile
1 4 5
- A takes 3 from 3rd pile
1 4 2
- B takes 1 from 2nd pile
1 3 2
- A takes 1 from 2nd pile
1 2 2
- B takes 1 from 1st pile
0 2 2
- A takes 1 from 2nd pile
0 1 2
- B takes 1 from 3rd pile
0 1 1
- A takes 1 from 2nd pile
0 0 1
- B takes 1 from 3rd pile
0 0 0
- A cannot make any further move
Hence, B won the match.
Note that B made the first move
Does that mean that B was an expert in the game, or got the benefit of making the first move, as similarly A won the match in previous example by making the first move? Let us take another example, where A makes the first move.

Example 3:
Initially we have 3 piles with following number of coins in each pile, and two players A & B,
1 4 5
We assume that first move is made by A
- A takes 3 from 3rd pile
1 4 2
- B takes 1 from 2nd pile
1 3 2
- A takes 1 from 2nd pile
1 2 2
- B takes 1 from 1st pile
0 2 2
- A takes 1 from 2nd pile
0 1 2
- B takes 1 from 3rd pile
0 1 1
- A takes 1 from 2nd pile
0 0 1
- B takes 1 from 3rd pile
0 0 0
- A cannot make any further move
Hence, B won the match.
Note that A made the first move
What's actually happening here? In Example 1, A made the first move, and won the match, in Example 2, B made with first move, and won the match, in Example 3, A made the first move, still lost the match.
In Example 1 & Example 2, the initial configuration of the pile were same, so the player who was moving first was winning. In Example 3, the initial configuration was different from Example 1 & 2.

From all these examples, we can conclude the following points on which the winner of a particular game depends:

1. The player who makes the first move.
2. The initial configuration of the match.

In fact, we can determine the winner of a Nim Game by analyzing the above two points, even without making any move.

Nim Sum: The cumulative XOR value of the number of coins/stones in each pile at any point of the game is called Nim-Sum at that point. “If both A and B play optimally (i.e. – they don’t make any mistakes), then the player starting first is guaranteed to win if the Nim-Sum at the beginning of the game is non-zero. Otherwise, if the Nim-Sum evaluates to zero, then player A will lose definitely.” 

For the proof of the above theorem, Have a look at this – https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula

Let us re-analyze the Example 1, 2 & 3 with the help of Nim Sum.

Example 1:
Initially we have 3 piles with following number of coins in each pile, and two players A & B,
3 4 5
We assume that first move is made by A

Nim Sum (Cumulative XOR): 3 XOR 4 XOR 5 = 3^4^5 = 2.
Hence, Nim Sum is non-zero, and the player making the first move won the match, i.e., A in this example.

Example 2:
Initially we have 3 piles with following number of coins in each pile, and two players A & B,
3 4 5
We assume that first move is made by B

Nim Sum (Cumulative XOR): 3 XOR 4 XOR 5 = 3^4^5 = 2.
Hence, Nim Sum is non-zero, and the player making the first move won the match, i.e., B in this example.

Example 3:
Initially we have 3 piles with following number of coins in each pile, and two players A & B,
1 4 5
We assume that first move is made by A

Nim Sum (Cumulative XOR): 3 XOR 4 XOR 5 = 3^4^5 = 0.
Hence, Nim Sum is zero, and the player making the first move will lose the match in all conditions, i.e., A lost the match, and B won the match.

Read Next: Wilson’s Theorem | Mathematics