Prerequisites : Grundy Numbers/Numbers and Mex
We have already seen in Set 2 (https://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:
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
We have already seen how to calculate the Grundy Numbers of this game in the previous article.
Third Step : The XOR of 3, 0, 1 = 2
Fourth Step : Since XOR is a non-zero number, so we can say that the first player will win.
Below is the program that implements above 4 steps.