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

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

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

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

Применение

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

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

Сумма игр

Если у нас имеется n игр $G_{1},G_{2},...,G_{n}$, то можно рассмотреть комбинацию этих игр, для которой игровое поле состоит из совокупности игровых полей для игр $G_{1},G_{2},...,G_{n}$ и за один ход игрок может выбрать некоторое i, 1 ≤ i ≤ n, и сделать ход на игровом поле для игры $G_{i}$. Такая комбинация называется суммой игр $G_{1},G_{2},...,G_{n}$ и обозначается $G_{1}+G_{2}+...+G_{n}$. Ситуацию на игровом поле игры $G_{1}+G_{2}+...+G_{n}$, когда игровое поле игры Gi находится в позиции $P_{i}$, удобно обозначать как $(P_{1},P_{2},...,P_{n})$.

Функция Гранди обладает одним удивительным свойством, которое позволяет оптимально играть в сумму игр $G_{1}+G_{2}+...+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. Функция Шпрага-Гранди