Игры. Функция Гранди
Функция Гранди
Урок посвящён функции Гранди, с помощью которой решаются игры, составленные из нескольких независимых частей. Общие понятия теории беспристрастных игр (P- и N-позиции, игра «ним», теорема Бутона) изложены в уроке Теория игр; здесь они используются без повторного вывода.
Минимальное отсутствующее число (mex)
Для конечного множества $M$ неотрицательных целых чисел величина $\operatorname{mex} M$ (от англ. minimum excludant) — это наименьшее неотрицательное целое число, которого нет в $M$:
$$\operatorname{mex} M = \min\{\, k \in \mathbb{Z}_{\ge 0} : k \notin M \,\}.$$
Например, $\operatorname{mex} \varnothing = 0$, $\operatorname{mex} \{0, 1, 3\} = 2$, $\operatorname{mex} \{1, 2\} = 0$. Если в множестве $M$ ровно $m$ элементов, то $\operatorname{mex} M \le m$, поэтому для вычисления достаточно проверить числа от $0$ до $m$.
Функция Гранди
Пусть игра задана позициями: из позиции $x$ ведут ходы в её варианты — позиции из множества $\operatorname{Opt}(x)$. Функция Гранди $g$ задаётся рекурсивно:
$$g(x) = \operatorname{mex} \{\, g(y) : y \in \operatorname{Opt}(x) \,\}.$$
Для позиции без ходов $\operatorname{Opt}(x) = \varnothing$ и $g(x) = 0$. Определение корректно, так как игра конечна: значения вариантов вычисляются раньше значения самой позиции (индукция по длине игры).
Теорема. Для одной беспристрастной игры $g(x) = 0$ тогда и только тогда, когда позиция $x$ является P-позицией.
Доказательство проводится индукцией по длине игры: для всех вариантов $y$ утверждение считается уже доказанным. Если $g(x) = 0$, то число $0$ не входит в множество $\{g(y)\}$, значит, ни один вариант не имеет значения $0$. По предположению индукции ни один вариант не является P-позицией, поэтому $x$ является P-позицией. Если $g(x) \neq 0$, то $0$ входит в множество $\{g(y)\}$, иначе mex был бы равен $0$. Значит, некоторый вариант $y$ имеет $g(y) = 0$. По предположению индукции $y$ является P-позицией, и $x$ является N-позицией.
Пример. Рассмотрим игру «вычитание» с множеством ходов $S = \{1, 3, 4\}$: из кучи в $n$ камней за ход можно взять $s$ камней, где $s \in S$ и $s \le n$. Проигрывает тот, кто не может сделать ход. Вариантами кучи в $n$ камней являются кучи $n - s$ для допустимых $s$. Значения Гранди начинаются так (при $n = 0$ ходов нет):
$$g(0) = 0, \quad g(1) = \operatorname{mex}\{g(0)\} = 1, \quad g(2) = \operatorname{mex}\{g(1)\} = 0.$$
Значение $g(4)$ определяется вариантами $g(3)$, $g(1)$ и $g(0)$:
$$g(4) = \operatorname{mex}\{g(3), g(1), g(0)\} = \operatorname{mex}\{1, 1, 0\} = 2.$$
Продолжая вычисления, получаем:
$$g(0), g(1), \dots, g(10) = 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1.$$
Позиции с $g = 0$, то есть кучи в $0$, $2$, $7$ и $9$ камней, являются P-позициями.
Сумма игр
Сумма игр $G_1 + \dots + G_k$ — это игра, позиция которой состоит из позиций $x_1, \dots, x_k$ отдельных игр. Ход заключается в том, что игрок выбирает одну из компонент и делает в ней допустимый ход, а остальные компоненты не меняются. Игра заканчивается, когда ходов нет ни в одной компоненте. Сумма беспристрастных игр сама является беспристрастной игрой.
Теорема Шпрага — Гранди. Значение Гранди суммы равно побитовому XOR значений слагаемых:
$$g(x_1, \dots, x_k) = g(x_1) \oplus g(x_2) \oplus \dots \oplus g(x_k).$$
В частности, позиция суммы является P-позицией тогда и только тогда, когда $g(x_1) \oplus \dots \oplus g(x_k) = 0$.
Доказательство. Обозначим $a_i = g(x_i)$ и $s = a_1 \oplus \dots \oplus a_k$. Доказательство ведётся индукцией по длине игры: для вариантов суммы утверждение уже доказано, то есть их значения Гранди равны XOR значений компонент. Нужно показать, что mex множества значений Гранди вариантов суммы равен $s$. Для этого проверяются два утверждения.
1) Ни один вариант суммы не имеет значения $s$. Ход меняет одну компоненту, например $x_i$, на вариант $y$ с $g(y) = b$. Так как $a_i = \operatorname{mex}\{g(y)\}$, число $a_i$ не входит в множество значений вариантов $x_i$, поэтому $b \neq a_i$. Значение новой суммы равно $s \oplus a_i \oplus b$ и не равно $s$.
2) Каждое число $t < s$ является значением некоторого варианта суммы. Пусть $p$ — старший бит, в котором числа $s$ и $t$ различаются. Так как $t < s$, в бите $p$ число $s$ равно $1$, а $t$ равно $0$. Поскольку $s$ является XOR чисел $a_i$, найдётся число $a_i$, у которого бит $p$ равен $1$. Положим $b = a_i \oplus s \oplus t$. Числа $b$ и $a_i$ различаются в бите $p$, где у $b$ стоит $0$, и совпадают во всех более старших битах, поэтому $b < a_i$. Так как $a_i = \operatorname{mex}$, число $b$ входит в множество значений вариантов $x_i$: найдётся вариант $y$ с $g(y) = b$. Ход $x_i \to y$ даёт сумму со значением $s \oplus a_i \oplus b = t$.
Из пунктов 1) и 2) следует, что mex равен $s$, что и требовалось доказать.
Пример. Для игры «вычитание» с $S = \{1, 3, 4\}$ значения $g(4) = 2$, $g(6) = 2$ и $g(5) = 3$. Позиция $(4, 6)$ является P-позицией, так как $2 \oplus 2 = 0$. Позиция $(4, 5)$ является N-позицией, так как $2 \oplus 3 = 1 \neq 0$. Выигрышный ход в ней — взять один камень из второй кучи: получится позиция $(4, 4)$, в которой XOR значений Гранди равен нулю.
Вычисление значений функции Гранди
Для игры с множеством ходов $S$ значения $g(0), g(1), \dots, g(N)$ вычисляются в порядке возрастания $n$ по формуле
$$g(n) = \operatorname{mex} \{\, g(n - s) : s \in S,\ s \le n \,\}.$$
Для каждого $n$ нужно просмотреть не более $|S|$ вариантов, а mex найти за $O(|S|)$, используя булев массив размера $|S| + 1$. Поэтому все значения вычисляются за $O(N \cdot |S|)$ операций и с памятью $O(N)$.
Реализация на C++
// Функция Гранди игры «вычитание»: из кучи можно взять s камней, где s из множества moves.
// g(n) = mex{ g(n - s) : s из moves, s <= n }; значения для n от 0 до max_n вычисляются за O(max_n * |moves|).
#include <iostream>
#include <vector>
// mex: наименьшее неотрицательное целое число, которого нет в values.
int mex(const std::vector<int>& values) {
std::vector<bool> seen(values.size() + 1, false); // значения больше values.size() не влияют на ответ
for (int v : values) {
if (v < static_cast<int>(seen.size())) seen[v] = true;
}
int result = 0;
while (seen[result]) ++result;
return result;
}
// Значения g(0), ..., g(max_n) для игры, в которой ход состоит во взятии s камней из множества moves.
std::vector<int> grundy_values(int max_n, const std::vector<int>& moves) {
std::vector<int> g(max_n + 1, 0);
for (int n = 0; n <= max_n; ++n) {
std::vector<int> options;
for (int s : moves) {
if (s <= n) options.push_back(g[n - s]);
}
g[n] = mex(options);
}
return g;
}
int main() {
const std::vector<int> moves = {1, 3, 4};
std::vector<int> g = grundy_values(10, moves);
std::cout << "g(0..10):";
for (int value : g) std::cout << ' ' << value;
std::cout << '\n'; // g(0..10): 0 1 0 1 2 3 2 0 1 0 1
// Две независимые кучи: позиция P тогда и только тогда, когда g(a) XOR g(b) = 0
std::cout << "(4, 6): " << ((g[4] ^ g[6]) == 0 ? "P" : "N") << '\n'; // (4, 6): P
std::cout << "(4, 5): " << ((g[4] ^ g[5]) == 0 ? "P" : "N") << '\n'; // (4, 5): N
return 0;
}
Программа вычисляет $g(0), \dots, g(10)$ для игры «вычитание» с $S = \{1, 3, 4\}$ и проверяет две кучи из примера выше. Значения сверены с полным перебором выигрышных позиций на 300 случайных множествах ходов.
См. также: Теория игр — P- и N-позиции, игра «ним», теорема Бутона.