Рубрики

Комбинаторная теория игр | Комплект 2 (Игра Нима)

Настоятельно рекомендуем ссылаться на приведенную ниже статью в качестве предпосылки этого.

Комбинаторная теория игр | Комплект 1 (Введение)

В этом посте обсуждается игра Нима. Игра Нима описывается следующими правилами:

« Приведено количество куч, в которых каждая куча содержит несколько камней / монет. В каждом ходу игрок может выбрать только одну кучу и удалить любое количество камней (хотя бы один) из этой кучи. Считается, что игрок, который не может двигаться, проигрывает (то есть тот, кто взял последний камень, является победителем). »

Например, предположим, что есть два игрока — A и B , и изначально есть три стопки монет, изначально в каждой по 3, 4, 5 монет, как показано ниже. Мы предполагаем, что первый ход сделан A. Смотрите рисунок ниже для четкого понимания всей игры.

A Выиграл матч (Примечание: A сделал первый ход)

Так был ли у А сильный опыт в этой игре? или он / она имел некоторое преимущество над B , начав сначала?

Давайте теперь поиграем снова, с той же конфигурацией свай, что и выше, но на этот раз B сначала стартует вместо A.

B Выиграл матч (Примечание: B сделал первый ход)

Из приведенного выше рисунка должно быть ясно, что игра зависит от одного важного фактора — кто запускает игру первым?

Так выигрывает ли игрок, который стартует первым?
Давайте снова поиграем в игру, начиная с А , и на этот раз с другой начальной конфигурацией свай. Сваи изначально имеют 1, 4, 5 монет.

Будет ли снова выиграть , как он начал первый? Покажи нам.

А сделал первый ход, но проиграл.

Итак, результат понятен. А потерял. Но как? Мы знаем, что эта игра сильно зависит от того, какой игрок начинает первым. Таким образом, должен быть еще один фактор, который доминирует в результате этой простой, но интересной игры. Этот фактор является начальной конфигурацией куч / куч. На этот раз начальная конфигурация отличалась от предыдущей.

Итак, мы можем сделать вывод, что эта игра зависит от двух факторов:

  1. Игрок, который начинает первым.
  2. Начальная конфигурация свай / куч.

Фактически, мы можем предсказать победителя игры, даже не играя в игру!

Nim-Sum: совокупное значение XOR количества монет / камней в каждой куче / куче в любой точке игры называется Nim-Sum в этой точке.

«Если и А, и В играют оптимально (т. Е. Они не совершают ошибок), то игрок, стартовавший первым, гарантированно выиграет, если Ним-сумма в начале игры отлична от нуля. В противном случае, если Nim-Sum оценивается в ноль, то игрок A определенно проиграет ».

Для доказательства приведенной выше теоремы см. Https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula.

Оптимальная стратегия:

    Пара выводов о побитовом XOR, необходимом для понимания Оптимальной стратегии:

  • Если сумма XOR чисел 'n' уже равна нулю, то невозможно сделать сумму XOR равной нулю путем однократного уменьшения числа.
  • Если сумма XOR чисел 'n' не равна нулю, то существует по крайней мере один подход, при котором при уменьшении числа сумма XOR равна нулю.

Первоначально могли существовать два случая.

Случай 1: Начальная сумма Нима равна нулю
Как мы знаем, в этом случае, если сыграно оптимально, B выигрывает, а это значит, что B всегда предпочитает иметь Nim сумму ноль для хода A.
Таким образом, поскольку сумма Nim изначально равна нулю, любое количество элементов A, удаляющих новую сумму Nim, будет ненулевым (как упомянуто выше). Кроме того, так как B предпочел бы Nim сумму нуля за ход A , он затем сделал бы ход, чтобы снова сделать Nim Sum нулем (что всегда возможно, как упомянуто выше).
Игра будет продолжаться до тех пор, пока в каждой куче есть предметы, и в каждом из их соответствующих ходов A сделает сумму Nim ненулевой, а B снова сделает ее равной нулю, и в конечном итоге не останется никаких элементов, а B будет одним выбрать последний выигрывает игру.

Из вышеприведенного объяснения очевидно, что оптимальной стратегией для каждого игрока является доведение суммы Ним для своего оппонента до нуля в каждом их ходе, что будет невозможно, если оно уже равно нулю.

