Функция Шпрага — Гранди

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

В случае дискретных игр иногда называется нимбером.

Теорема Шпрага-Гранди — это общий вывод из результатов, которые были независимо сформулированы и доказаны Р. Шпрагом (1935) и П. М. Гранди (1939). Она состоит в том, что для любой беспристрастной игры, где выигрывает сделавший последний ход, для каждой позиции однозначно определено значение функции Шпрага-Гранди, которое и определяет выигрышную стратегию либо её отсутствие.

Определения

Определение 1

Функцией Шпрага-Гранди называется такая функция F, определенная для x и принимающая неотрицательные значения, так что:

$F(x)=mex\{F(y)\ |\ y\in G(x)\}$

где

• y — одна из позиций, в которую можно перейти непосредственно из позиции х за один ход,
• F(y) — значения Шпрага-Гранди позиций, в которые можно перейти непосредственно из позиции х за один ход,
• G(x) — список позиций, в которые можно перейти непосредственно из позиции х за один ход.

Таким образом, F(x) — наименьшее неотрицательное целое число, не найденное среди значений Шпрага-Гранди для определенных х.

Определение 2

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

$F(P)=0,$ если позиция P — однозначно проигрышная (нельзя сделать ни одного хода)

$F(P)=\min(\Omega \setminus \{F(Q)|Q\in G(P)\})$ в иных случаях,

где $\Omega$ — множество целых неотрицательных чисел, а $G(P)$ — множество всех допустимых ходов из позиции P.

Основные свойства

1. Если х — конечная позиция, то F(x) = 0. Позиции х, для которых F(x) = 0, являются П-позициями (проигрышными для игрока, чья очередь делать ход), тогда как все другие позиции соответственно Н-позициями (выигрышными для игрока, чья очередь делать ход). Выигрышная стратегия заключается в том, чтобы выбирать на каждом шаге ход, в котором значение Шпрага-Гранди равно нулю.
2. Из позиции х, для которой F(x) = 0, существуют ходы только в позицию у такую, что F(y) ≠ 0.
3. Из позиции х, для которой F(x) ≠ 0, существует хотя бы один ход в позицию у, для которой F(y) = 0.

Применение

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

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

Сумма игр

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

Функция Шпрага-Гранди обладает одним удивительным свойством, которое позволяет оптимально играть в сумму игр $G_{1}+G_{2}+...+G_{n}$, зная функцию Шпрага-Гранди для всех позиций каждой из игр $G_{i}$. Формулируется оно следующим образом:

$F(P_{1},P_{2},\dots ,P_{n})=F(P_{1})\oplus F(P_{2})\oplus \dots \oplus F(P_{n}),$

где $\oplus$ — исключающее «или» (он же XOR).

Пример

Задача

Имеется площадь, состоящая из 10 клеток. Играют два игрока. За один ход разрешается делить площадь на две неравные ненулевые площади так, чтобы единство каждой отдельно взятой клетки не нарушалось (то есть клетку делить нельзя). Проигрывает тот, кто не может сделать ход. Кто выигрывает при условии правильной справедливой игры?

Решение

Задача решается с конца. Рассмотрим варианты деления площади для всех случаев от 1 до 10 клеток, и найдем для них значения функции Шпрага-Гранди. Заметим, что для данной игры, в результате деления площади каждый раз на две новые площади, значение функции Шпрага-Гранди находится с помощью Ним-суммы.

Значение Шпрага-Гранди для n = 10 получается равным 0. Следовательно, игрок, делающий ход первым, проигрывает. При любом его ходе второй игрок переходит в позиции 4 + 4 или n = 1/2/7, значение Шпрага-Гранди для которых также равно 0.

Ответ

Выигрывает тот, кто ходит вторым.

См. также

• Ним (игра)
• Игра Гранди

Ссылки

• Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.
• Nivasch G. The Sprague-Grundy theory of impartial games  (недоступная ссылка с 13-05-2013 [3987 дней] — история) (англ.)
• Куммер Б. Н. §2.2. Функция Гранди и суммы порядка p // Игры на графах. — 1982.
• B. C. A. Milvang-Jensen. Combinatorial Games, Theory and Applications (неопр.). — 2000.
• Thomas S. Ferguson GAME THEORY
• The Sprague-Grundy theory of impartial games  (недоступная ссылка с 13-05-2013 [3987 дней] — история) (англ.), November 9, 2005
• Sprague-Grundy Values of Grundy’s Game (англ.)
• P. M. Grundy. Mathematics and Games (неопр.) // Eureka. — 1964. — Т. 27. Архивировано 27 сентября 2007 года.