Problem 3: Consider a variation of Game of Nim. The game begins with a single pi

Question

Problem 3: Consider a variation of Game of Nim. The game begins with a single pile of stones. The move by a player consists of dividing the pile into two piles that contain unequal number of stones. For example, if one pile contains six stones, it could be subdivided into piles of 5 and 1, or 4 and 2, but not 3 and 3 The first player who cannot make a move loses the game. A. Draw the complete game tree for this version of Nim if the start state consists of 6 stones B. Perform a minimax evaluation for this game. Let 1 denote a win and -1 a loss [40 Points, 20 points each]

Explanation / Answer

Approach:
Grundy number for each pile is calculated based on the number of stones.To compensate the zero move we will have to modify grundy values we used in standard nim game.
If pile size is odd; grundy number is size+1 and
if pile size is even; grundy number is size-1.
We XOR all the grundy number values to check if final Grundy number(G) of game is non zero or not to decide who is winner of game.

Explanation:
Grundy number of a state is the smallest positive integer that cannot be reached in one valid move.
So, we need to calculate mex value for each n, bottom up wise so that we can induce the grundy number for each n. where n is the pile size and valid move is the move that will lead the current player to winning state.

Winning state: A tuple of values from where the current player will win the game no matter what opponent does. (If G!=0)
Losing state: A tuple of values from where the current player will loose the game no matter what opponent does. (If G=0)

For a given pile size n, we have two states:
(1) n with no zero move available,
grundy number will same as standard nim game.
(2) n with zero move available, we can
reach above state and other states with
zero move remaining.

For, n = 0, g(0) = 0, empty pile

For, n = 1, we can reach two states:
(1) n = 0 (zero move not used)
(2) n = 1 (zero move used)
Therefore, g(1) = mex{0, 1} which implies
that g(1)=2.

For, n = 2, we can reach :
(1) n = 0 (zero move not used) state
because this is a valid move.
(2) n = 1 is not a valid move, as it will
lead the current player into loosing state.
Therefore, g(2) = mex{0} which implies
that g(2)=1.

If we try to build a solution bottom-up
like this, it turns out that if n is even,
the grundy number is n - 1 and when it is odd,
the grundy is n + 1.
Below is the implementation of above approach:

// CPP program for the variation
// in nim game
#include <bits/stdc++.h>
using namespace std;

// Function to return final
// grundy Number(G) of game
int solve(int p[], int n)
{
int G = 0;
for (int i = 0; i < n; i++) {

// if pile size is odd
if (p[i] & 1)
  
// We XOR pile size+1
G ^= (p[i] + 1);

else // if pile size is even

// We XOR pile size-1
G ^= (p[i] - 1);
}
return G;
}

// driver program
int main()
{
// Game with 3 piles
int n = 3;

// pile with different sizes
int p[3] = { 32, 49, 58 };

// Function to return result of game
int res = solve(p, n);

if (res == 0) // if G is zero
cout << "Player 2 wins";
else // if G is non zero
cout << "Player 1 wins";

return 0;
}

// Recursion tree I am not able to upload

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.