Advanced Nim’s Game

What is the Advance Game of Nim?

Let us discuss what the Standard Game of Nim or Nim Game is before we define the Advanced Game of Nim(Zero Move Nim Game).

The Game of Nim or Nim game is a mathematical combinatorial game in which we have a pile of some objects, say coins in this case, and two players who will take turns one after the other. In each turn, a player must pick at least one object(coin in this case), and may remove any number of objects(coins) given that they all belong to the same pile. The game is won by the one who picks the last object(coin).

In Advanced Game of Nim, for each non-empty pile, either of the players can remove zero items and be counted as its move, but this move can only be used once per pile by either of the players. This is a slight modification over the standard nim game.

Before we move on to the approach to solve the advanced game of nim, let us understand some terms related to the solution.

Grundy Number

A Grundy Number is a number that defines a state of a combinatorial game. Using Grundy Number we can define any Impartial Game(such as Nim Game).

Before we revisit the Grundy Number, let us understand another term MEX(Minimum Excludant).

MEX(Minimum Excludant)

Minimum Excludant (MEX)is the smallest non-negative number not present in a set of numbers, that is the minimum value of the complement set. The Minimum Excluded values are also used in greedy coloring algorithms in graph theory.

Lets take a look at some examples to understand how Minimum Excludant (or MEX) works:

Examples:

• $MEX(Φ) = 0$
  • The Minimum Excludant (or MEX) of a null set ($Φ$) is $0$.
• $MEX({1, 2, 3}) = 0$
  • The Minimum Excludant (or MEX) of this set is $0$
• $MEX({0, 2, 4, 6, ..}) = 1$
  • The Minimum Excludant (or MEX) of a set of all even numbers is the first odd number, that is $1$.
• $MEX({0, 1, 2, 3, 4, 7, 149}) = 5$
  • The Minimum Excludant (or MEX) of this set is $5$.
• $MEX({0, 1, 2, 3,..., ω}) = ω+1$
  • The Minimum Excludant (or MEX) of this set is $ω+1$, where $ω$ is the ordinal limit of the natural numbers.
• $MEX({0, 1, 2, 3,...}) = ω$
  • The Minimum Excludant (or MEX) of this set is $ω$, where $ω$ is the ordinal limit of the natural numbers.

Now that we have a basic understanding of how the MEX works, let us take a look at how MEX helps us in calculating the Grundy number ($G(N)$) next.

How to calculate Grundy Number?

The calculation of the Grundy Number is based on the following statement: The Grundy Number is equal to 0 for a game that is immediately lost by the player who plays first, otherwise, the Grundy Number is equal to the MEX of all the numbers which are possible next positions by making one move in the game.

Let us take a look at an example to see how we can calculate the Grundy Number.

The game will start with a pile of N coins and two players. The player whose turn is first may move any number of positive coins. The last player to move any number of coins wins the game. Before moving onto some cases, for simplicity, we'll say that the $Grundy(N)$ is written as $G(N)$.

Let us take a look at some cases:

Let N be the number of coins in the pile.

1. N = 0 : If the pile has 0 coins then the first player has nothing to pick and loses the game immediately, thus,

   $G(0)$ = $0$

2. N = 1 : If the pile has 1 coin then he has the following one option :

   1. The player picks 1 coin, then 0 coins are left whose Grundy value is G(0)=0.

   $G(1)$ = $MEX(\{G(0)\})$ = $MEX(\{0\})$ = $1$.

3. N = 2 : If the pile has 2 coin then he has the following options :

   1. The player picks 1 coin, then 1 coin is left whose Grundy value is G(1)=1.
   2. The player picks 2 coin, then 0 coins are left whose Grundy value is G(0)=0.

   $G(2)$ = $MEX(\{G(0),G(1)\})$ = $MEX(\{0,1\})$ = $2$.

