Teoría de juegos combinatorios | Juego 3 (Grundy Numbers/Numbers y Mex)

Hemos presentado la Teoría de Juegos Combinatorios en el Conjunto 1 y discutido el Juego de Nim en el Conjunto 2 .
Grundy Number es un número que define un estado de un juego. Podemos definir cualquier juego imparcial (ejemplo: juego de nim) en términos de Número de Grundy.

Los Números Grundy o Números determinan cómo se puede resolver cualquier Juego Imparcial (no solo el Juego de Nim) una vez que hemos calculado los Números Grundy asociados con ese juego usando el Teorema de Sprague-Grundy.
Pero antes de calcular los números de Grundy, necesitamos aprender sobre otro término: Mex.

¿Qué es Méx?  
El ‘mínimo excluyente’, también conocido como ‘Mex’, de un conjunto de números es el número no negativo más pequeño que no está presente en el conjunto. 
 

¿Cómo calcular los números de Grundy?  
Usamos esta definición: el número de Grundy es igual a 0 para un juego que el primer jugador pierde inmediatamente y es igual a Mex de los números de todas las siguientes posiciones posibles para cualquier otro juego.
A continuación se muestran tres juegos y programas de ejemplo para calcular Grundy Number y Mex para cada uno de ellos. El cálculo de los números de Grundy se realiza básicamente mediante una función recursiva llamada función de cálculo de Grundy() que utiliza la función de cálculo de Mex() como su subrutina.

Ejemplo 1 
El juego comienza con una pila de n piedras, y el jugador que se mueve puede tomar cualquier número positivo de piedras. Calcula los números de Grundy para este juego. El último jugador en moverse gana. ¿Qué jugador gana el juego?
Dado que si el primer jugador tiene 0 piedras, perderá inmediatamente, entonces Grundy(0) = 0
Si un jugador tiene 1 piedras, puede tomar todas las piedras y ganar. Entonces, la siguiente posición posible del juego (para el otro jugador) es (0) piedras.
Por lo tanto, Grundy (1) = Mex (0) = 1 [Según la definición de Mex]
De manera similar, si un jugador tiene 2 piedras, entonces puede tomar solo 1 piedra o puede tomar todas las piedras y gana. Entonces, la siguiente posición posible del juego (para el otro jugador) es (1, 0) piedras respectivamente.
Por lo tanto, Grundy(2) = Mex(0, 1) = 2 [Según la definición de Mex]
Similarmente, si un jugador tiene ‘n’ piedras, entonces puede tomar solo 1 piedra, o puede tomar 2 piedras… .. o puede tomar todas las piedras y ganar. Así que la siguiente posición posible del juego (para el otro jugador) es (n-1, n-2,….1) piedras respectivamente.
Por tanto, Grundy(n) = Mex (0, 1, 2, ….n-1) = n [Según la definición de Mex] 

Resumimos el primer valor de Grundy de 0 a 10 en la siguiente tabla: 

