Combinatorial Game Theory  Set 4 (Sprague – Grundy Theorem)
We have already seen in Set 2 (http://www.geeksforgeeks.org/combinatorialgametheoryset2gamenim/), that we can find who wins in a game of Nim without actually playing the game.
Suppose we change the classic Nim game a bit. This time each player can only remove 1, 2 or 3 stones only (and not any number of stones as in the classic game of Nim). Can we predict who will win?
Yes, we can predict the winner using SpragueGrundy Theorem.
What is SpragueGrundy Theorem?
Suppose there is a composite game (more than one subgame) made up of N subgames and two players, A and B. Then SpragueGrundy Theorem says that 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 XOR of the grundy numbers of position in each subgames at the beginning of the game is nonzero. Otherwise, if the XOR evaluates to zero, then player A will lose definitely, no matter what.
How to apply Sprague Grundy Theorem ?
We can apply SpragueGrundy Theorem in any impartial game and solve it. The basic steps are listed as follows:
 Break the composite game into subgames.
 Then for each subgame, calculate the Grundy Number at that position.
 Then calculate the XOR of all the calculated Grundy Numbers.
 If the XOR value is nonzero, then the player who is going to make the turn (First Player) will win else he is destined to lose, no matter what.
Example Game : The game starts with 3 piles having 3, 4 and 5 stones, and the player to move may take any positive number of stones upto 3 only from any of the piles [Provided that the pile has that much amount of stones]. The last player to move wins. Which player wins the game assuming that both players play optimally?
How to tell who will win by applying SpragueGrundy Theorem?
As, we can see that this game is itself composed of several subgames.
First Step : The subgames can be considered as each piles.
Second Step : We see from the below table that
Grundy(3) = 3 Grundy(4) = 0 Grundy(5) = 1
Third Step : The XOR of 3, 4, 5 = 2
Fourth Step : Since XOR is a nonnegative number, so we can say that the first player will win.
Below is C++ program that implements above 4 steps.

/* Game Description
"A game is played between two players and there are N piles
of stones such that each pile has certain number of stones.
On his/her turn, a player selects a pile and can take any
nonnegative number of stones upto 3 (i.e 1,2,3)
The player who cannot move is considered to lose the game
(i.e., one who take the last stone is the winner).
Can you find which player wins the game if both players play
optimally (they don't make any mistake)? "
A Dynamic Programming approach to calculate Grundy Number
and Mex and find the Winner using Sprague  Grundy Theorem. */
#include<bits/stdc++.h>
using
namespace
std;
/* piles[] > Array having the initial count of stones/coins
in each piles before the game has started.
n > Number of piles
Grundy[] > Array having the Grundy Number corresponding to
the initial position of each piles in the game
The piles[] and Grundy[] are having 0based indexing*/
#define PLAYER1 1
#define PLAYER2 2
// A Function to calculate Mex of all the values in that set
int
calculateMex(unordered_set<
int
> Set)
{
int
Mex = 0;
while
(Set.find(Mex) != Set.end())
Mex++;
return
(Mex);
}
// A function to Compute Grundy Number of 'n'
int
calculateGrundy(
int
n,
int
Grundy[])
{
Grundy[0] = 0;
Grundy[1] = 1;
Grundy[2] = 2;
Grundy[3] = 3;
if
(Grundy[n] != 1)
return
(Grundy[n]);
unordered_set<
int
> Set;
// A Hash Table
for
(
int
i=1; i<=3; i++)
Set.insert (calculateGrundy (ni, Grundy));
// Store the result
Grundy[n] = calculateMex (Set);
return
(Grundy[n]);
}
// A function to declare the winner of the game
void
declareWinner(
int
whoseTurn,
int
piles[],
int
Grundy[],
int
n)
{
int
xorValue = Grundy[piles[0]];
for
(
int
i=1; i<=n1; i++)
xorValue = xorValue ^ Grundy[piles[i]];
if
(xorValue != 0)
{
if
(whoseTurn == PLAYER1)
printf
(
"Player 1 will win\n"
);
else
printf
(
"Player 2 will win\n"
);
}
else
{
if
(whoseTurn == PLAYER1)
printf
(
"Player 2 will win\n"
);
else
printf
(
"Player 1 will win\n"
);
}
return
;
}
// Driver program to test above functions
int
main()
{
// Test Case 1
int
piles[] = {3, 4, 5};
int
n =
sizeof
(piles)/
sizeof
(piles[0]);
// Find the maximum element
int
maximum = *max_element(piles, piles + n);
// An array to cache the subproblems so that
// recomputation of same subproblems is avoided
int
Grundy[maximum + 1];
memset
(Grundy, 1,
sizeof
(Grundy));
// Calculate Grundy Value of piles[i] and store it
for
(
int
i=0; i<=n1; i++)
calculateGrundy(piles[i], Grundy);
declareWinner(PLAYER1, piles, Grundy, n);
/* Test Case 2
int piles[] = {3, 8, 2};
int n = sizeof(piles)/sizeof(piles[0]);
int maximum = *max_element (piles, piles + n);
// An array to cache the subproblems so that
// recomputation of same subproblems is avoided
int Grundy [maximum + 1];
memset(Grundy, 1, sizeof (Grundy));
// Calculate Grundy Value of piles[i] and store it
for (int i=0; i<=n1; i++)
calculateGrundy(piles[i], Grundy);
declareWinner(PLAYER2, piles, Grundy, n); */
return
(0);
}
Output :
Player 1 will win Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org