4. N = 3 : If the pile has 3 coin then he has the following options :

   1. The player picks 1 coin, then 2 coins are left whose Grundy value is G(2)=2.
   2. The player picks 2 coin, then 1 coin is left whose Grundy value is G(1)=1.
   3. The player picks 3 coin, then 0 coins are left whose Grundy value is G(0)=0.

   $G(3)$ = $MEX(\{G(0),G(1),G(2)\})$ = $MEX(\{0,1,2\})$ = $3$.

5. N = 4 : If the pile has 4 coin then he has the following options :

   1. The player picks 1 coin, then 3 coins are left whose Grundy value is G(3)=3.
   2. The player $picks 2 coin, then 2 coins are left whose Grundy value is G(2)=2.
   3. The player picks 3 coin, then 1 coin is left whose Grundy value is G(1)=1.
   4. The player picks 4 coin, then 0 coins are left whose Grundy value is G(0)=0.

   $G(4)$ = $MEX(\{G(0),G(1),G(2),G(3)\})$ = $MEX(\{0,1,2,3\})$ = $4$.

6. N = 5 : If the pile has 5 coin then he has the following options :

   1. The player picks 1 coin, then 4 coins are left whose Grundy value is G(4)=4.
   2. The player picks 2 coin, then 3 coins are left whose Grundy value is G(3)=3.
   3. The player picks 3 coin, then 2 coins are left whose Grundy value is G(2)=2.
   4. The player picks 4 coin, then 1 coin is left whose Grundy value is G(1)=1.
   5. The player picks 5 coin, then 0 coins are left whose Grundy value is G(0)=0.

   $G(4)$ = $MEX(\{G(0),G(1),G(2),G(3),G(4)\})$ = $MEX(\{0,1,2,3,4\})$ = $5$.

Let us formulate the size of the pile with its corresponding Grundy Number and try to find if it follows some pattern or not.

From the above table, it can be easily observed that for any $N$ its corresponding Grundy Number that is $Grundy(N)$ or $G(N)$ is $N$.

Also, note that the problem that we just discussed above is actually the Standard Game of Nim. Therefore just like the way we $XOR$(Exclusive-OR) the Grundy Number of the size of piles to solve Standard Game of Nim we will use the same method over here but before we do that let us find the Grundy Number for Advanced Nim game(Zero Move Nim game).

Approach

We'll first try to find the Grundy Number (Grundy(N)) for some simple values of N, where N is the size of a pile of coins.

For simplicity, we will call the move of picking zero coins as zero moves and,

$G(N)$ is the Grundy Number of N that is $Grundy(N)$. nF as the pile of size N with no zero moves left. nT as the pile of size N with zero moves left ( we can reach the state of nF from nT for a value of n but the reverse is not possible since we can only use the zero move once).

Also, we should note that Grundy(N) is actually equivalent to Grundy(nT), thus for every N, its corresponding Grundy number will be Grundy(nT).

Let us look at some cases now:

1. N = 0 : If the pile has 0 coins then the first player has nothing to pick and loses the game immeditely,thus, $G(0)$ = $0$

Note: We cannot pick 0 coin because the zero move is defined that it can only be applied to a pile having non zero coins.

2. N = 1 : There are two cases in this:

   1. nF = 1 : Pile of size 1 with no zero move left:
      1. The player picks 1 coin, then 0 coins are left. $G(1F)$ = $MEX(\{0\})$ = $1$
   2. nT = 1 : Pile of size 1 with zero move left:
      1. The player picks 1 coin, then 0 coins are left.
      2. The player make the zero move and does not pick any coin, this new state is now 1F (pile of size 1 with no zero move left) $G(1T)$ = $MEX(\{0,G(1F)\})$ = = $MEX(\{0,1\})$ = $2$

   Therefore, $G(1)$ = $G(1T)$ = $2$