/* A recursive C++ program to find Grundy Number for
   a game which is like a one-pile version of Nim.
  Game Description : 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.
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)
{
    if (n == 0)
        return (0);
  
    unordered_set<int> Set; // A Hash Table
  
    for (int i=0; i<=n-1; i++)
            Set.insert(calculateGrundy(i));
  
    return (calculateMex(Set));
}
  
// Driver program to test above functions
int main()
{
    int n = 10;
    printf("%d", calculateGrundy(n));
    return (0);
}

// A recursive Java program to find Grundy
// Number for a game which is like a 
// one-pile version of Nim. Game 
// Description : 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? 
import java.util.*; 
  
class GFG{
      
// A Function to calculate Mex of all
// the values in that set. 
public static int calculateMex(Set<Integer> Set) 
{ 
    int Mex = 0; 
    
    while (Set.contains(Mex)) 
        Mex++; 
    
    return (Mex); 
} 
    
// A function to Compute Grundy Number
// of 'n'. Only this function varies
// according to the game 
public static int calculateGrundy(int n) 
{ 
    if (n == 0) 
        return (0); 
          
    // A Hash Table 
    Set<Integer> Set = new HashSet<Integer>();   
    
    for(int i = 0; i <= n - 1; i++) 
        Set.add(calculateGrundy(i)); 
    
    return (calculateMex(Set)); 
} 
  
// Driver code
public static void main(String[] args)
{
    int n = 10;
      
    System.out.print(calculateGrundy(n));
}
}
  
// This code is contributed by divyeshrabadiya07

''' A recursive Python3 program to find Grundy Number for
a game which is like a one-pile version of Nim.
Game Description : 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? '''
  
# 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'
# Only this function varies according to the game
def calculateGrundy( n):
    if (n == 0):
        return (0)
  
    Set = set() # A Hash Table
  
    for i in range(n):
        Set.add(calculateGrundy(i));
  
    return (calculateMex(Set))
  
# Driver program to test above functions
n = 10;
print(calculateGrundy(n))
  
# This code is contributed by ANKITKUMAR34

// A recursive C# program to find Grundy
// Number for a game which is like a 
// one-pile version of Nim. Game 
// Description : 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?
using System;
using System.Collections; 
using System.Collections.Generic; 
  
class GFG{
  
// 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'. Only this function varies
// according to the game 
static int calculateGrundy(int n) 
{ 
    if (n == 0) 
        return (0); 
          
    // A Hash Table 
    HashSet<int> Set = new HashSet<int>(); 
    
    for(int i = 0; i <= n - 1; i++) 
            Set.Add(calculateGrundy(i)); 
    
    return (calculateMex(Set)); 
}    
  
// Driver code
public static void Main(string []arg)
{
    int n = 10; 
      
    Console.Write(calculateGrundy(n)); 
}
}
  
// This code is contributed by rutvik_56

<script>
// A recursive javascript program to find Grundy
// Number for a game which is like a 
// one-pile version of Nim. Game 
// Description : 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? 
  
    // A Function to calculate Mex of all
    // the values in that set.
    function calculateMex( Set) {
        var Mex = 0;
  
        while (Set.has(Mex))
            Mex++;
  
        return (Mex);
    }
  
    // A function to Compute Grundy Number
    // of 'n'. Only this function varies
    // according to the game
    function calculateGrundy(n) {
        if (n == 0)
            return (0);
  
        // A Hash Table
        var set = new Set();
  
        for (i = 0; i <= n - 1; i++)
            set.add(calculateGrundy(i));
  
        return (calculateMex(set));
    }
  
    // Driver code
      
        var n = 10;
  
        document.write(calculateGrundy(n));
  
// This code contributed by aashish1995
</script>

Producción : 

10

La solución anterior se puede optimizar usando Programación Dinámica ya que hay subproblemas superpuestos. La implementación basada en programación dinámica se puede encontrar aquí .

Ejemplo 2 
El juego comienza con una pila de n piedras, y el jugador a mover puede tomar cualquier número positivo de piedras hasta 3 solamente. El último jugador en moverse gana. ¿Qué jugador gana el juego? Este juego es una versión de 1 pila de Nim.
Dado que si el primer jugador tiene 0 piedras, perderá inmediatamente, entonces Grundy(0) = 0
Si un jugador tiene 1 piedras, puede tomar todas las piedras y ganar. Entonces, la siguiente posición posible del juego (para el otro jugador) es (0) piedras

Por lo tanto, Grundy(1) = Mex(0) = 1 [Según la definición de Mex]
De manera similar, si un jugador tiene 2 piedras, puede tomar solo 1 piedra o puede tomar 2 piedras y ganar. Entonces, la siguiente posición posible del juego (para el otro jugador) es (1, 0) piedras respectivamente.
Por lo tanto, Grundy(2) = Mex(0, 1) = 2 [Según la definición de Mex]
De manera similar, Grundy(3) = Mex(0, 1, 2) = 3 [Según la definición de Mex]

Pero ¿qué pasa con 4 piedras? 
Si un jugador tiene 4 piedras, entonces puede tomar 1 piedra o puede tomar 2 piedras o 3 piedras, pero no puede tomar 4 piedras (ver las restricciones del juego). Entonces, la siguiente posición posible del juego (para el otro jugador) es (3, 2, 1) piedras respectivamente.
Por lo tanto, Grundy(4) = Mex (1, 2, 3) = 0 [Según la definición de Mex]
Entonces podemos definir el Número de Grundy de cualquier n >= 4 recursivamente como
Grundy(n) = Mex[Grundy (n -1), Grundy (n-2), Grundy (n-3)]

Resumimos el primer valor de Grundy de 0 a 10 en la siguiente tabla: 
 

/* A recursive C++ program to find Grundy Number for
a game which is one-pile version of Nim.
Game Description : The game starts with a pile of
n stones, and the player to move may take any
positive number of stones up to 3 only.
The last player to move wins. */
#include<bits/stdc++.h>
using namespace std;
  
