Teoria dos jogos combinatórios | Conjunto 4 (Sprague - Grundy Teorema)
Pré -requisitos: Números/números Grundy e Mex
Já vimos no Set 2 (https://www.geeksforgeeks.org/dsa/combinatorial-game-tory-set-2-game-nim/) que podemos encontrar quem vence em um jogo de NIM sem realmente jogar o jogo.
Suponha que mudemos um pouco o jogo clássico do NIM. Desta vez, cada jogador pode remover apenas 1 ou 3 pedras (e não qualquer número de pedras como no jogo clássico do NIM). Podemos prever quem vai ganhar?
Sim, podemos prever o vencedor usando o teorema de Sprague-Grundy.
O que é o teorema de Sprague-Grundy?
Suponha que haja um jogo composto (mais de um sub-jogo) composto por N Subgates e dois jogadores A e B. Então o teorema de Sprague-Grundy diz que, se o jogo A e B jogam de maneira ideal (ou seja, eles não cometem erros), o jogador é garantido pela primeira vez que não é garantido. Caso contrário, se o XOR avaliar para zero, o jogador A perderá definitivamente, não importa o quê.
Como aplicar o teorema de Sprague Grundy?
Podemos aplicar o teorema de Sprague-Grundy em qualquer jogo imparcial e resolvê -lo. As etapas básicas estão listadas da seguinte forma:
- Divida o jogo composto em subginchas.
- Em seguida, para cada sub-jogo, calcule o número Grundy nessa posição.
- Em seguida, calcule o XOR de todos os números grundy calculados.
- Se o valor do XOR for diferente de zero, o jogador que fará a curva (o primeiro jogador) vencerá mais que ele está destinado a perder, não importa o quê.
Exemplo de jogo: O jogo começa com 3 pilhas com 3 4 e 5 pedras e o jogador a se mover pode levar qualquer número positivo de pedras até 3 apenas de qualquer uma das pilhas [desde que a pilha tenha tanta quantidade de pedras]. O último jogador a se mover vence. Qual jogador vence o jogo assumindo que os dois jogadores jogam de maneira ideal?
Como saber quem vencerá aplicando o teorema de Sprague-Grundy?
Como podemos ver que este jogo é composto por vários subgatórios.
Primeiro passo: Os subgenográficos podem ser considerados como cada pilhas.
Segunda etapa: Vemos da tabela abaixo que
Grundy(3) = 3 Grundy(4) = 0 Grundy(5) = 1
Já vimos como calcular o número Grundy deste jogo no anterior artigo.
Terceira etapa: O xor de 3 0 1 = 2
Quarta etapa: Como XOR é um número diferente de zero, podemos dizer que o primeiro jogador vencerá.
Abaixo está o programa que implementa acima de 4 etapas.
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>
Saída :
Player 1 will win
Complexidade do tempo: O (n^2) onde n é o número máximo de pedras em uma pilha.
Complexidade espacial: O (n) como a matriz Grundy é usado para armazenar os resultados de subproblemas para evitar cálculos redundantes e é necessário o espaço O (n).
Referências:
https://en.wikipedia.org/wiki/sprague%E2%80%93Grundy_theorem
Exercite -se aos leitores: Considere o jogo abaixo.
Um jogo é jogado por dois jogadores com N inteiros A1 A2 .. An. Em sua vez, um jogador seleciona um número inteiro divide -o por 2 3 ou 6 e depois pega o chão. Se o número inteiro se tornar 0, ele será removido. O último jogador a se mover vence. Qual jogador vence o jogo se os dois jogadores jogam de maneira ideal?
Dica: veja o exemplo 3 de anterior artigo.
