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

---

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

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

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

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

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

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

---