Teória kombinatorických hier Set 4 (Sprague - Grundyova veta)
Predpoklady: Grundy čísla/čísla a MEX
Už sme videli v set 2 (https://www.geeksforgeeks.org/dsa/combinatorial-game-ceory-set-2-game-nim/, že môžeme nájsť, kto vyhrá v hre Nim bez toho, aby sa hral hra.
Predpokladajme, že trochu zmeníme klasickú hru NIM. Tentoraz môže každý hráč odstrániť iba 1 2 alebo 3 kamene (a nie akýkoľvek počet kameňov ako v klasickej hre NIM). Môžeme predpovedať, kto vyhrá?
Áno, môžeme predpovedať víťaza pomocou Sprague-Grundyovej vety.
Čo je to veta Sprague-Grundy?
Predpokladajme, že existuje kompozitná hra (viac ako jedna čiastková hra) zložená z n-hier N a dvoch hráčov A a B. Potom Sprague-Grundy Theorém hovorí, že ak A aj B hrajú optimálne (t. V opačnom prípade, ak XOR vyhodnotí na nulu, potom hráč A určite stratí bez ohľadu na to, čo.
Ako aplikovať Sprague Grundy Vetu?
Môžeme aplikovať Sprague-Grunditicu vetu v každom nestranná hra a vyriešiť to. Základné kroky sú uvedené takto:
- Rozdeľte kompozitnú hru na čiastkové hry.
- Potom pre každú čiastkovú hru vypočítajte číslo Grundy v tejto polohe.
- Potom vypočítajte XOR všetkých vypočítaných čísel Grundy.
- Ak je hodnota XOR nenulová, potom hráč, ktorý sa chystá otočiť (prvý hráč), vyhrá inak, je predurčený stratiť bez ohľadu na to.
Príkladová hra: Hra začína 3, ktoré majú 3 hromady, ktoré majú 3 4 a 5 kameňov, a hráč, ktorý sa má pohybovať, môže vziať akýkoľvek kladný počet kameňov do 3 iba od ktorejkoľvek z hromád [za predpokladu, že hromada má toľko množstva kameňov]. Posledný hráč sa pohybuje. Ktorý hráč vyhrá hru za predpokladu, že obaja hráči hrajú optimálne?
Ako povedať, kto vyhrá tým, že uplatňuje Grundy Grundy?
Ako vidíme, že táto hra je sama o sebe zložená z niekoľkých čiastkových hier.
Prvý krok: Podiely môžu byť považované za každé hromady.
Druhý krok: Vidíme z nižšie uvedenej tabuľky, ktorá
Grundy(3) = 3 Grundy(4) = 0 Grundy(5) = 1
Už sme videli, ako vypočítať grundy čísla tejto hry v predchádzajúci článok.
Tretí krok: Xor z 3 0 1 = 2
Štvrtý krok: Pretože XOR je nenulové číslo, takže môžeme povedať, že prvý hráč vyhrá.
Nižšie je program, ktorý implementuje nad 4 kroky.
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>
Výstup:
Player 1 will win
Časová zložitosť: O (n^2), kde n je maximálny počet kameňov v hromade.
Zložitosť vesmíru: O (n) Pretože sa Grundy pole používa na ukladanie výsledkov podprava, aby sa predišlo redundantným výpočtom a zaberá priestor O (n).
Referencie:
https://en.wikipedia.org/wiki/sprague%E2%80%93Grundy_theorerem
Cvičte čitateľom: Zvážte nižšie uvedenú hru.
Hra hra hrajú dvaja hráči s N Celné čísla A1 A2 .. An. Na svojom odbočení hráč vyberie celé číslo, ktoré ho rozdeľuje o 2 3 alebo 6 a potom vezme podlahu. Ak sa celé číslo dostane 0, odstráni sa. Posledný hráč sa pohybuje. Ktorý hráč vyhrá hru, ak obaja hráči hrajú optimálne?
Tip: Pozri príklad 3 predchádzajúci článok.