// A Function to calculate Mex of all the values in
// that set.
  
// A function to Compute Grundy Number of 'n'
// Only this function varies according to the game
int calculateGrundy(int n)
{
    if (n == 0)
        return (0);
    if (n == 1)
        return (1);
    if (n == 2)
        return (2);
    if (n == 3)
        return (3);
    else
        return (n%(3+1));
}
  
// Driver program to test above functions
int main()
{
    int n = 10;
    printf("%d", calculateGrundy(n));
    return (0);
}

/* A recursive Java program to find 
Grundy Number for a game which is 
one-pile version of Nim.
Game Description : The game starts with
a pile of n stones, and the player to
move may take any positive number of stones 
up to 3 only.The last player to move wins. */
import java.util.*;
  
class GFG
{
  
      
    // A function to Compute Grundy 
    // Number of 'n' Only this function 
    // varies according to the game
    static int calculateGrundy(int n) 
    {
        if (n == 0) 
            return 0;
        if (n == 1) 
            return 1;
        if (n == 2) 
            return 2;
        if (n == 3)
            return 3;
        else
            return (n%(3+1));
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int n = 10;
        System.out.printf("%d", calculateGrundy(n));
    }
} 
// This code is contributed by rahulnamdevrn27

# A recursive Python3 program to find Grundy Number 
# for a game which is one-pile version of Nim. 
# Game Description : The game starts with a pile 
# of n stones, and the player to move may take 
# any positive number of stones up to 3 only. 
# The last player to move wins.
  
  
   
# A function to Compute Grundy Number of 'n' 
# Only this function varies according to the game 
def calculateGrundy(n): 
  
    if 0 <= n <= 3:
        return n
      
    else:
        return (n%(3+1));
        
     
   
# Driver program to test above functions 
if __name__ == "__main__": 
   
    n = 10 
    print(calculateGrundy(n)) 
      
# This code is contributed by rahulnamdevrn27

/* A recursive Java program to find Grundy Number 
for a game which is one-pile version of Nim. 
Game Description : The game starts with a pile of 
n stones, and the player to move may take any 
positive number of stones up to 3 only.The last 
player to move wins. */
using System; 
using System.Collections.Generic;
  
class GFG 
{ 
  
      
    // A function to Compute Grundy Number of 
    // 'n' Only this function varies according 
    // to the game 
    static int calculateGrundy(int n) 
    { 
        if (n == 0) 
            return 0;
        if (n == 1) 
            return 1;
        if (n == 2) 
            return 2;
        if (n == 3)
            return 3;
        else
            return (n%(3+1));
          
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
        int n = 10; 
        Console.Write(calculateGrundy(n)); 
    } 
} 
// This code is contributed by rahulnamdevrn27

<script>
  
/* A recursive Javascript program to find
Grundy Number for a game which is
one-pile version of Nim.
Game Description : The game starts with
a pile of n stones, and the player to
move may take any positive number of stones
up to 3 only.The last player to move wins. */
  
// A function to Compute Grundy
// Number of 'n' Only this function
// varies according to the game
function calculateGrundy(n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    if (n == 3)
        return 3;
    else
        return (n % (3 + 1));
}
  
// Driver code
let n = 10;
  
document.write(calculateGrundy(n));
  
// This code is contributed by rag2127
  
</script>

Producción : 

2

La solución general para el código anterior cuando se nos permite recoger hasta k piedras se puede encontrar aquí .

Ejemplo 3 
El juego comienza con un número-‘n’ y el jugador que se mueve divide el número-‘n’ entre 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?

Resumimos el primer valor de Grundy de 0 a 10 en la siguiente tabla: 

Piensa en cómo generamos esta tabla.

/* A recursive C++ program to find Grundy Number for
   a game.
 Game Description:  The game starts with a number- 'n'
 and the player to move divides the number- 'n' with 2, 3
 or 6 and then takes the floor. If the integer becomes 0,
 it is removed. The last player to move wins.  */
#include<bits/stdc++.h>
using namespace std;
  
