🤔 Вы когда-нибудь слышали о теории игр?
Что, если я скажу вам, что вы можете предсказать победителя игры еще до начала игры? Да, вы можете сделать это с помощью теории игры. Если вы новичок в соревновательном программировании, теория игр может быть для вас чем-то новым. Однако на большинстве хакатонов часто встречаются проблемы с программированием по теории игр.
Вступление
Используя теорию игр, вы можете предсказать победителей, но только в комбинаторных играх. Комбинаторные игры - это игры, в которые будут играть два человека, и в этих играх не будет рандомизации (например, подбрасывание монет). Кроме того, эти игры всегда заканчиваются в состоянии победы или поражения.
Например, такие игры, как Chess, Tic Tac Toe и Game of Nim, подпадают под категорию комбинаторных игр.
Теория игр - довольно важная тема в математике. Поэтому разобраться во всех методах теории игр (конечно, для нас, программистов) практически невозможно. Вот почему я выбрал теорию игр в соревновательном программировании. С помощью некоторых математических теорем мы можем решать такие игры, как «Game of Nim». Однако решить такие игры, как шахматы или крестики-нолики, немного сложно. В этой статье мы обсудим, как решить эту Игру Нима, используя Теорию Игр.
Game of Nim - это комбинаторная игра, а также беспристрастная игра. Что такое беспристрастные игры?
В основном мы можем разделить эти игры на две категории:
Игра Нима?
«Игра Нима» проста. Есть n стопок монет, (между двумя игроками) каждый игрок может взять хотя бы одну монету из любой стопки. Побеждает тот, кто сделает последний ход. Оба игрока будут играть оптимально. (играю на победу)
Пример: -
Есть два игрока, Джон и Кевин. Они решили сыграть в эту «Игру Нима». Таким образом, они построили 3 стопки монет, каждая из которых содержит монеты соответственно 3, 4 и 5. Один игрок должен взять 1, 2 или 3 монеты в каждом раунде. Если Джон сделает первый ход, и оба игрока сыграют оптимально. Это один из возможных сценариев.
Кевин берет последнюю монету. Таким образом, Кевин выигрывает игру.
Как предсказать победителя?
Теория игр подразумевает, что победитель этой игры наверняка будет зависеть от двух факторов.
01. Кто запускает игру.
02. Количество монет в каждой стопке. (не общее количество монет во всех стопках)
Это не означает, что человек, который начинает игру, будет все время выигрывать, может быть состояние, которое Кевин проиграет в нашем примере. ( изменением количества монет)
Сделаем жизнь проще. Предположим, что в нашем примере есть только одна стопка. В этой стопке 5 монет. Два игрока будут по очереди, и один игрок может взять 1,2 или 3 монеты. Тогда победителем будет,
Если оба игрока играют оптимально, то игрок, начинающий первым, гарантированно выиграет, если значение grundy в начале игры не равно нулю. В противном случае, если грандиозное значение равно нулю, игрок, начинающий первым, однозначно проиграет.
Ага, закидываю сюда много нового. Так что держитесь крепче и наденьте очки для компьютерных фанатов. 🤓
Что такое Grundy Value?
Мы хотим вычислить грандиозное значение в начале нашей игры. Grundy Value - это MEX значение всех возможных состояний, в которые вы можете перейти в начале. Эти Grundy Values определяют каждое игровое состояние. Следовательно, если общее количество монет равно 5,
Grundy (5) = MEX (возможные состояния, в которые можно перейти)
MEX (минимальный исключающий)
MEX или иным образом Минимальный исключающий элемент набора - это наименьшее неотрицательное число, которое отсутствует в наборе.
Пример: - если S = {0, 1, 3, 8, 12}, то MEX (S) = 2
Теперь вы можете подумать, что Гранди (5) для приведенного выше примера,
Гранди (5) = MEX ({4,3,2}) → Гранди (5) = 0
Боюсь, это неверно. Здесь мы говорим о возможных состояниях игры. В этой теореме возможные состояния игры определяются с помощью чисел Гранди. (Я уже говорил тебе раньше)
Ex:-
- состояние получения одной монеты - Гранди (4)
- состояние получения двух монет - Гранди (3)
- состояние взятия трех монет - Гранди (2)
Следовательно,
Гранди (5) = MEX ({Гранди (4), Гранди (3), Гранди (2)})
Теперь вы можете ясно увидеть здесь рекурсивную функцию. Неудивительно, что комбинаторная теория игр и программирование идеально подходят друг другу😀. Давайте посчитаем все значения Гранди для нашего примера.
Из приведенной выше таблицы вычислим Гранди (5),
Гранди (5) = MEX ({Гранди (4), Гранди (3), Гранди (2)})
Гранди (5) = MEX ({0,3,2}) → Гранди (5) = 1
Гранди (5) равно ненулевому значению. Следовательно, если оба игрока играют оптимально, игрок, начавший первым. Возникает вопрос, как решить, если стопок монет больше одной? Вот тут-то и пригодится Теорема Спрага - Гранди.
Теорема Спрага-Гранди
Нам нужно вычислить значение XOR для набора, которое может быть сгенерировано путем применения грубого значения для каждой стопки . Если значение XOR равно ненулевое, игрок, начавший первым, выиграет . Если значение XOR равно ноль, игрок, начавший первым, проиграет .
Обратите внимание, мы предполагаем, что оба игрока будут играть оптимально. Применим теорему Спрага-Гранди к нашему примеру с игрой в Ним.
В начале в каждой стопке по 3, 4 и 5 монет соответственно. Теперь, если бы мы вычислили значение XOR,
Значение XOR = XOR (Гранди (3), Гранди (4), Гранди (5))
Значение XOR = XOR (3, 0, 1) → Значение XOR = 2
Значение XOR - это неотрицательное число. Следовательно, мы можем предположить, что первый игрок выиграет. Наш пример тоже это доказывает.
Поздравляю! 👏 вы изучили комбинаторную теорию игр. Хотя я не сказал вам, как это реализовать с помощью языка программирования. Попробуйте сделать это самостоятельно. Вот проблема программирования, которую я создал с помощью теории игр для одного из наших университетских хакатонов.
Удачного кодирования! 😉
Ресурсы
- Комбинаторная теория игр Гранди чисел I, Гаурав Сен
- Комбинаторная теория игр | Набор 4 (Теорема Спрага - Гранди) от Рашит Белвариар
Если вы узнали что-то новое, не забудьте также поделиться этим постом.