Случай 2: Начальная сумма Нима не равна нулю
Теперь, следуя оптимальному подходу А, теперь сумма Нима будет равна нулю (что возможно, поскольку начальная сумма Нима не равна нулю, как упоминалось выше). Теперь, в свою очередь B , поскольку сумма nim уже равна нулю, какое бы число B ни выбрало, сумма nim будет ненулевой, и A может выбрать число, чтобы снова сделать сумму nim нулевой. Это будет продолжаться до тех пор, пока в любой куче есть предметы.
И А будет тот, кто выберет последний пункт.

Итак, как обсуждалось в вышеупомянутых случаях, теперь должно быть очевидно, что Оптимальная стратегия для любого игрока состоит в том, чтобы сделать нулевую сумму нулевой, если она не равна нулю, и если она уже равна нулю, то, что бы ни делал игрок сейчас, это можно отменить ,

Применим приведенную выше теорему в играх, сыгранных выше В первой игре A начался первым, и Nim-Sum в начале игры было 3 XOR 4 XOR 5 = 2, что является ненулевым значением, и, следовательно, A выиграл. Принимая во внимание, что во втором игровом процессе, когда начальная конфигурация куч была 1, 4 и 5, и A начинался первым, тогда A суждено было проиграть, так как Nim-Sum в начале игры был 1 XOR 4 XOR 5 = 0

Реализация:

В программе ниже мы играем в Nim-Game между компьютером и человеком (пользователь)
В приведенной ниже программе используются две функции
knowWinnerBeforePlaying ():: сообщает результат перед воспроизведением.
playGame (): играет в полную версию и, наконец, объявляет победителя. Функция playGame () не принимает ввод от человека (пользователя), вместо этого она использует функцию rand () для случайного подбора кучи и случайного удаления любого количества камней из выбранной кучи.

Приведенную ниже программу можно изменить, чтобы получить ввод от пользователя, удалив функцию rand () и вставив функции cin или scanf ().

/ * AC программа для реализации Game of Nim. Программа

   предполагает, что оба игрока играют оптимально * /

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

  
#define COMPUTER 1
#define HUMAN 2

  
/ * Структура для хранения двух параметров хода

  

 Ход имеет два параметра:

  1) pile_index = Индекс кучи, из которой камень

                    будет удален

  2) stone_removed = Количество камней, удаленных из

                        куча проиндексирована = pile_index * /

struct move

{

    int pile_index;

    int stones_removed;

};

  
/ *

 piles [] -> Массив с начальным количеством камней / монет

            в каждой куче до начала игры.

 n -> Количество свай

  

 Сваи [] имеют индексирование на основе 0 * /

  
// Функция AC для вывода текущего игрового состояния.

void showPiles (int piles[], int n)

{

    int i;

    printf ("Current Game Status -> ");

    for (i=0; i<n; i++)

        printf ("%d ", piles[i]);

    printf("\n");

    return;

}

  
// AC функция, которая возвращает True, если игра закончилась и
// Ложь, если игра еще не закончена

bool gameOver(int piles[], int n)

{

    int i;

    for (i=0; i<n; i++)

        if (piles[i]!=0)

            return (false);

  

    return (true);

}

  
// Функция AC для объявления победителя игры

void declareWinner(int whoseTurn)

{

    if (whoseTurn == COMPUTER)

        printf ("\nHUMAN won\n\n");

    else

        printf("\nCOMPUTER won\n\n");

    return;

}

  
// Функция AC для вычисления Nim-Sum в любой точке
// игры.

int calculateNimSum(int piles[], int n)

{

    int i, nimsum = piles[0];

    for (i=1; i<n; i++)

        nimsum = nimsum ^ piles[i];

    return(nimsum);

}

  
// AC функция, чтобы делать ходы игры Nim

void makeMove(int piles[], int n, struct move * moves)

