Теория игр

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

Беспристрастные игры

Игра называется беспристрастной, если выполнены следующие условия:

P- и N-позиции

Позиция называется P-позицией (позицией проигрыша), если игрок, который должен сделать ход, проигрывает при правильной игре соперника. Позиция называется N-позицией (позицией выигрыша), если игрок, который должен сделать ход, выигрывает при правильной игре.

Теорема. В конечной беспристрастной игре каждая позиция является P-позицией или N-позицией, но не обеими сразу. Позиция $x$ является P-позицией тогда и только тогда, когда все ходы из $x$ ведут в N-позиции. Позиция $x$ является N-позицией тогда и только тогда, когда из $x$ есть ход в P-позицию.

Доказательство проводится индукцией по максимальной длине игры из позиции. Если ходов нет, позиция является P-позицией: игрок, который должен ходить, проигрывает. Если из $x$ есть ход в P-позицию $y$, то игрок, который ходит в $x$, переходит в $y$, и соперник проигрывает, значит, $x$ является N-позицией. Если все ходы из $x$ ведут в N-позиции, то после любого хода игрока, который ходит в $x$, соперник оказывается в выигрышной позиции и выигрывает, значит, $x$ является P-позицией.

Поэтому P- и N-позиции можно найти по определению, начиная с позиций, из которых нет ходов: позиция является P, если все её ходы ведут в N, и N, если есть ход в P. Если позиций $K$, а из каждой позиции выходит не больше $M$ ходов, то такой перебор выполняется за $O(K \cdot M)$ операций. Программа на Python делает то же самое рекурсией с мемоизацией.

Игра «ним»

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

Побитовое исключающее ИЛИ (XOR) чисел $a$ и $b$ обозначается $a \oplus b$: в его двоичной записи стоит $1$ там, где ровно одно из чисел $a$, $b$ содержит $1$.

Теорема Бутона. Позиция игры «ним» с кучами $a_1, \dots, a_k$ является P-позицией тогда и только тогда, когда $a_1 \oplus a_2 \oplus \dots \oplus a_k = 0$.

Доказательство проводится индукцией по общему числу камней. Пусть $s = a_1 \oplus \dots \oplus a_k$. Если $s = 0$, то любой ход заменяет некоторую кучу $a_i$ на меньшую $a_i'$, и новое значение XOR равно $a_i \oplus a_i' \neq 0$. Все ходы ведут в позиции с ненулевым XOR, которые по предположению индукции являются N-позициями, значит, позиция является P-позицией. Если $s \neq 0$, пусть $p$ — старший ненулевой бит числа $s$. В этом бите XOR равен единице, значит, найдётся куча $a_i$ с единицей в бите $p$. Тогда $a_i \oplus s < a_i$, и ход, уменьшающий кучу $a_i$ до $a_i \oplus s$, даёт XOR, равный нулю. Эта позиция по предположению индукции является P-позицией, значит, исходная позиция является N-позицией.

Из доказательства следует выигрышная стратегия: в N-позиции нужно найти кучу $a_i$, для которой $a_i \oplus s < a_i$, и уменьшить её до $a_i \oplus s$. Например, в позиции из трёх куч $3$, $4$, $5$ значение $s = 3 \oplus 4 \oplus 5 = 2$, и подходит первая куча: $3 \oplus 2 = 1 < 3$. Ход «взять $2$ камня из первой кучи» даёт позицию $(1, 4, 5)$ с XOR, равным нулю.

Идея теоремы Шпрага — Гранди

Для любой беспристрастной игры каждой позиции $x$ можно сопоставить неотрицательное целое число $g(x)$, которое называют значением Гранди. Оно вычисляется по значениям вариантов хода как наименьшее неотрицательное число, которого среди них нет (mex). Позиция является P-позицией тогда и только тогда, когда $g(x) = 0$. Для игры «ним» значение Гранди кучи равно её размеру.

Главная идея теоремы Шпрага — Гранди состоит в следующем. Сумма нескольких независимых игр, в которой игрок в каждом ходе выбирает одну из игр и делает в ней ход, тоже является беспристрастной игрой. Её значение Гранди равно XOR значений слагаемых. Поэтому каждую игру можно заменить кучей «нима» подходящего размера, а теорема Бутона оказывается частным случаем. Подробнее о функции Гранди, о mex и о доказательстве — в уроке Игры. Функция Гранди.

