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

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

Определение

Определение: Функцией Шпрага-Гранди называется такая функция G, определенная для x и принимающая неотрицательные значения, так что:
$\!G(x) = min \{n\geq 0 : n\neq G(y), y \in F(x)\}$, где
n – любое целое неотрицательное число,
y – одна из позиций, в которую можно перейти непосредственно из позиции х за один ход,
G(y) – значения Шпрага-Гранди позиций, в которые можно перейти непосредственно из позиции х за один ход,
F(x) – список позиций, в которые можно перейти непосредственно из позиции х за один ход.
Таким образом, G(x) – наименьшее неотрицательное целое число, не найденное среди значение Шпрага-Гранди для определенных х.

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

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

Правило minex

Используя правило minex, функцию Шпрага-Гранди можно иначе записать как:
$G(x) = minex\{G(y) : y \in F(x)\}$
Для определения правила minex рассмотрим игру Ним с пятью ним кучками : {0, 1, 2, 5, 9}, которые представляют собой множество S. Правило говорит, что если исходы игры G эквивалентны ним кучкам размера, представленным множеством S, то G эквивалентно ним кучке размера m , где m является самым маленьким неотрицательным целым числом, не содержавшимся в S. Это число m записывается как minex(S) , где minex расшифровывается как ‘minimum excludant’, что на русском языке означает «минимальное невключаемое». Таким образом,
$m = minex(S) = min\{k\geq 0|k\notin S\}$
minex{0, 1, 2, 5, 9} = 3

Пример задачи

Задача: Имеется площадь, состоящая из 10 клеток. Играют два игрока. За один ход разрешается делить площадь на две неравные ненулевые площади так, чтобы единство каждой отдельно взятой клетки не нарушалось(т.е. клетку делить нельзя). Прогрывает тот, что не может сделать ход. Кто выигрывает при условии правильной справедливой игры?
Решение: Задача решается с конца.Рассмотрим варианты деления площади если клеток от 1 до 10 и найдем значения Шпрага-Гранди для каждого случая. Заметим, что для данной игры, в результате деления площади каждый раз на две новые площади, значение Шпрага-Гранди находится используя Ним сумму.
Значение Шпрага-Гранди для n = 10 равно 0. Следовательно, игрок, делающий ход первым проигрывает.
Ответ: Выигрывает тот, кто ходит вторым.

Литература

• Brit C. A. Milvang-Jensen Combinatorial Games,Theory and Applications February 18, 2000
  
• Thomas S. Ferguson GAME THEORY
  
• The Sprague-Grundy theory of impartial games November 9, 2005 [[1]]
  
• Sprague-Grundy Values of Grundy's Game[[2]]
  
• Nim game [[3]]
  
• Grundy's game [[4]]
  
• P. M. Grundy Mathematics and Games Eureka 27 1964 [[5]]