3. N = 2 : There are two cases in this:

   1. nF = 2 : Pile of size 2 with no zero move left:
      1. The player picks 2 coin, then 0 coins are left.
      2. The player picks 1 coin, then 1 coins are left, this new state is now 1F (pile of size 1 with no zero move left). $G(2F)$ = $MEX(\{0,G(1F)\})$ = = $MEX(\{0,1\})$ = $2$
   2. nT = 2 : Pile of size 2 with zero move left:
      1. The player picks 2 coin, then 0 coins are left.
      2. The player picks 1 coin, then 1 coin is left, this new state is now 1T (pile of size 1 with zero move left).
      3. The player make the zero move and does not pick any coin, this new state is now 2F (pile of size 2 with no zero move left) $G(2T)$ = $MEX(\{0,G(1T),G(2F)\})$ = = $MEX(\{0,2,2\})$ = $1$

   Therefore, $G(2)$ = $G(2T)$ = $1$

Note: We cannot create the state 1F(pile of size 2 with no zero move left) from the current state that is 2T because we would have to make two different moves i.e., pick 1 coin from the pile and make a zero move while we are allowed to make only one move.

4. N = 3 : There are two cases in this:

   1. nF = 3 : Pile of size 3 with no zero move left:
      1. The player picks 3 coin, then 0 coins are left.
      2. The player picks 2 coin, then 1 coins are left, this new state is now 1F (pile of size 1 with no zero move left).
      3. The player picks 1 coin, then 2 coins are left, this new state is now 2F (pile of size 2 with no zero move left). $G(3F)$ = $MEX(\{0,G(1F),G(2F)\})$ = = $MEX(\{0,1,2\})$ = $3$
   2. nT = 3 : Pile of size 3 with zero move left:
      1. The player picks 3 coin, then 0 coins are left.
      2. The player picks 2 coin, then 1 coins are left, this new state is now 1T (pile of size 1 with zero move left).
      3. The player picks 1 coin, then 2 coin is left, this new state is now 2T (pile of size 2 with zero move left).
      4. The player make the zero move and does not pick any coin, this new state is now 3F (pile of size 3 with no zero move left) $G(3T)$ = $MEX(\{0,G(1T),G(2T),G(3F)\})$ = = $MEX(\{0,2,1,3\})$ = $4$

   Therefore, $G(3)$ = $G(3T)$ = $4$

5. N = 4 : There are two cases in this:

   1. nF = 4 : Pile of size 4 with no zero move left:
      1. The player picks 4 coin, then 0 coins are left.
      2. The player picks 3 coin, then 1 coins are left, this new state is now 1F (pile of size 1 with no zero move left).
      3. The player picks 2 coin, then 2 coins are left, this new state is now 2F (pile of size 2 with no zero move left).
      4. The player picks 1 coin, then 3 coins are left, this new state is now 3F (pile of size 3 with no zero move left). $G(4F)$ = $MEX(\{0,G(1F),G(2F),G(3F)\})$ = = $MEX(\{0,1,2,3\})$ = $4$
   2. nT = 4 : Pile of size 4 with zero move left:
      1. The player picks 4 coin, then 0 coins are left.
      2. The player picks 3 coin, then 1 coins are left, this new state is now 1T (pile of size 1 with zero move left).
      3. The player picks 2 coin, then 2 coins are left, this new state is now 2T (pile of size 2 with zero move left).
      4. The player picks 1 coin, then 3 coin is left, this new state is now 3T (pile of size 3 with zero move left).
      5. The player make the zero move and does not pick any coin, this new state is now 4F (pile of size 4 with no zero move left) $G(2T)$ = $MEX(\{0,G(1T),G(2T),G(3T),G(4F)\})$ = $MEX(\{0,2,1,4,4\})$ = $3$

   Therefore, $G(4)$ = $G(4T)$ = $3$

