Cybernetics Wiki
Advertisement

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

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

, 
   если позиция  - однозначно проигрышная (нельзя сделать ни одного хода)
 
   в иных случаях(здесь  - множество целых неотрицательных чисел,
а  - множество всех допустимых ходов из позиции )

Применение[]

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

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

Сумма игр[]

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

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

, где — исключающее «или».

Ссылки[]

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

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

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

Advertisement