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

Функция Гранди — функция, определённая для игр для 2 игроков, где проигрывает игрок, не имеющий возможности сделать очередной ход. Широко используется в теории игр. В случае дискретных игр иногда называется нимбером.

Функция определена на множестве всех позиций игры G следующим образом:

$\!F(P) = 0$, 
   если позиция P - однозначно проигрышная (нельзя сделать ни одного хода)
$\!F(P) = min (\Omega\setminus\{F(Q)|Q \in G(P)\})$ 
   в иных случаях(здесь Ω - множество целых неотрицательных чисел,
а G(P) - множество всех допустимых ходов из позиции P)

Применение

Одно из полезных свойств функции Гранди заключается в том, что она равна нулю для всех проигрышных позиций и положительна для всех выигрышных позиций. Это даёт метод нахождения выигрышной стратегии:

1. Найти функцию Гранди, например, строя её рекуррентно, начиная с конечных позиций.
2. Если в начальной позиции функция Гранди равна нулю, то игра для первого игрока проигрышна.
3. В противном случае, первый игрок может выиграть, перемещаясь каждым ходом в позицию с нулевым значением функции Гранди.

Сумма игр

Если у нас имеется n игр G₁,G₂,...,G_n, то можно рассмотреть комбинацию этих игр, для которой игровое поле состоит из совокупности игровых полей для игр G₁,G₂,...,G_n и за один ход игрок может выбрать некоторое i, 1 ≤ i ≤ n, и сделать ход на игровом поле для игры G_i. Такая комбинация называется суммой игр G₁,G₂,...,G_n и обозначается G₁ + G₂ + ... + G_n. Ситуацию на игровом поле игры G₁ + G₂ + ... + G_n, когда игровое поле игры Gi находится в позиции P_i, удобно обозначать как (P₁,P₂,...,P_n).

Функция Гранди обладает одним удивительным свойством, которое позволяет оптимально играть в сумму игр G₁ + G₂ + ... + G_n, зная функцию Гранди для всех позиций каждой из игр Gi. Формулируется оно следующим образом:

$\!F(P_1, P_2, ..., P_n) = F(P_1)\oplus F(P_2)\oplus ... \oplus F(P_n)$, где $\!\oplus$ — исключающее «или».

Ссылки

1. Куммер Б.N. «Игры на графах», 1982 (§ 2.2. Функция Гранди и суммы порядка р)

2. http://yucs.org/~gnivasch/cgames/spraguegrundy/index.html Статья о теории Шпрага-Гранди объективных игр на графах (на англ. яз.)

3. Функция Шпрага-Гранди