Théorie des jeux combinatoires | Ensemble 4 (Sprague - Théorème Grundy)
Prérequis: Nombres / nombres Grundy et Mex
Nous avons déjà vu dans le set 2 (https://www.geeksforgeeks.org/dsa/combinatorial-game-theory-set-2-game-nim/) que nous pouvons trouver qui gagne dans un jeu de NIM sans réellement jouer au jeu.
Supposons que nous changeons un peu le jeu NIM classique. Cette fois, chaque joueur ne peut supprimer que 1 2 ou 3 pierres uniquement (et pas n'importe quel nombre de pierres comme dans le jeu classique de NIM). Pouvons-nous prédire qui gagnera?
Oui, nous pouvons prédire le gagnant à l'aide du théorème de Sprague-Gundy.
Qu'est-ce que le théorème de Sprague-Gundy?
Supposons qu'il y ait un jeu composite (plus d'un sous-jeu) composé de n sous-matches et de deux joueurs A et B., alors le théorème de Sprague-Gundy dit que si A et B jouent de manière optimale (c'est-à-dire qu'ils ne font aucune position), alors le joueur qui commence d'abord est garantie si le XOR du grundy de position de position dans chaque sous-jeux au début du jeu est non zéro. Sinon, si le XOR évalue à zéro, le joueur A perdra définitivement quoi qu'il arrive.
Comment appliquer le théorème de Sprague Grundy?
Nous pouvons appliquer le théorème de Sprague-Gundy dans n'importe quel jeu impartial et résolvez-le. Les étapes de base sont répertoriées comme suit:
- Cassez le jeu composite en sous-jeux.
- Ensuite, pour chaque sous-jeu, calculez le numéro Grundy à cette position.
- Calculez ensuite le XOR de tous les nombres Grundy calculés.
- Si la valeur XOR est non nul, le joueur qui va faire le tour (premier joueur) gagnera sinon il est destiné à perdre quoi qu'il arrive.
Exemple de jeu: Le jeu commence avec 3 piles ayant 3 4 et 5 pierres et le joueur à déplacer peut prendre n'importe quel nombre positif de pierres jusqu'à 3 uniquement à partir des piles [à condition que la pile ait autant de pierres]. Le dernier joueur à déménager gagne. Quel joueur remporte le jeu en supposant que les deux joueurs jouent de manière optimale?
Comment savoir qui gagnera en appliquant le théorème de Sprague-Gundy?
Comme nous pouvons le voir, ce jeu est lui-même composé de plusieurs sous-jeux.
Première étape: Les sous-jeux peuvent être considérés comme chaque piles.
Deuxième étape: Nous voyons dans le tableau ci-dessous que
Grundy(3) = 3 Grundy(4) = 0 Grundy(5) = 1
Nous avons déjà vu comment calculer les nombres Grundy de ce jeu dans le précédent article.
Troisième étape: Le xor de 3 0 1 = 2
Quatrième étape: Puisque XOR est un nombre non nul, nous pouvons dire que le premier joueur gagnera.
Vous trouverez ci-dessous le programme qui implémente au-dessus de 4 étapes.
C++ /* 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-zero number of stones upto 3 (i.e- 123) 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 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 ); }
Java import java.util.* ; /* 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-zero number of stones upto 3 (i.e- 123) 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. */ class GFG { /* 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*/ static int PLAYER1 = 1 ; static int PLAYER2 = 2 ; // A Function to calculate Mex of all the values in that set static int calculateMex ( HashSet < Integer > Set ) { int Mex = 0 ; while ( Set . contains ( Mex )) Mex ++ ; return ( Mex ); } // A function to Compute Grundy Number of 'n' static 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 ] ); // A Hash Table HashSet < Integer > Set = new HashSet < Integer > (); for ( int i = 1 ; i <= 3 ; i ++ ) Set . add ( calculateGrundy ( n - i Grundy )); // Store the result Grundy [ n ] = calculateMex ( Set ); return ( Grundy [ n ] ); } // A function to declare the winner of the game static 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 ) System . out . printf ( 'Player 1 will winn' ); else System . out . printf ( 'Player 2 will winn' ); } else { if ( whoseTurn == PLAYER1 ) System . out . printf ( 'Player 2 will winn' ); else System . out . printf ( 'Player 1 will winn' ); } return ; } // Driver code public static void main ( String [] args ) { // Test Case 1 int piles [] = { 3 4 5 }; int n = piles . length ; // Find the maximum element int maximum = Arrays . stream ( piles ). max (). getAsInt (); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int Grundy [] = new int [ maximum + 1 ] ; Arrays . fill ( Grundy - 1 ); // 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); */ } } // This code is contributed by PrinciRaj1992
Python3 ''' 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-zero number of stones upto 3 (i.e- 123) 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. 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''' PLAYER1 = 1 PLAYER2 = 2 # A Function to calculate Mex of all # the values in that set def calculateMex ( Set ): Mex = 0 ; while ( Mex in Set ): Mex += 1 return ( Mex ) # A function to Compute Grundy Number of 'n' def calculateGrundy ( n Grundy ): Grundy [ 0 ] = 0 Grundy [ 1 ] = 1 Grundy [ 2 ] = 2 Grundy [ 3 ] = 3 if ( Grundy [ n ] != - 1 ): return ( Grundy [ n ]) # A Hash Table Set = set () for i in range ( 1 4 ): Set . add ( calculateGrundy ( n - i Grundy )) # Store the result Grundy [ n ] = calculateMex ( Set ) return ( Grundy [ n ]) # A function to declare the winner of the game def declareWinner ( whoseTurn piles Grundy n ): xorValue = Grundy [ piles [ 0 ]]; for i in range ( 1 n ): xorValue = ( xorValue ^ Grundy [ piles [ i ]]) if ( xorValue != 0 ): if ( whoseTurn == PLAYER1 ): print ( 'Player 1 will win n ' ); else : print ( 'Player 2 will win n ' ); else : if ( whoseTurn == PLAYER1 ): print ( 'Player 2 will win n ' ); else : print ( 'Player 1 will win n ' ); # Driver code if __name__ == '__main__' : # Test Case 1 piles = [ 3 4 5 ] n = len ( piles ) # Find the maximum element maximum = max ( piles ) # An array to cache the sub-problems so that # re-computation of same sub-problems is avoided Grundy = [ - 1 for i in range ( maximum + 1 )]; # Calculate Grundy Value of piles[i] and store it for i in range ( n ): 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); ''' # This code is contributed by rutvik_56
C# using System ; using System.Linq ; using System.Collections.Generic ; /* 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-zero number of stones upto 3 (i.e- 123) 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. */ class GFG { /* 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*/ static int PLAYER1 = 1 ; //static int PLAYER2 = 2; // A Function to calculate Mex of all the values in that set static int calculateMex ( HashSet < int > Set ) { int Mex = 0 ; while ( Set . Contains ( Mex )) Mex ++ ; return ( Mex ); } // A function to Compute Grundy Number of 'n' static 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 ]); // A Hash Table HashSet < int > Set = new HashSet < int > (); for ( int i = 1 ; i <= 3 ; i ++ ) Set . Add ( calculateGrundy ( n - i Grundy )); // Store the result Grundy [ n ] = calculateMex ( Set ); return ( Grundy [ n ]); } // A function to declare the winner of the game static 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 ) Console . Write ( 'Player 1 will winn' ); else Console . Write ( 'Player 2 will winn' ); } else { if ( whoseTurn == PLAYER1 ) Console . Write ( 'Player 2 will winn' ); else Console . Write ( 'Player 1 will winn' ); } return ; } // Driver code static void Main () { // Test Case 1 int [] piles = { 3 4 5 }; int n = piles . Length ; // Find the maximum element int maximum = piles . Max (); // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided int [] Grundy = new int [ maximum + 1 ]; Array . Fill ( Grundy - 1 ); // 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); */ } } // This code is contributed by mits
JavaScript < script > /* 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-zero number of stones upto 3 (i.e- 123) 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. */ /* 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*/ let PLAYER1 = 1 ; let PLAYER2 = 2 ; // A Function to calculate Mex of all the values in that set function calculateMex ( Set ) { let Mex = 0 ; while ( Set . has ( Mex )) Mex ++ ; return ( Mex ); } // A function to Compute Grundy Number of 'n' function calculateGrundy ( n Grundy ) { Grundy [ 0 ] = 0 ; Grundy [ 1 ] = 1 ; Grundy [ 2 ] = 2 ; Grundy [ 3 ] = 3 ; if ( Grundy [ n ] != - 1 ) return ( Grundy [ n ]); // A Hash Table let Set = new Set (); for ( let i = 1 ; i <= 3 ; i ++ ) Set . add ( calculateGrundy ( n - i Grundy )); // Store the result Grundy [ n ] = calculateMex ( Set ); return ( Grundy [ n ]); } // A function to declare the winner of the game function declareWinner ( whoseTurn piles Grundy n ) { let xorValue = Grundy [ piles [ 0 ]]; for ( let i = 1 ; i <= n - 1 ; i ++ ) xorValue = xorValue ^ Grundy [ piles [ i ]]; if ( xorValue != 0 ) { if ( whoseTurn == PLAYER1 ) document . write ( 'Player 1 will win
' ); else document . write ( 'Player 2 will win
' ); } else { if ( whoseTurn == PLAYER1 ) document . write ( 'Player 2 will win
' ); else document . write ( 'Player 1 will win
' ); } return ; } // Driver code // Test Case 1 let piles = [ 3 4 5 ]; let n = piles . length ; // Find the maximum element let maximum = Math . max (... piles ) // An array to cache the sub-problems so that // re-computation of same sub-problems is avoided let Grundy = new Array ( maximum + 1 ); for ( let i = 0 ; i < maximum + 1 ; i ++ ) Grundy [ i ] = 0 ; // Calculate Grundy Value of piles[i] and store it for ( let 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); */ // This code is contributed by avanitrachhadiya2155 < /script>
Sortir :
Player 1 will win
Complexité du temps: O (n ^ 2) où n est le nombre maximum de pierres dans une pile.
Complexité de l'espace: O (n) Comme le tableau Grundy est utilisé pour stocker les résultats des sous-problèmes pour éviter les calculs redondants et il faut o (n) espace.
Références:
https://en.wikipedia.org/wiki/Sprague%E2%80%93grundy_theorem
Exercice aux lecteurs: Considérez le jeu ci-dessous.
Un jeu est joué par deux joueurs avec n entiers a1 a2 .. an. À son tour, un joueur sélectionne un entier le divise par 2 3 ou 6, puis prend le sol. Si l'entier devient 0, il est supprimé. Le dernier joueur à déménager gagne. Quel joueur remporte le jeu si les deux joueurs jouent de manière optimale?
Astuce: voir l'exemple 3 de précédent article.
![Méthode Java main() – public static void main (String[] args)](https://techcodeview.com/img/java-basics/92/java-main-method-public-static-void-main.webp)
