Nim’s Game | Code Implementation

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:

1. On each turn, a player must choose one heap.
2. The player can remove any number of objects from the chosen heap, but they must remove at least one object.
3. 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:

1. The game position with all heaps empty is called a “losing position” because the player who faces it will lose the game.
2. 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

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:
 
  0112    3    Heap A
  1002    4    Heap B
  1012    5    Heap C
  -----
  0102    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 ⊕ size[heap]) of 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

X is the the 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