Combinatorial Game Theory | Set 4 (Sprague – Grundy Theorem)

link 0

We have already seen in Set 2 (http://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/), 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 Sprague-Grundy Theorem.

What is Sprague-Grundy Theorem?
Suppose there is a composite game (more than one sub-game) made up of N sub-games and two players, A and B. Then Sprague-Grundy 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 sub-games at the beginning of the game is non-zero. 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 Sprague-Grundy Theorem in any impartial game and solve it. The basic steps are listed as follows:

  1. Break the composite game into sub-games.
  2. Then for each sub-game, calculate the Grundy Number at that position.
  3. Then calculate the XOR of all the calculated Grundy Numbers.
  4. If the XOR value is non-zero, 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 Sprague-Grundy Theorem?
As, we can see that this game is itself composed of several sub-games.

First Step : The sub-games can be considered as each piles.
Second Step : We see from the below table that

Grundy(3) = 3
Grundy(4) = 0 
Grundy(5) = 1

Sprague - Grundy Theorem

 

Third Step : The XOR of 3, 4, 5 = 2

Fourth Step : Since XOR is a non-negative 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
 non-negative 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 0-based 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 (n-i, 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<=n-1; 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 sub-problems so that
    // re-computation of same sub-problems 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<=n-1; 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 sub-problems so that
    // re-computation of same sub-problems 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<=n-1; 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

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar