Ним и функция Шпрага-Гранди: игры, которые складываются

Если ты умеешь считать числа Гранди через mex и знаешь, почему сумма игр решается XOR, листай до «Теперь сам».

Как думаешь, кто выиграет

Три кучки: 3, 5 и 7 камней. За ход берёшь любое количество из одной кучки. Кто взял последний камень - выиграл (у соперника нет хода). Ходишь ты.

Прежде чем читать дальше, ответь себе: стоит ли ходить вообще, или любая твоя партия проиграна? Минимакс ответит, перебрав сотни позиций. А если кучек десять и в каждой по тысяче камней - позиций больше, чем атомов во Вселенной. Неужели ответ требует перебора?

На что это похоже

Шахматный блиц на нескольких досках сразу, где ход - сделать ход на одной любой доске, а проигрывает тот, кому ходить уже некуда нигде. Каждую доску можно оценить отдельно - и оказывается, что оценка доски не «выиграна или проиграна», а ЧИСЛО: насколько она «эквивалентна кучке камней». Тогда весь сеанс - это ним из нескольких кучек, и судьбу решает простая операция над этими числами.

Механизм: mex, числа Гранди и XOR

mex(набор) = наименьшее неотрицательное целое, которого в наборе нет
             mex{0, 1, 3} = 2,   mex{1, 2} = 0,   mex{} = 0

число Гранди позиции:  g(p) = mex { g(q) : q - позиция после хода из p }
                       нет ходов → g = 0 (проигрыш ходящего)
g(p) = 0  ⇔  ходящий проигрывает при правильной игре соперника

сумма игр (ход - в ОДНОЙ части):  g = g₁ XOR g₂ XOR … XOR g_k

XOR: записать числа в двоичной системе и в каждом разряде
     сложить без переноса (1 + 1 = 0)
     3 = 011,  5 = 101,  7 = 111
     011 XOR 101 = 110,  110 XOR 111 = 001

Почему в ниме число Гранди кучки - её размер: из кучки k можно перейти в кучки 0, 1, …, k − 1, их числа Гранди - все от 0 до k − 1, и mex - ровно k.

Почему XOR. Если XOR равен нулю, любой ход меняет ровно одну часть - и один разряд хотя бы одного числа, - и XOR становится ненулевым. Если XOR не ноль, найдётся ход в часть, после которого он ноль: возьми старший разряд XOR, найди часть, у которой в этом разряде единица, и уменьши её число Гранди до g_i XOR (общий XOR) - оно меньше, а значит, по определению mex, такой ход существует. Так игрок с ненулевым XOR всегда возвращает соперника в ноль, и в конце у соперника нет хода.

Правило

В играх, где ходы одинаковы для обоих, ничьих нет и проигрывает не имеющий хода, у каждой позиции есть число Гранди: mex чисел Гранди позиций после хода; ноль - проигрыш ходящего. Игра из независимых частей, где за ход меняется одна часть, имеет число Гранди - XOR чисел частей (теорема Шпрага-Гранди). В ниме число кучки - её размер, и выигрышный ход - сделать XOR нулём.

Разбор: ним 3, 5, 7 и игра «бери 1, 3 или 4»

НИМ 3, 5, 7
XOR = 3 XOR 5 XOR 7 = 1  ≠ 0  → ходящий выигрывает
ход: нужна кучка, которая уменьшится до g XOR 1:
    3 XOR 1 = 2 < 3   → взять 1 камень из кучки 3
позиция 2, 5, 7:  2 XOR 5 XOR 7 = 010 XOR 101 XOR 111 = 000

ИГРА «БЕРИ 1, 3 ИЛИ 4 КАМНЯ» из одной кучки
g(0) = 0
g(1) = mex{g(0)}                 = mex{0}       = 1
g(2) = mex{g(1)}                 = mex{1}       = 0
g(3) = mex{g(2), g(0)}           = mex{0, 0}    = 1
g(4) = mex{g(3), g(1), g(0)}     = mex{1, 1, 0} = 2
g(5) = mex{g(4), g(2), g(1)}     = mex{2, 0, 1} = 3
...  дальше период 7: 0 1 0 1 2 3 2 | 0 1 0 1 2 3 2 | ...