// 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'
// Only this function varies according to the game
int calculateGrundy (int n)
{
    if (n == 0)
        return (0);
  
    unordered_set<int> Set; // A Hash Table
  
    Set.insert(calculateGrundy(n/2));
    Set.insert(calculateGrundy(n/3));
    Set.insert(calculateGrundy(n/6));
  
    return (calculateMex(Set));
}
  
// Driver program to test above functions
int main()
{
    int n = 10;
    printf("%d", calculateGrundy (n));
    return (0);
}

/* A recursive Java program to find Grundy Number for
a game.
Game Description : The game starts with a number- 'n'
and the player to move divides the number- 'n' with 2, 3
or 6 and then takes the floor. If the integer becomes 0,
it is removed. The last player to move wins. */
import java.util.*;
  
class GFG 
{
  
    // 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'
    // Only this function varies according to the game
    static int calculateGrundy(int n) 
    {
        if (n == 0) 
        {
            return (0);
        }
  
        HashSet<Integer> Set = new HashSet<Integer>(); // A Hash Table
  
        Set.add(calculateGrundy(n / 2));
        Set.add(calculateGrundy(n / 3));
        Set.add(calculateGrundy(n / 6));
  
        return (calculateMex(Set));
    }
  
    // Driver code
    public static void main(String[] args) 
    {
        int n = 10;
        System.out.printf("%d", calculateGrundy(n));
    }
} 
  
// This code is contributed by PrinciRaj1992

# A recursive Python3 program to 
# find Grundy Number for a game. 
# Game Description : The game starts with a number- 'n' 
# and the player to move divides the number- 'n' with 2, 3 
# or 6 and then take the floor. If the integer becomes 0, 
# it is removed. The last player to move wins.
  
# 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' 
# Only this function varies according to the game 
def calculateGrundy(n): 
   
    if n == 0:
        return 0 
  
    Set = set() # A Hash Table 
  
    Set.add(calculateGrundy(n // 2)) 
    Set.add(calculateGrundy(n // 3)) 
    Set.add(calculateGrundy(n // 6)) 
  
    return (calculateMex(Set)) 
   
# Driver program to test above functions 
if __name__ == "__main__": 
   
    n = 10 
    print(calculateGrundy(n)) 
      
# This code is contributed by Rituraj Jain

/* A recursive C# program to find Grundy Number for 
a game. 
Game Description: The game starts with a number- 'n' 
and the player to move divides the number- 'n' with 2, 3 
or 6 and then takes the floor. If the integer becomes 0, 
it is removed. The last player to move wins. */
using System;
using System.Collections.Generic;
  
class GFG 
{ 
  
    // 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' 
    // Only this function varies according to the game 
    static int calculateGrundy(int n) 
    { 
        if (n == 0) 
        { 
            return (0); 
        } 
  
        // A Hash Table 
        HashSet<int> Set = new HashSet<int>(); 
  
        Set.Add(calculateGrundy(n / 2)); 
        Set.Add(calculateGrundy(n / 3)); 
        Set.Add(calculateGrundy(n / 6)); 
  
        return (calculateMex(Set)); 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        int n = 10; 
        Console.WriteLine(calculateGrundy(n)); 
    } 
} 
  
// This code is contributed by PrinciRaj1992

<script>
  
/* A recursive Javascript program to find 
Grundy Number for a game.
Game Description : The game starts with a 
number- 'n' and the player to move divides 
the number- 'n' with 2, 3 or 6 and then
takes the floor. If the integer becomes 0,
it is removed. The last player to move wins. */
  
// 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'. Only this function varies
// according to the game
function calculateGrundy(n)
{
    if (n == 0)
    {
        return (0);
    }
      
    // A Hash Table
    let set = new Set(); 
  
    set.add(calculateGrundy(Math.floor(n / 2)));
    set.add(calculateGrundy(Math.floor(n / 3)));
    set.add(calculateGrundy(Math.floor(n / 6)));
  
    return(calculateMex(set));
}
  
// Driver code
let n = 10;
  
document.write(calculateGrundy(n));
  
// This code is contributed by avanitrachhadiya2155
  
</script>

Producción : 

0

La solución anterior se puede optimizar usando Programación Dinámica ya que hay subproblemas superpuestos. La implementación basada en programación dinámica se puede encontrar aquí .

Referencias-  
https://en.wikipedia.org/wiki/Mex_(mathematics)  
https://en.wikipedia.org/wiki/Number
En la próxima publicación, discutiremos soluciones para Imparcial Games usando Grundy Numbers o Numbers.
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.