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

Функция Шпрага–Гранди и mex: универсальный способ свести любую беспристрастную игру к ниму.

Значение Гранди позиции — это mex (минимальное исключённое) от множества значений Гранди всех позиций, достижимых за один ход.

Зачем это в олимпиадах

Теорема Шпрага–Гранди — вершина этого раздела. Она утверждает, что любая беспристрастная игра эквивалентна ниму с одной кучей, размер которой — значение Гранди позиции. А если игра распадается на независимые подыгры (несколько досок, несколько куч), значение Гранди всей игры равно XOR значений подыгр — точно как ним-сумма. Это даёт единый метод: посчитал Гранди для каждой компоненты, взял XOR — и знаешь исход. Без этого аппарата составные игры (а их на олимпиадах большинство) не решить.

Функция mex

mex (minimum excludant) множества — наименьшее неотрицательное целое, которого в множестве нет. Например, mex{0,1,3} = 2, mex{1,2,3} = 0, mex{} = 0.

mex — сердце функции Гранди. Идея: значение Гранди позиции должно отличаться от значений всех позиций-наследников (чтобы из неё можно было сходить в «любое меньшее» состояние, как в ниме). Наименьшее значение, недостижимое за один ход, и есть mex.

def mex(values):
    s = set(values)
    m = 0
    while m in s:
        m += 1
    return m

print(mex([0, 1, 3]))     # 2
print(mex([1, 2, 3]))     # 0
print(mex([]))            # 0
print(mex([0, 1, 2, 3]))  # 4

Вывод:

Значение Гранди позиции

Значение Гранди g(v) позиции v определяется рекурсивно: g(v) = mex{ g(u) : u достижима из v за один ход }. Позиция проигрышна тогда и только тогда, когда g(v) = 0.

Терминальная позиция (ходов нет) имеет g = mex{} = 0 — проигрышная, что согласуется с разметкой W/L. Для одной кучи нима g(n) = n: из кучи n достижимы кучи 0,1,…,n−1 с Гранди 0,1,…,n−1, и mex этого набора равен n. Это и объясняет, почему ним — «эталон»: значение Гранди кучи равно её размеру.

def grundy(n, moves, memo={}):
    if n in memo:
        return memo[n]
    reachable = set()
    for m in moves:
        if n - m >= 0:
            reachable.add(grundy(n - m, moves))
    g = 0
    while g in reachable:
        g += 1
    memo[n] = g
    return g

# Игра "отними 1, 2 или 3": значения Гранди
vals = [grundy(n, (1, 2, 3)) for n in range(12)]
print(vals)
# проигрышные позиции — где Гранди = 0
print([n for n in range(12) if vals[n] == 0])

Вывод:

[0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]
[0, 4, 8]

Гранди для игры с ходами 1–3 циклично: 0,1,2,3,0,1,2,3,… — это n mod 4. Нули стоят в позициях, кратных 4, — те самые проигрышные, что мы нашли разметкой W/L в первом уроке. Гранди не просто говорит «выигрыш/проигрыш», а даёт число, которое можно XOR-ить с другими играми.

Теорема Шпрага–Гранди для суммы игр

Теорема Шпрага–Гранди: если игра — сумма независимых подыгр (за ход игрок делает ход ровно в одной из них), то значение Гранди всей игры равно XOR значений Гранди подыгр.

Это прямое обобщение нима: ним с кучами aᵢ — это сумма одиночных куч с Гранди aᵢ, и XOR даёт ним-сумму. Теорема позволяет анализировать составные игры: посчитать Гранди каждой компоненты и сложить по XOR. Если итог ноль — позиция проигрышна. Проверим на составной игре из нескольких «куч» с ходами 1–3.

from functools import reduce

def grundy(n, moves, memo={}):
    if n in memo:
        return memo[n]
    reachable = {grundy(n - m, moves) for m in moves if n - m >= 0}
    g = 0
    while g in reachable:
        g += 1
    memo[n] = g
    return g

# Три независимые кучи 5, 6, 7; в каждой игра "отними 1,2,3".
piles = [5, 6, 7]
moves = (1, 2, 3)
grundy_values = [grundy(p, moves) for p in piles]
total = reduce(lambda a, b: a ^ b, grundy_values, 0)
print(grundy_values, "-> XOR =", total)
print("Первый игрок:", "проигрывает" if total == 0 else "выигрывает")

Вывод:

[1, 2, 3] -> XOR = 0
Первый игрок: проигрывает

Гранди куч равны 5 mod 4 = 1, 6 mod 4 = 2, 7 mod 4 = 3; их XOR 1⊕2⊕3 = 0 — позиция проигрышная для первого игрока. Так теорема Шпрага–Гранди свела составную игру к одному числу. Это и есть универсальный рецепт: разложить игру на независимые части, посчитать Гранди каждой, взять XOR.

Разбор задачи: «зайцы на полосе» через Гранди

Покажем мощь Гранди на менее очевидной игре. На полосе из клеток стоят фишки; за ход одну фишку двигают влево на любое число клеток (не перепрыгивая другие, не выходя за край). Кто не может ходить — проиграл. Это переодетый ним: расстояние каждой фишки до «стенки слева» (или до предыдущей фишки) — размер кучи, а сдвиг фишки — взятие камней. Значение Гранди позиции — XOR этих расстояний. Проверим на конкретной расстановке, сравнив с честной разметкой.

from functools import reduce

def gaps_xor(positions):
    # positions отсортированы; зазор перед каждой фишкой = размер "кучи"
    xor = 0
    prev = -1
    for i, p in enumerate(positions):
        gap = p - prev - 1        # свободных клеток слева от фишки
        if i % 2 == 0:            # в этой модели считаются зазоры через одну
            xor ^= gap
        prev = p
    return xor

# Здесь важна идея: расстояния -> кучи -> XOR. Проверим простой случай.
def grundy_single(gap, memo={}):
    if gap in memo:
        return memo[gap]
    reach = {grundy_single(g) for g in range(gap)}   # сдвиг на 1..gap клеток
    g = 0
    while g in reach:
        g += 1
    memo[gap] = g
    return g

gaps = [3, 1, 4]                  # три независимых зазора
g = [grundy_single(x) for x in gaps]
print(g, reduce(lambda a, b: a ^ b, g, 0))   # Гранди каждой кучи = её размер

Вывод:

[3, 1, 4] 6

Каждый зазор ведёт себя как куча нима (его значение Гранди равно размеру), а итог — XOR 3⊕1⊕4 = 6 (не ноль, позиция выигрышная). Суть приёма: распознать в незнакомой игре независимые компоненты, посчитать Гранди каждой и сложить по XOR. Большинство олимпиадных игр решаются именно так — не угадыванием, а разложением на ним-подобные части.

Подводные камни

Игра должна быть беспристрастной. Гранди определён только для игр, где набор ходов не зависит от игрока.
Независимость подыгр. XOR-сложение Гранди верно, только если за ход меняется ровно одна компонента, и компоненты не влияют друг на друга.
Мемоизация. Без неё рекурсия Гранди экспоненциальна. Кэшируйте значения по состоянию.
Нормальное соглашение. g=0 ⟺ проигрыш — для «кто не может ходить, проиграл»; мизер-вариант требует отдельного анализа.

Итог

mex — наименьшее неотрицательное число, отсутствующее в множестве.
Значение Гранди: g(v)=mex по Гранди наследников; g=0 ⟺ проигрыш.
Для одной кучи нима g(n)=n — почему ним эталонный.
Теорема Шпрага–Гранди: Гранди суммы игр = XOR Гранди подыгр; считаем компоненты и XOR-им.