В игре «1, 3 или 4» кучка из 2 камней проигрышна для ходящего: из неё можно взять только 1, и соперник берёт последний. А две такие кучки по 5 камней: 3 XOR 3 = 0 - тоже проигрыш, хотя каждая по отдельности выигрышна.

Разбор: числа Гранди против перебора

Программа считает числа Гранди для нима и для игры «1, 3 или 4», а затем для всех позиций из трёх кучек до восьми камней сверяет правило XOR с честным перебором минимаксом.

from functools import lru_cache


def mex(nabor):                       # наименьшее число не из набора
    m = 0
    while m in nabor:
        m += 1
    return m


@lru_cache(None)
def grundi(kuchka, hody):             # одна кучка, можно взять из hody
    return mex({grundi(kuchka - h, hody) for h in hody if h <= kuchka})


@lru_cache(None)
def vyigryshnaya(kuchki, hody):       # перебор: есть ли ход в позицию,
    for i, k in enumerate(kuchki):    # проигрышную для соперника
        for h in hody:
            if h <= k:
                nov = kuchki[:i] + (k - h,) + kuchki[i + 1:]
                nov = tuple(sorted(nov))
                if not vyigryshnaya(nov, hody):
                    return True
    return False


def xor(chisla):                      # сложение разрядов без переноса
    r = 0
    for x in chisla:
        r ^= x
    return r


nim = tuple(range(1, 11))             # ним: брать сколько угодно
print("ним, Гранди кучек 0..10:", [grundi(k, nim) for k in range(11)])
hody = (1, 3, 4)                      # можно брать 1, 3 или 4
print("ходы 1,3,4, Гранди 0..14:", [grundi(k, hody) for k in range(15)])

proverok = 0
for igra in (nim, hody):
    for a in range(9):
        for b in range(a, 9):
            for c in range(b, 9):
                g = xor(grundi(k, igra) for k in (a, b, c))
                assert vyigryshnaya((a, b, c), igra) == (g != 0)
                proverok += 1
print("позиций из трёх кучек сверено с перебором:", proverok)
for kuchki in ((3, 5, 6), (3, 5, 7)):
    g = xor(kuchki)
    print(f"ним {kuchki}: XOR = {g},",
          "ходящий выигрывает" if g else "ходящий проигрывает")

ним, Гранди кучек 0..10: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ходы 1,3,4, Гранди 0..14: [0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, 0]
позиций из трёх кучек сверено с перебором: 330
ним (3, 5, 6): XOR = 0, ходящий проигрывает
ним (3, 5, 7): XOR = 1, ходящий выигрывает

Все 330 позиций в обеих играх совпали с перебором. В ниме числа Гранди - сами размеры кучек; в игре «1, 3 или 4» видна периодичность с периодом 7, и для кучки в миллиард камней число Гранди вычисляется по остатку от деления на 7 - без всякого перебора.

Что ломается без этого

Первая ошибка - складывать числа Гранди обычным сложением или брать их максимум: XOR и только XOR - 2 + 2 = 4, а 2 XOR 2 = 0, и две одинаковые кучки проигрышны. Вторая - применять теорему к играм, где у игроков разные ходы (шахматы, шашки) или возможна ничья: там чисел Гранди нет. Третья - путать правила окончания: в «поддавках», где проиграл взявший последний камень, анализ другой (для нима почти тот же, но не для произвольной суммы игр). Четвёртая - считать числа Гранди рекурсией без запоминания: позиции повторяются, и время взрывается; таблица по позициям - это та же динамика.

Зачем это в работе

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

Теперь сам

Ним с кучками 1, 4, 5, 6. Ходящий выигрывает или проигрывает? Если выигрывает - какой ход?