Basics of Game Theory

Some Basics of Game Theory.
Q1.Let us suppose that you have 74 coins and you can pick minimum 2 coins and maximum 6 coins and There are two players A and B
how much coins should a pick at start to win the game.
Ans 1: You have to reduce 74 to multiple of (2+6)

so A will reduce 74 to 72.Now its Finders winners means the player who plays
last turn wins the match At each turn

A will reduce the game to multiple of 8 to win the game at last suppose at last
the number will arrive at 8 now B will pick any thing

between 2 and 6 coins a will pick the left over coin and wins the match.
But if it would be a Keepers losers game than
we have to reduce the number to multiple of 8 + x (Where x is equal to 1<x<=a ).

**************************** Composite Game / Grundy Number *********


Imp-> We will use sprague grundy theorem in that case in

which we are not suppose to choose any no of coins we want we have a limit


Q2.Calculate Grundy Number.
/* A Dynamic Programming (Memoization-based) approach to
calculate Grundy Number of a Game
Game Description-
Just like a one-pile version of Nim, the game starts with
a pile of n stones, and the player to move may take any positive number of stones.
The last player to move wins. Which player wins the game? */


using namespace std;

// A Function to calculate Mex of all the values in that set

// This function remains same

int calculateMex(unordered_set<int> Set)


int Mex = 0;

while (Set.find (Mex) != Set.end())


return (Mex);


// A function to Compute Grundy Number of ‘n’

// Only this function varies according to the game

int calculateGrundy(int n, int Grundy[])


if (n == 0)

return (0);

if (Grundy[n] != -1)

return (Grundy[n]);

unordered_set<int> Set; // A Hash Table

for (int i=0; i<=n-1; i++)

Set.insert(calculateGrundy(i, Grundy));

// Store the result

Grundy[n] = calculateMex (Set);



// Driver program to test above functions

int main()


int n = 10;

// An array to cache the sub-problems so that

// re-computation of same sub-problems is avoided

int Grundy[n+1];

memset (Grundy, -1, sizeof(Grundy));
printf (“%d”, calculateGrundy(n, Grundy));
return (0);





Now we know that when we have to calculate grundy number now if We have N piles and we have to pick minimum x coins and maximum

y coins so here we will use Sprague grundy theorem. We will calculate XOR of all grundy theorem if it comes zero 2nd PLayer

would win either A.

You may also like...

Leave a Reply

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

%d bloggers like this: