Функция Гранди

Булева пометка «выигрышная или проигрышная» отвечает на вопрос про одну игру. Но если играют сразу в несколько независимых игр и ход — сходить в любой из них, знания исходов по отдельности не хватает: две проигрышные игры вместе могут оказаться выигрышными, а могут и нет.

Чтобы игры можно было складывать, позиции приписывают число — значение Гранди:

$$G(v) = \mathrm{mex}\,\{\,G(u) : u \text{ достижима из } v \text{ за один ход}\,\},$$

где $\mathrm{mex}$ множества — наименьшее неотрицательное число, которого в нём нет. У позиции без ходов множество пусто, и $\mathrm{mex}\,\varnothing = 0$.

Связь с исходом

Позиция проигрышная тогда и только тогда, когда $G = 0$.

Обе стороны следуют прямо из $\mathrm{mex}$:

• если $G(v) = 0$, то нуля среди значений соседей нет — все ходы ведут в выигрышные позиции;
• если $G(v) = k > 0$, то все числа $0, \dots, k-1$ среди соседей есть, в частности ноль, — есть ход в проигрышную.

То есть для одной игры Гранди не даёт ничего нового. Всё богатство — в сумме игр.

Как считать

int grundy(int v) {
    if (computed[v]) return value[v];
    computed[v] = true;
    std::vector<char> seen(moves[v].size() + 1, 0);
    for (int u : moves[v]) { int g = grundy(u); if (g < (int)seen.size()) seen[g] = 1; }
    int m = 0;
    while (m < (int)seen.size() && seen[m]) m++;
    return value[v] = m;
}

Размер seen выбран не случайно. Значение $\mathrm{mex}$ по $d$ числам не превосходит $d$, поэтому массива длины $d + 1$ хватает всегда, а всё, что больше, можно не запоминать. Суммарно по всем вершинам это $O(V + E)$ — без этого приёма получилось бы $O(V \cdot \max G)$ памяти или лишний логарифм на множество.

Кратные рёбра значение не меняют. $\mathrm{mex}$ считается по множеству, а повтор в множестве ничего не добавляет. Но время они съедают, так что при $m$ рёбрах цикл всё равно проходит все $m$ штук.

Чему равно значение Гранди

Заранее — ничему. Для конкретной игры его считают перебором на маленьких размерах, после чего смотрят на таблицу и угадывают закономерность; см. «Как искать закономерность».

Пара примеров, чтобы было с чем сравнивать:

игра	значение Гранди
куча $x$, берут сколько угодно	$x$
куча $x$, берут от 1 до $k$	$x \bmod (k + 1)$
куча $x$, берут элемент из $S$	периодично, период ищется перебором

Смежное

• Сумма игр — зачем всё это было;
• Ним — игра, ради которой определение и придумано.