Комбинаторная теория игр | Набор 3 (Цифры Гранди / Числа и Мекс)

Опубликовано: 7 Октября, 2022

Мы представили комбинаторную теорию игр в выпуске 1 и обсудили игру Ним во втором выпуске.
Grundy Number — это число, которое определяет состояние игры. Мы можем определить любую беспристрастную игру (например, игру ним) в терминах числа Гранди.

Числа Гранди или Числа определяют, как может быть решена любая Беспристрастная Игра (не только Игра Ним), после того как мы вычислили Числа Гранди, связанные с этой игрой, используя Теорему Шпрага-Гранди.
Но прежде чем вычислять числа Гранди, нам нужно узнать о другом термине — Mex.

Что такое Мекс?
«Минимальный исключающий», также известный как «Mex», набора чисел — это наименьшее неотрицательное число, отсутствующее в наборе.

Как рассчитать числа Гранди?
Мы используем это определение: число/число Гранди равно 0 для игры, которая немедленно проиграна первым игроком, и равно Mex чисел всех возможных следующих позиций для любой другой игры.
Ниже приведены три примера игр и программ для расчета числа Гранди и Мекс для каждой из них. Вычисление чисел Гранди выполняется в основном с помощью рекурсивной функции, называемой функцией calculateGrundy(), которая использует функцию calculateMex() в качестве своей подпрограммы.

Пример 1
Игра начинается с кучи из n камней, и игрок, который ходит, может взять любое положительное количество камней. Рассчитайте числа Гранди для этой игры. Последний игрок, который ходит, выигрывает. Какой игрок выигрывает игру?
Поскольку, если у первого игрока 0 камней, он сразу же проиграет, поэтому Гранди (0) = 0.
Если у игрока 1 камень, то он может взять все камни и выиграть. Таким образом, следующая возможная позиция в игре (для другого игрока) — (0) камней.
Следовательно, Гранди (1) = Mex (0) = 1 [согласно определению Mex]
Точно так же, если у игрока 2 камня, то он может взять только 1 камень или может взять все камни и выиграть. Таким образом, следующая возможная позиция в игре (для другого игрока) — (1, 0) камней соответственно.
Следовательно, Гранди (2) = Mex (0, 1) = 2 [согласно определению Mex]
Точно так же, если у игрока «n» камней, то он может взять только 1 камень, или он может взять 2 камня…….. или он может взять все камни и выиграть. Таким образом, следующая возможная позиция в игре (для другого игрока) — (n-1, n-2,….1) камней соответственно.
Следовательно, Grundy(n) = Mex (0, 1, 2, ….n-1) = n [согласно определению Mex]

Мы суммируем первое значение Гранди от 0 до 10 в таблице ниже:


C++




/* 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);
}
Java



// 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
Python3



""" 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
C#



// 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
Javascript



<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>
Выход :
10
Приведенное выше решение можно оптимизировать с помощью динамического программирования, так как есть перекрывающиеся подзадачи. Реализацию на основе динамического программирования можно найти здесь.
Пример 2
 Игра начинается с кучи из n камней, и игрок для хода может взять любое положительное количество камней, не превышающее 3. Последний игрок, который ходит, выигрывает. Какой игрок выигрывает игру? Эта игра представляет собой версию Нима с 1 стопкой.
 Поскольку, если у первого игрока 0 камней, он сразу же проиграет, поэтому Гранди (0) = 0.
 Если у игрока 1 камень, то он может взять все камни и выиграть. Таким образом, следующая возможная позиция в игре (для другого игрока) — (0) камней.
Следовательно, Гранди (1) = Mex (0) = 1 [согласно определению Mex]
 Аналогично, если у игрока 2 камня, то он может взять только 1 камень или может взять 2 камня и выиграть. Таким образом, следующая возможная позиция в игре (для другого игрока) — (1, 0) камней соответственно.
 Следовательно, Гранди (2) = Mex (0, 1) = 2 [согласно определению Mex]
 Точно так же Гранди (3) = Mex (0, 1, 2) = 3 [согласно определению Mex]
А как же 4 камня?
 Если у игрока 4 камня, то он может взять 1 камень или может взять 2 камня или 3 камня, но не может взять 4 камня (см. ограничения игры). Таким образом, следующая возможная позиция в игре (для другого игрока) — (3, 2, 1) камней соответственно.
 Следовательно, Гранди(4) = Mex (1, 2, 3) = 0 [согласно определению Mex]
 Таким образом, мы можем определить число Гранди любого n >= 4 рекурсивно как-
 Гранди (n) = Mex[Гранди (n-1), Гранди (n-2), Гранди (n-3)]
Мы суммируем первое значение Гранди от 0 до 10 в таблице ниже:

C++



/* 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);
}
Java



/* 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

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