Программа на Python перебирает позиции с мемоизацией, находит выигрышный ход по XOR и проверяет теорему Бутона на всех позициях, где три кучи имеют размер до $6$. Программа на C++ выполняет ту же проверку для трёх куч размером до $6$ и выводит число несовпадений, которое должно быть равно нулю.

Реализация на Python

# Беспристрастная игра «Ним»: P- и N-позиции перебором с мемоизацией; теорема Бутона (XOR размеров куч).
from functools import lru_cache
from itertools import product


def moves(heaps):
    """Позиции, в которые можно перейти одним ходом: из одной кучи взять любое положительное число камней."""
    result = []
    for i, size in enumerate(heaps):
        for taken in range(1, size + 1):
            result.append(heaps[:i] + (size - taken,) + heaps[i + 1:])
    return result


@lru_cache(maxsize=None)
def is_p_position(heaps):
    """True, если позиция P: игрок, который должен ходить, проигрывает, то есть все ходы ведут в N-позиции."""
    return all(not is_p_position(nxt) for nxt in moves(heaps))


def xor_of(heaps):
    value = 0
    for size in heaps:
        value ^= size
    return value


def winning_move(heaps):
    """Ход в P-позицию по теореме Бутона: (номер кучи, новый размер) или None, если позиция уже P."""
    total = xor_of(heaps)
    if total == 0:
        return None
    for i, size in enumerate(heaps):
        if (size ^ total) < size:
            return i, size ^ total
    return None


def main():
    print([h for h in product(range(5), repeat=2) if is_p_position(h)])  # [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
    print(is_p_position((1, 2, 3)), is_p_position((1, 2, 4)))  # True False
    print(winning_move((3, 4, 5)))  # (0, 1): после хода куча 3 становится 1, XOR равен 0
    # Теорема Бутона: позиция P тогда и только тогда, когда XOR размеров куч равен 0
    print(all(is_p_position(h) == (xor_of(h) == 0) for h in product(range(7), repeat=3)))  # True


if __name__ == "__main__":
    main()

Реализация на C++

// Ним: позиция P тогда и только тогда, когда XOR размеров куч равен 0 (теорема Бутона).
// Проверка: перебор с мемоизацией сравнивается с XOR для всех позиций из трёх куч размером до 6.
#include <iostream>
#include <map>
#include <vector>

using Heaps = std::vector<int>;

// true, если позиция heaps выигрышная для игрока, который ходит (N-позиция).
// Выигрышна, если есть ход в P-позицию, то есть в позицию, где противник проигрывает.
bool is_n_position(const Heaps& heaps, std::map<Heaps, bool>& memo) {
  auto found = memo.find(heaps);
  if (found != memo.end()) return found->second;
  bool wins = false;
  for (std::size_t i = 0; i < heaps.size() && !wins; ++i) {
    for (int taken = 1; taken <= heaps[i] && !wins; ++taken) {
      Heaps next = heaps;
      next[i] -= taken;
      wins = !is_n_position(next, memo);
    }
  }
  memo[heaps] = wins;
  return wins;
}

int xor_of(const Heaps& heaps) {
  int value = 0;
  for (int size : heaps) value ^= size;
  return value;
}

int main() {
  std::map<Heaps, bool> memo;
  int mismatches = 0;
  for (int a = 0; a <= 6; ++a) {
    for (int b = 0; b <= 6; ++b) {
      for (int c = 0; c <= 6; ++c) {
        bool is_p = !is_n_position({a, b, c}, memo);
        if (is_p != (xor_of({a, b, c}) == 0)) ++mismatches;
      }
    }
  }
  std::cout << "mismatches: " << mismatches << '\n';  // mismatches: 0
  std::cout << "(1, 2, 3): " << (is_n_position({1, 2, 3}, memo) ? "N" : "P") << '\n';  // P
  std::cout << "(1, 2, 4): " << (is_n_position({1, 2, 4}, memo) ? "N" : "P") << '\n';  // N
  return 0;
}