Requisitos previos: Grundy Numbers/Numbers y Mex
Ya vimos en el Set 2 (https://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/), que podemos encontrar quién gana en un juego de Nim sin realmente jugar el juego.
Supongamos que cambiamos un poco el clásico juego de Nim. Esta vez cada jugador solo puede quitar 1, 2 o 3 piedras (y no cualquier número de piedras como en el clásico juego de Nim). ¿Podemos predecir quién ganará?
Sí, podemos predecir el ganador usando el Teorema de Sprague-Grundy.
¿Qué es el teorema de Sprague-Grundy?
Supongamos que hay un juego compuesto (más de un subjuego) formado por N subjuegos y dos jugadores, A y B. Entonces el teorema de Sprague-Grundy dice que si tanto A como B juegan de manera óptima (es decir, no comete ningún error), entonces el jugador que comienza primero tiene la garantía de ganar si el XOR de los números grundy de posición en cada subjuego al comienzo del juego no es cero. De lo contrario, si el XOR se evalúa como cero, entonces el jugador A definitivamente perderá, pase lo que pase.
¿Cómo aplicar el Teorema de Sprague Grundy?
Podemos aplicar el Teorema de Sprague-Grundy en cualquier juego imparcial y resolverlo. Los pasos básicos se enumeran a continuación:
- Divide el juego compuesto en subjuegos.
- Luego, para cada subjuego, calcule el número de Grundy en esa posición.
- Luego calcule el XOR de todos los números de Grundy calculados.
- Si el valor de XOR es distinto de cero, entonces el jugador que va a hacer el turno (primer jugador) ganará, de lo contrario, está destinado a perder, pase lo que pase.
Juego de ejemplo: El juego comienza con 3 pilas que tienen 3, 4 y 5 piedras, y el jugador que mueve puede tomar cualquier número positivo de piedras hasta 3 solo de cualquiera de las pilas [siempre que la pila tenga esa cantidad de piedras]. El último jugador en moverse gana. ¿Qué jugador gana el juego suponiendo que ambos jugadores juegan de manera óptima?
¿Cómo saber quién ganará aplicando el Teorema de Sprague-Grundy?
Como podemos ver, este juego se compone de varios subjuegos.
Primer paso: los subjuegos se pueden considerar como montones.
Segundo paso: Vemos en la siguiente tabla que
Grundy(3) = 3 Grundy(4) = 0 Grundy(5) = 1
Ya hemos visto cómo calcular los Números Grundy de este juego en el artículo anterior .
Tercer paso: el XOR de 3, 0, 1 = 2
Cuarto paso: dado que XOR es un número distinto de cero, podemos decir que el primer jugador ganará.
A continuación se muestra el programa que implementa los 4 pasos anteriores.
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- 1,2,3)
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<bits/stdc++.h>
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- 1,2,3)
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 win\n");
else
System.out.printf("Player 2 will win\n");
}
else
{
if (whoseTurn == PLAYER1)
System.out.printf("Player 2 will win\n");
else
System.out.printf("Player 1 will win\n");
}
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- 1,2,3)
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- 1,2,3)
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 win\n");
else
Console.Write("Player 2 will win\n");
}
else
{
if (whoseTurn == PLAYER1)
Console.Write("Player 2 will win\n");
else
Console.Write("Player 1 will win\n");
}
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- 1,2,3)
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<br>");
else
document.write("Player 2 will win<br>");
}
else
{
if (whoseTurn == PLAYER1)
document.write("Player 2 will win<br>");
else
document.write("Player 1 will win<br>");
}
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>
Producción :
Player 1 will win
Referencias:
https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
Ejercicio para los lectores: Considere el siguiente juego.
“Un juego es jugado por dos jugadores con N números enteros A1, A2, .., AN. En su turno, un jugador selecciona un número entero, lo divide por 2, 3 o 6 y luego toma la palabra. Si el entero se convierte en 0, se elimina. El último jugador en moverse gana. ¿Qué jugador gana el juego si ambos jugadores juegan de manera óptima?
Sugerencia: consulte el ejemplo 3 del artículo anterior .
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA