# 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? */ #include<bits/stdc++.h> 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()) Mex++; 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); return(Grundy[n]); } // 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); } ********************************************************************************************* ********************************************************************************************* ->IMPORTANT : 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. |

## Recent Comments