# 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```

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

Skip to toolbar