In the world of mathematical games, Nim’s game stands out as a fascinating and challenging two-player game. Despite its simple rules, Nim’s game requires strategic thinking and logical reasoning to win the game.

###### What is Nim’s Game?

Nim’s game is played with a set of heaps, each containing a certain number of objects or stones. Two players take turns removing objects from the heaps according to the following rules:

- On each turn, a player must choose one heap.
- The player can remove any number of objects from the chosen heap, but they must remove at least one object.
- The players alternate turns until no objects are left.

The player who cannot make a move (i.e., when all heaps are empty) loses the game.

###### Nim’s variation – Misère game

Nim is also played as a *misère game*, in which the player to take the last object loses instead of winning.

###### Winning Strategy for Nim’s Game (Normal version)

To increase your chances of winning Nim’s game, you need to employ a winning strategy based on the game’s mathematical properties. Here’s the key idea:

- The game position with all heaps empty is called a “losing position” because the player who faces it will lose the game.
- Any game position that is not a losing position is a “winning position” because the player can make a move to force the opponent into a losing position.

Based on this idea, we can determine the winning or losing nature of a game position using a principle called “XOR-sum.”

###### XOR-Sum (Nim-Sum)

The **XOR (exclusive OR) operation** is a bitwise operation that `returns true`

if and only if the **operands** have **different boolean values**. In Nim’s game, we can apply XOR to the number of objects in each heap and obtain the XOR-sum of all the heaps’ sizes.**If at any time in the game, the XOR-sum of the heaps’ sizes is zero, it means we are in a losing position.** Otherwise, we are in a winning position for a non-zero XOR-sum.

###### Game play

Let Alice and Bob be playing with heaps of three, four and five objects

Heap A | Heap B | Heap C | Move |

3 | 4 | 5 | Game begins |

1 | 4 | 5 | Bob takes 2 from A |

1 | 4 | 2 | Alice takes 3 from C |

1 | 3 | 2 | Bob takes 1 from B |

1 | 2 | 2 | Alice takes 1 from B |

0 | 2 | 2 | Bob takes entire A heap, leaving two 2s |

0 | 1 | 2 | Alice takes 1 from B |

0 | 1 | 1 | Bob takes 1 from C leaving two 1s. |

0 | 0 | 1 | Alice takes 1 from B |

0 | 0 | 0 | Bob takes 1 from C heap and wins |

**Winning position using XOR Sum**

The Nim-sum/XOR-sum (X) of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2

Calculating Nim-sum using Binary representation:

011_{2}3 Heap A

100_{2}4 Heap B

101_{2}5 Heap C

-----

010_{2}2

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.

###### Winning Strategy Moves

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 (X ⊕`

of ** **size[heap])**X** and heap-size is less than the heap-size `(size[heap])`

; **the winning strategy is to always play in such a heap and reduce that heap’s size to the “nim-sum of its size with X”**, ie

A ⊕ X = 3 ⊕ 2 = 1 [(011) ⊕ (010) = 001 ]

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

So, we could see that only the size of Heap A is reduced after calculating the xor-sum of X and size[Heap A]. Hence, the winning move is to reduce the size of Heap A to `(X ⊕ Size[Heap A])`

ie 1. We could do this by removing two objects from Heap A.

###### Optimum Game Play

Heap A | Heap B | Heap C | Move |

3 | 4 | 5 | Game Begins, X = 3 ⊕ 4 ⊕ 5 = 2 |

1 | 4 | 5 | Take 2 from A to make it 1, (X ⊕ A) = 2 ⊕ 3 = 1 |

1 | 4 | 2 | Opponent takes 3 from C, X = 1 ⊕ 4 ⊕ 2 = 7 |

1 | 3 | 2 | Take 1 from B to make it 3, X = 7, (X ⊕ B) = 7 ⊕ 4 = 3 |

1 | 2 | 2 | Opponent takes 1 from B, X = 1 ⊕ 2 ⊕ 2 = 1 |

0 | 2 | 2 | Take 1 from A to make it 0, X = 1, (X ⊕ A) = 1 ⊕ 1 = 0 |

0 | 1 | 2 | Opponent takes 1 from B |

0 | 1 | 1 | Take 1 from C leaving two 1s. |

0 | 0 | 1 | Opponent takes 1 from B |

0 | 0 | 0 | Take 1 from C heap and win |

`XOR-sum`

of all the current heap sizes ie X = current_size[A] ⊕ current_size[B] ⊕ current_size[C]**Note:** If at a time, we’ve multiple Heaps such that `X ⊕ Size[Heap]`

is less than `Size[Heap]`

, it does not matter which heap is selected. As long as the XOR sum of the heap-size and the X (`XOR-sum`

of all the current heap sizes) is less than the actual heap-size, we could select any Heap and make a move (remove objects) that reduces the selected heap’s size to the XOR sum of its current size with X. This strategy guarantees a winning position for the player.

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.

**Code Implementation**

```
//
// main.cpp
// Nim's Game
//
// Created by Himanshu on 24/05/23.
//
#include <iostream>
#include <cstdlib>
#include <numeric>
using namespace std;
int calculateXORSum (int heaps[], int n) {
int xorSum = 0;
for (int i = 0; i < n; i++) {
xorSum ^= heaps[i];
}
return xorSum;
}
void printGameState (int heaps[], int n) {
for (int i = 0; i < n; i++) {
cout << heaps[i] << " ";
}
cout << "\n";
}
void makeMove (int heaps[], int heapIndex, int move) {
heaps[heapIndex] -= move;
}
int getRandomMove (int heapSize) {
return rand() % heapSize + 1;
}
void printWinner (int currentPlayer) {
if (currentPlayer == 1) {
cout << "Player A wins\n";
} else {
cout << "Player B wins\n";
}
}
void playNimGame (int heaps[], int n) {
int xorSum = calculateXORSum(heaps, n);
int currentPlayer = 1; // 1 for Player A, 2 for Player B
cout << "Game begins\n";
printGameState(heaps, n);
while (true) {
int heapIndex = -1;
int move = -1;
// Find a heap where the XOR sum of heap size and xorSum is less than the heap size
for (int i = 0; i < n; i++) {
if ((heaps[i] ^ xorSum) < heaps[i]) {
heapIndex = i;
move = heaps[i] - (heaps[i] ^ xorSum);
break;
}
}
// If no such heap is found, the current player loses
if (heapIndex == -1) {
printWinner((currentPlayer == 1) ? 2 : 1);
break;
}
// Make the move
if (currentPlayer == 1) {
cout << "Player A takes " << move << " from Heap " << (heapIndex + 1) << "\n";
} else {
cout << "Player B takes " << move << " from Heap " << (heapIndex + 1) << "\n";
}
makeMove(heaps, heapIndex, move);
printGameState(heaps, n);
int sum = accumulate(heaps, heaps + n, 0);
// If all heaps are emptied
if (sum == 0) {
printWinner(currentPlayer);
break;
}
// Switch the current player
currentPlayer = (currentPlayer == 1) ? 2 : 1;
xorSum = calculateXORSum(heaps, n);
// Random move for Player B
if (currentPlayer == 2) {
int randomHeapIndex;
do {
randomHeapIndex = rand() % n;
} while (heaps[randomHeapIndex] == 0);
int randomMove = getRandomMove(heaps[randomHeapIndex]);
cout << "Player B takes " << randomMove << " from Heap " << (randomHeapIndex + 1) << "\n";
makeMove(heaps, randomHeapIndex, randomMove);
printGameState(heaps, n);
// Switch the current player
currentPlayer = (currentPlayer == 1) ? 2 : 1;
xorSum = calculateXORSum(heaps, n);
}
}
}
bool isWinningPosition (int heaps[], int n) {
int xorSum = calculateXORSum(heaps, n);
return xorSum != 0;
}
int main() {
int heaps[] = {3, 4, 5};
int numHeaps = sizeof(heaps) / sizeof(heaps[0]);
if (isWinningPosition(heaps, numHeaps)) {
std::cout << "You are in a winning position!\n\n";
playNimGame(heaps, numHeaps);
} else {
std::cout << "You are in a losing position!\n\n";
}
return 0;
}
```

**Output**

You are in a winning position!

Game begins

3 4 5

Player A takes 2 from Heap 1

1 4 5

Player B takes 2 from Heap 2

1 2 5

Player A takes 2 from Heap 3

1 2 3

Player B takes 3 from Heap 3

1 2 0

Player A takes 1 from Heap 2

1 1 0

Player B takes 1 from Heap 2

1 0 0

Player A takes 1 from Heap 1

0 0 0

Player A wins

**Source:** Wikipedia