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:

- The player who makes the first move.
- 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