6. N = 5 : There are two cases in this:

   1. nF = 5 : Pile of size 5 with no zero move left:
      1. The player picks 5 coin, then 0 coins are left.
      2. The player picks 4 coin, then 1 coins are left, this new state is now 1F (pile of size 1 with no zero move left).
      3. The player picks 3 coin, then 2 coins are left, this new state is now 2F (pile of size 2 with no zero move left).
      4. The player picks 2 coin, then 3 coins are left, this new state is now 3F (pile of size 3 with no zero move left).
      5. The player picks 1 coin, then 4 coins are left, this new state is now 4F (pile of size 4 with no zero move left). $G(4F)$ = $MEX(\{0,G(1F),G(2F),G(3F),G(4F)\})$ = = $MEX(\{0,1,2,3,4\})$ = $5$
   2. nT = 5 : Pile of size 5 with zero move left:
      1. The player picks 5 coin, then 0 coins are left.
      2. The player picks 4 coin, then 1 coins are left, this new state is now 1T (pile of size 1 with zero move left).
      3. The player picks 3 coin, then 2 coins are left, this new state is now 2T (pile of size 2 with zero move left).
      4. The player picks 2 coin, then 3 coins are left, this new state is now 3T (pile of size 3 with zero move left).
      5. The player picks 1 coin, then 4 coin is left, this new state is now 4T (pile of size 4 with zero move left).
      6. The player make the zero move and does not pick any coin, this new state is now 4F (pile of size 4 with no zero move left) $G(2T)$ = $MEX(\{0,G(1T),G(2T),G(3T),G(4T),G(5F)\})$ = $MEX(\{0,2,1,4,3,5\})$ = $6$

   Therefore, $G(5)$ = $G(5T)$ = $6$

Let us now formulate the size of the pile with its corresponding Grundy Number and try to find if it follows some pattern or not.

From the above table, it can be easily observed that for any $N$ its corresponding Grundy Number that is $Grundy(N)$ is either $N+1$ if $N$ is odd or $N-1$ if $N$ is even, i.e.

Now that we have the formula to find the Grundy number of any state (that is G(N)), let us move forward to define the Winning State and the Losing State of the game.

Winning State and Losing State

As we have noticed and pointed out above that this game is very analogous to the Standard Game of Nim (Nim Game), we shall be using a similar method of using the Cumulative XOR(Nim Sum) to define the winning state (Winner of the game) and the losing state (Loser of the game). We shall only talk about the player whose going to play first when we talk about the Winning state or losing state.

For an array Piles[] which represents the sizes of the pile of coins,

Winning State

Considering both the players play optimally, which means that they don’t make any moves that may hamper their chances of winning, then the player to play first will win the game if and only if the Cumulative XOR(Nim Sum) of the Grundy Number of the size of the piles is Non-zero.

Losing State

Otherwise, the player to play first will lose the game if and only if the Nim Sum of the Grundy Number of the size of the piles is Zero.

Example

Let us take a look at some examples before implementing the code.

Example 1:

Given piles of coins are:

Input:

$Piles[]$ = {$4$, $7$, $5$}

Output:

Player 1 wins the game.

Explanation: Let us first calculate the equivalent Grundy number for each pile $Grundy[]$ = {${ 3, 8, 6}$}

Now we calculate the Nim Sum(Cumulative XOR)

$Nim Sum$ = (3^8^6) = $12$

Since the Nim sum is Non-Zero, Player 1 wins the game, Let us take a look at another example before moving forward.

Example 2:

Given piles of coins are:

Input:

$Piles[]$ = {$10$, $4$, $9$}

Output:

Player 2 wins the game.

Explanation: Let us first calculate the equivalent Grundy number for each pile $Grundy[]$ = {${ 9, 3, 10}$}

Now we calculate the Nim Sum(Cumulative XOR)

$Nim Sum$ = (9^3^10) = $0$

Since the Nim sum is Zero, Player 2 wins the game.

Let us now look at the implementation of the above logic.

Implementation in C++

Output

Time and Space Complexity

The Time Complexity of the above defined solution is $O(n)$ where n is the size of the piles' array. However, the auxiliary space complexity is $O(1)$, since no additional space has been used as we just need one variable to store the Nim sum(cumulative XOR).