{

    int i, nim_sum = calculateNimSum(piles, n);

  

    // Игрок с текущим ходом выигрывает

    // позиция. Поэтому он / она / она играет оптимально и пытается сделать

    // Nim-Sum как 0

    if (nim_sum != 0)

    {

        for (i=0; i<n; i++)

        {

            // Если это не незаконный ход

            // затем сделать этот шаг.

            if ((piles[i] ^ nim_sum) < piles[i])

            {

                (*moves).pile_index = i;

                (*moves).stones_removed =

                                 piles[i]-(piles[i]^nim_sum);

                piles[i] = (piles[i] ^ nim_sum);

                break;

            }

        }

    }

  

    // Игрок с текущим ходом проигрывает

    // позиция, поэтому он / она / она может ждать только противника

    // сделать ошибку (чего не происходит в этой программе

    // так как оба игрока играют оптимально). Он случайно

    // выбираем непустую кучу и случайным образом удаляем несколько камней

    // от него. Если противник не ошибся, то это

    // не имеет значения, какую кучу выберет этот игрок, так как он

    // суждено проиграть эту игру.

  

    // Если вы хотите ввести себя, то удалите rand ()

    // функционирует и модифицирует код для ввода данных.

    // Но помните, вы все равно не сможете изменить свой

    // судьба / предсказание.

    else

    {

        // Создать массив для хранения индексов непустых куч

        int non_zero_indices[n], count;

  

        for (i=0, count=0; i<n; i++)

            if (piles[i] > 0)

                non_zero_indices [count++] = i;

  

        (*moves).pile_index = (rand() % (count));

        (*moves).stones_removed =

                 1 + (rand() % (piles[(*moves).pile_index]));

        piles[(*moves).pile_index] =

         piles[(*moves).pile_index] - (*moves).stones_removed;

  

        if (piles[(*moves).pile_index] < 0)

            piles[(*moves).pile_index]=0;

    }

    return;

}

  
// Функция AC для игры в игру Нима

void playGame(int piles[], int n, int whoseTurn)

{

    printf("\nGAME STARTS\n\n");

    struct move moves;

  

    while (gameOver (piles, n) == false)

    {

        showPiles(piles, n);

  

        makeMove(piles, n, &moves);

  

        if (whoseTurn == COMPUTER)

        {

            printf("COMPUTER removes %d stones from pile "

                   "at index %d\n", moves.stones_removed,

                   moves.pile_index);

            whoseTurn = HUMAN;

        }

        else

        {

            printf("HUMAN removes %d stones from pile at "

                   "index %d\n", moves.stones_removed,

                   moves.pile_index);

            whoseTurn = COMPUTER;

        }

    }

  

    showPiles(piles, n);

    declareWinner(whoseTurn);

    return;

}

  

void knowWinnerBeforePlaying(int piles[], int n,

                             int whoseTurn)

{

    printf("Prediction before playing the game -> ");

  

    if (calculateNimSum(piles, n) !=0)

    {

        if (whoseTurn == COMPUTER)

            printf("COMPUTER will win\n");

        else

            printf("HUMAN will win\n");

    }

    else

    {

        if (whoseTurn == COMPUTER)

            printf("HUMAN will win\n");

        else

            printf("COMPUTER will win\n");

    }

  

    return;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Тестовый пример 1

    int piles[] = {3, 4, 5};

    int n = sizeof(piles)/sizeof(piles[0]);

  

    // Мы предскажем результаты перед игрой

    // КОМПЬЮТЕР запускается первым

    knowWinnerBeforePlaying(piles, n, COMPUTER);

  

    // Давайте поиграем в игру с компьютером, начинающимся первым

    // и проверяем, был ли наш прогноз верным или нет

    playGame(piles, n, COMPUTER);

  

    / *

    Тестовый пример 2

    int piles [] = {3, 4, 7};

    int n = sizeof (сваи) / sizeof (сваи [0]);

  

    // Мы предскажем результаты перед игрой

    // ЧЕЛОВЕК (Ты) начинается первым

    knowWinnerBeforePlaying (сваи, п, компьютер);

  

    // Давайте поиграем в игру с компьютером, начинающимся первым

    // и проверяем, был ли наш прогноз верным или нет

    playGame (сваи, н, ЧЕЛОВЕК); * /

  

    return(0);

}

Вывод: может отличаться на разных трассах, так как случайные числа используются для определения следующего хода (для проигравшего игрока).

Prediction before playing the game -> COMPUTER will win

GAME STARTS

Current Game Status -> 3 4 5 
COMPUTER removes 2 stones from pile at index 0
Current Game Status -> 1 4 5 
HUMAN removes 3 stones from pile at index 1
Current Game Status -> 1 1 5 
COMPUTER removes 5 stones from pile at index 2
Current Game Status -> 1 1 0 
HUMAN removes 1 stones from pile at index 1
Current Game Status -> 1 0 0 
COMPUTER removes 1 stones from pile at index 0
Current Game Status -> 0 0 0 

COMPUTER won

Ссылки :
https://en.wikipedia.org/wiki/Nim

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Комбинаторная теория игр | Комплект 2 (Игра Нима)

0.00 (0%) 0 votes