Теория игр на собеседовании: Ним, функция Шпрага–Гранди и Can I Win

Игровые задачи на собеседовании: выигрышные и проигрышные позиции, Ним и XOR, функция Шпрага–Гранди, разбор Nim Game, Stone Game, Predict the Winner и Can I Win. Код на Python.

15 мин чтенияалгоритмы · теория игр · динамическое программирование · python

Коротко

ВопросОтвет
Что за задачиДвое ходят по очереди, оба играют оптимально. Нужно сказать, выиграет ли первый
Главная идеяПозиция выигрышная, если есть ход в проигрышную. Проигрышная — если все ходы ведут в выигрышные
НимПервый выигрывает, если XOR размеров куч не равен нулю
Шпраг–ГрандиКаждой позиции ставится число g=mexg = \mathrm{mex} чисел соседей. Сумма игр — XOR этих чисел
Как решать в целомМемоизация по состоянию: O(состояния×ходы)O(\text{состояния} \times \text{ходы}). Потом ищем закономерность
ЗадачиNim Game (292), Stone Game (877), Predict the Winner (486), Can I Win (464)

Игровые задачи пугают формулировкой «оба игрока играют оптимально». Кажется, нужно перебрать все стратегии соперника. На деле всё сводится к одному рекурсивному правилу и мемоизации. Иногда за перебором стоит формула в одну строку, и интервьюер ждёт, что вы её заметите.

Какие игры здесь разбираются

Теория игр — большая область. На собеседованиях встречается узкий класс, беспристрастные комбинаторные игры:

  • два игрока ходят по очереди;
  • информация полная, случайности нет;
  • набор доступных ходов зависит только от позиции, а не от того, чей ход (поэтому «беспристрастные»);
  • игра конечна, ничьих нет;
  • кто не может сделать ход, проигрывает. Это нормальное правило. Обратное называют мизерным.

Stone Game и Predict the Winner формально не беспристрастные: там важен счёт каждого игрока. Но решаются они той же идеей, поэтому разберём и их.

Выигрышные и проигрышные позиции

Возьмём простейшую игру. На столе nn камней, за ход можно взять 1, 2 или 3. Кто взял последний камень, тот выиграл. Это задача Nim Game, LeetCode 292.

Каждую позицию (число оставшихся камней) пометим одной из двух букв:

  • P (previous) — проигрышная для того, кто ходит. Выигрывает предыдущий игрок;
  • N (next) — выигрышная для того, кто ходит.

Правила разметки:

  1. Позиция без ходов — P. Ходить нечем, вы проиграли.
  2. Если хотя бы один ход ведёт в P — позиция N. Делаем этот ход, и сопернику достаётся проигрышная позиция.
  3. Если все ходы ведут в N — позиция P. Что бы вы ни сделали, соперник окажется в выигрышной позиции.

«Оптимальная игра» здесь означает ровно это: игрок, у которого есть ход в P, его делает. Перебирать стратегии соперника не нужно, правила 2 и 3 уже учитывают все его ответы.

Посчитаем таблицу снизу вверх:

def win_table(n, moves=(1, 2, 3)): win = [False] * (n + 1) # win[0] = False: ходить нечем — проигрыш for x in range(1, n + 1): win[x] = any(m <= x and not win[x - m] for m in moves) return win print([int(w) for w in win_table(12)]) # [0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]

Нули стоят на 0, 4, 8, 12. Закономерность видна сразу: проигрышны позиции, кратные 4. Доказательство короткое. Из позиции 4k4k любой ход (1, 2 или 3) уводит в число, не кратное 4. А из числа, не кратного 4, всегда можно взять остаток от деления на 4 и вернуть соперника в 4k4k.

def canWinNim(n: int) -> bool: return n % 4 != 0

Сложность — O(1)O(1). В задаче nn доходит до 231−12^{31} - 1, поэтому таблица на nn элементов не пройдёт ни по времени, ни по памяти. Это типичный сюжет: сначала перебор на маленьких nn, потом формула. На собеседовании так и говорите: «Посчитаю таблицу для первых 20 значений и поищу период». Это нормальный рабочий приём, а не жульничество.

Тот же приём на Divisor Game

LeetCode 1025: на доске число nn, ход — выбрать делитель xx (0<x<n0 < x < n, n mod x=0n \bmod x = 0) и заменить nn на n−xn - x. Кто не может ходить, проиграл. Перебор по той же схеме даёт: выигрывает первый тогда и только тогда, когда nn чётное. Из чётного числа всегда можно вычесть 1 и отдать сопернику нечётное. У нечётного все делители нечётные, поэтому после любого хода получается чётное.

Ним

Классический Ним: несколько куч камней, за ход можно взять из одной кучи любое положительное число камней. Кто взял последний камень, выиграл.

Позиция теперь — набор размеров куч, и состояний становится много. Но ответ даёт теорема Бутона (Charles Bouton, 1901):

первый игрок выигрывает  ⟺  a1⊕a2⊕⋯⊕ak≠0\text{первый игрок выигрывает} \iff a_1 \oplus a_2 \oplus \dots \oplus a_k \neq 0

где ⊕\oplus — побитовый XOR. Если вы забыли, как он работает, загляните в статью про битовые операции.

Почему XOR

Назовём XOR всех куч ним-суммой ss. Нужно проверить два свойства.

Из s=0s = 0 любой ход ведёт в s≠0s \neq 0. Ход меняет одну кучу aia_i на ai′≠aia_i' \neq a_i. Новая ним-сумма равна s⊕ai⊕ai′=ai⊕ai′s \oplus a_i \oplus a_i' = a_i \oplus a_i'. Это не ноль, потому что ai′≠aia_i' \neq a_i.

Из s≠0s \neq 0 есть ход в s=0s = 0. Возьмём старший единичный бит ss. Найдётся куча aia_i, у которой этот бит тоже равен единице: иначе в XOR он бы не появился. Заменим aia_i на ai⊕sa_i \oplus s. В старшем бите единица превращается в ноль, а более высокие биты не меняются. Значит, ai⊕s<aia_i \oplus s < a_i, и ход допустим. Новая ним-сумма: s⊕ai⊕(ai⊕s)=0s \oplus a_i \oplus (a_i \oplus s) = 0.

Конечная позиция (все кучи пусты) имеет s=0s = 0 и проигрышна. Получается, что позиции с s=0s = 0 — ровно P-позиции.

Доказательство сразу даёт и выигрышный ход:

from functools import reduce from operator import xor def nim_winning_move(piles): x = reduce(xor, piles, 0) if x == 0: return None # позиция проигрышная for i, p in enumerate(piles): target = p ^ x if target < p: return i, p - target # из кучи i взять столько камней print(nim_winning_move([3, 4, 5])) # (0, 2): из кучи 3 берём 2, остаётся 1, 1 ^ 4 ^ 5 = 0 print(nim_winning_move([1, 2, 3])) # None: 1 ^ 2 ^ 3 = 0

Проверка перебором

Формулу всегда стоит сверить с честным перебором. Здесь это делается за десяток строк:

from functools import lru_cache from itertools import product @lru_cache(maxsize=None) def nim_wins(piles): for i, p in enumerate(piles): for take in range(1, p + 1): nxt = tuple(sorted(piles[:i] + (p - take,) + piles[i + 1 :])) if not nim_wins(nxt): return True return False for piles in product(range(6), repeat=3): assert nim_wins(tuple(sorted(piles))) == (reduce(xor, piles) != 0)

Все 216 позиций из трёх куч размером до 5 совпали. Обратите внимание на sorted: порядок куч не важен, и сортировка уменьшает число состояний в кэше.

Мизерный Ним

Если взявший последний камень проигрывает, ответ почти тот же. Пока есть хотя бы одна куча больше 1, правило не меняется: выигрывает первый при ненулевом XOR. Если все кучи размером 0 или 1, всё решает чётность: первый выигрывает, когда единичных куч чётное число. Это правило тоже проверяется перебором. На собеседованиях мизерный вариант встречается редко, но вопрос «а если наоборот?» звучит.

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

Ним красив, но правила бывают другие. Например, из кучи можно брать только 1, 3 или 4 камня. Или ход разрезает кучу на две. Или играют на нескольких досках сразу, и за ход выбирают одну. Как здесь найти ответ?

Теорема Шпрага–Гранди (Роланд Шпраг, 1935; Патрик Гранди, 1939) говорит: любая беспристрастная игра эквивалентна ниму с одной кучей. Размер этой кучи называют числом Гранди позиции.

mex и числа Гранди

mex\mathrm{mex} (minimum excludant) — наименьшее неотрицательное целое, которого нет в множестве:

mex{0,1,3}=2,mex{1,2}=0,mex{}=0\mathrm{mex}\{0, 1, 3\} = 2, \quad \mathrm{mex}\{1, 2\} = 0, \quad \mathrm{mex}\{\} = 0

Число Гранди позиции vv:

g(v)=mex{ g(u):u достижима из v за один ход }g(v) = \mathrm{mex}\{\, g(u) : u \text{ достижима из } v \text{ за один ход} \,\}

Отсюда видно, почему это «куча нима». Из позиции с g=kg = k можно перейти в позиции со всеми значениями 0,1,…,k−10, 1, \dots, k-1, как из кучи размера kk. Переходы в значения больше kk тоже бывают, но они ничего не дают: соперник может вернуть gg обратно к kk.

Главное свойство: позиция проигрышная тогда и только тогда, когда g=0g = 0. Разметка P/N из прошлого раздела — частный случай: g=0g = 0 значит P, g>0g > 0 значит N.

def mex(values): seen = set(values) m = 0 while m in seen: m += 1 return m def grundy_table(n, moves): g = [0] * (n + 1) for x in range(1, n + 1): g[x] = mex(g[x - m] for m in moves if m <= x) return g print(grundy_table(12, (1, 2, 3))) # [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0] print(grundy_table(12, (1, 3, 4))) # [0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3]

Для правила «1, 2 или 3» числа Гранди равны n mod 4n \bmod 4. Нули совпали с ответом Nim Game. Для правила «1, 3 или 4» последовательность периодична с периодом 7: 0 1 0 1 2 3 2. Периодичность у игр с конечным набором вычитаемых чисел — частое явление, им и пользуются, когда nn большое.

Сумма игр

Ради этого функция Гранди и нужна. Пусть игра состоит из нескольких независимых частей: нескольких куч, досок, подграфов. За ход игрок выбирает одну часть и ходит в ней. Тогда

g(сумма)=g1⊕g2⊕⋯⊕gkg(\text{сумма}) = g_1 \oplus g_2 \oplus \dots \oplus g_k

Каждая часть ведёт себя как куча нима размера gig_i, а сумма — как Ним из этих куч. Первый выигрывает, если XOR не равен нулю.

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

@lru_cache(maxsize=None) def sum_wins(piles, moves=(1, 3, 4)): for i, p in enumerate(piles): for m in moves: if m <= p: nxt = tuple(sorted(piles[:i] + (p - m,) + piles[i + 1 :])) if not sum_wins(nxt): return True return False g = grundy_table(20, (1, 3, 4)) for piles in product(range(15), repeat=3): expected = g[piles[0]] ^ g[piles[1]] ^ g[piles[2]] != 0 assert sum_wins(tuple(sorted(piles))) == expected

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

Когда ход разрезает позицию

Если ход делит одну кучу на две, число Гранди результата — XOR двух частей. Например, в игре «уберите один или два соседних кегля из ряда» ход превращает ряд длины nn в два ряда длин aa и bb, и

g(n)=mex{ g(a)⊕g(b) }g(n) = \mathrm{mex}\{\, g(a) \oplus g(b) \,\}

по всем допустимым разрезам. На собеседовании такое встречается редко. Если встретилось, вы уже знаете, что делать.

Stone Game (LeetCode 877)

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

Решение через разность

Это уже не беспристрастная игра: важен счёт, а не только «кто не может ходить». Приём другой — считать разность: сколько очков ходящий игрок наберёт сверх соперника на отрезке [i, j], если оба играют оптимально.

diff(i,j)=max⁡(pi−diff(i+1,j), pj−diff(i,j−1))\mathrm{diff}(i, j) = \max\bigl(p_i - \mathrm{diff}(i+1, j),\ p_j - \mathrm{diff}(i, j-1)\bigr)

Взяв кучу, мы получаем её камни, а дальше ходит соперник, и его преимущество на оставшемся отрезке вычитается из нашего. Одна функция описывает обоих игроков, потому что после хода они меняются ролями. Такую схему называют минимакс в форме негамакса.

from functools import lru_cache def stone_diff(piles): @lru_cache(maxsize=None) def diff(i, j): if i > j: return 0 return max(piles[i] - diff(i + 1, j), piles[j] - diff(i, j - 1)) return diff(0, len(piles) - 1) print(stone_diff((5, 3, 4, 5))) # 1: первый наберёт на 1 камень больше

Сложность — O(n2)O(n^2) по времени и памяти. Это классическое ДП по отрезкам.

Решение в одну строку

def stoneGame(piles): return True

Это не шутка. Пронумеруем кучи с нуля и раскрасим: чётные индексы белые, нечётные чёрные. Куч чётное число, поэтому первый игрок может забрать все белые или все чёрные кучи по своему выбору. Если он взял крайнюю белую, оба края у соперника становятся чёрными. Соперник берёт чёрную и открывает белую. Первый игрок заранее сравнивает сумму белых и чёрных (они не равны, общая сумма нечётная) и играет за большую. Значит, он выигрывает всегда.

На собеседовании хорошо показать оба решения. ДП доказывает, что вы умеете решать такие задачи в общем виде. Наблюдение про раскраску показывает, что вы читаете ограничения. Убедитесь только, что интервьюер не убрал условие про чётность: без него return True неверен.

Predict the Winner (LeetCode 486)

Та же игра, но массив любой длины, ничья засчитывается первому. Раскраска больше не работает, нужна разность. Здесь удобно показать итеративную версию с памятью O(n)O(n):

def predict_the_winner(nums): n = len(nums) dp = nums[:] # dp[i] для отрезка длины 1: [i, i] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i] = max(nums[i] - dp[i + 1], nums[j] - dp[i]) return dp[0] >= 0 print(predict_the_winner([1, 5, 2])) # False print(predict_the_winner([1, 5, 233, 7])) # True

После прохода с длиной length в dp[i] лежит разность для отрезка [i, i + length - 1]. В формуле dp[i + 1] — ещё значение предыдущей длины для [i + 1, j], а dp[i] справа — для [i, j - 1]. Порядок обновления слева направо здесь важен: dp[i + 1] ещё не перезаписан в этом проходе.

Can I Win (LeetCode 464)

Числа от 1 до maxChoosableInteger (не больше 20). Игроки по очереди берут ещё не взятое число и прибавляют его к общей сумме. Кто первым довёл сумму до desiredTotal или выше, выиграл. Выиграет ли первый?

Состояние — маска взятых чисел

Позиция определяется тем, какие числа уже взяты. Чисел не больше 20, значит, множество кодируется битовой маской: не больше 220≈1062^{20} \approx 10^6 состояний. Подробно этот приём разобран в статье про ДП по битовым маскам.

Правило то же, что в начале статьи: позиция выигрышная, если есть ход, который сразу побеждает или оставляет сопернику проигрышную позицию.

from functools import lru_cache def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool: if desiredTotal <= 0: return True if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal: return False # даже все числа вместе не дотягивают — никто не выиграет @lru_cache(maxsize=None) def wins(used: int, remaining: int) -> bool: for k in range(1, maxChoosableInteger + 1): bit = 1 << k if used & bit: continue if k >= remaining or not wins(used | bit, remaining - k): return True return False return wins(0, desiredTotal) print(canIWin(10, 11)) # False print(canIWin(10, 1)) # True print(canIWin(20, 210)) # False: 1 + 2 + ... + 20 = 210, последнее число возьмёт второй

Тонкие места:

  • remaining не входит в ключ по смыслу. Сумма взятых чисел однозначно определяется маской, поэтому remaining — функция от used. Мемоизация по паре не увеличивает число состояний. Если пишете на Java или C++ с массивом на 2202^{20} элементов, индексируйте только маской.
  • Проверка «сумма всех чисел меньше цели» обязательна. Без неё рекурсия дойдёт до позиции, где все числа взяты, а цель не достигнута. Там ходов нет, wins вернёт False, и победа достанется тому, кто взял последнее число. Например, canIWin(3, 100) вернёт True, хотя до 100 не дотянется никто и правильный ответ — False.
  • desiredTotal <= 0. Первый игрок считается победителем сразу. Код вернул бы True и без этой проверки (любое k >= 0), но явная строка читается лучше и не зависит от деталей цикла.

Сложность — O(2m⋅m)O(2^m \cdot m), где mm = maxChoosableInteger. На самом тяжёлом входе Python укладывается примерно в секунду-две. На собеседовании этого достаточно.

Почему здесь нет формулы

Can I Win — хороший пример, когда закономерности нет. Числа «одноразовые», игра не раскладывается на независимые части, и Шпраг–Гранди не помогает. Остаётся честная мемоизация по состоянию. Это нормально: большинство игровых задач на LeetCode решаются именно так, а формула — приятный бонус.

Общий алгоритм решения игровой задачи

  1. Опишите состояние. Что полностью определяет позицию: число камней, отрезок [i, j], маска взятых элементов, набор куч.
  2. Решите, что считаете. Если важен только победитель — булево «выигрывает ли ходящий». Если важен счёт — разность очков ходящего и соперника.
  3. Запишите переход. Для булева: any(not win(next)). Для разности: max(gain - diff(next)).
  4. Добавьте мемоизацию. Без неё перебор экспоненциальный даже там, где состояний мало. Про сам приём — в статье о мемоизации.
  5. Если ограничения огромные (nn до 10910^9), посчитайте таблицу для маленьких значений и найдите период или формулу. Докажите её хотя бы на словах.
  6. Если игра раскладывается на независимые части, считайте число Гранди каждой части и берите XOR.

Типичные ошибки

Путать «есть ход» и «все ходы». Позиция выигрышная, если существует хотя бы один ход в проигрышную. Частая ошибка — вернуть False, как только нашёлся ход в выигрышную позицию соперника. Цикл должен перебрать все ходы, прежде чем объявить проигрыш.

Считать очки обоих игроков отдельно. В Stone Game так рождаются состояния вида (i, j, чей_ход, мои_очки), и их слишком много. Разность очков на отрезке не зависит от того, сколько уже набрано, и одной функции хватает на обоих игроков.

Забыть базу. Позиция без ходов — проигрыш в нормальной игре и выигрыш в мизерной. Перепутанная база инвертирует весь ответ.

Сложение вместо XOR. В сумме игр числа Гранди складываются через XOR. Обычная сумма даст неверный ответ уже на двух кучах по 1 камню: 1+1=2≠01 + 1 = 2 \neq 0, но позиция проигрышная, 1⊕1=01 \oplus 1 = 0.

Выдавать формулу без проверки. Закономерность из первых десяти значений может сломаться на одиннадцатом. Сверьте её с перебором хотя бы до 50–100.

Где это встречается на собеседованиях

Игровые задачи — не самая частая тема, но в списках LeetCode их хватает: Nim Game, Stone Game и несколько продолжений (Stone Game II–IX), Predict the Winner, Can I Win, Divisor Game, Flip Game II. Обычно они проверяют три вещи:

  • умеете ли вы формализовать «оптимальную игру» как рекурсию по состояниям;
  • видите ли, что нужна мемоизация, и правильно ли выбираете ключ;
  • замечаете ли закономерность, когда ограничения не оставляют места для перебора.

Хорошая стратегия ответа: сначала сформулировать правило P/N или разность, написать мемоизированный перебор, оценить число состояний и только потом искать формулу. Если формулу найти не удалось, рабочий перебор с правильной оценкой сложности — уже сильный ответ. Если удалось, покажите, как вы её проверили.

Для общей подготовки к ДП полезно начать со статьи динамическое программирование для начинающих: игровые задачи — это то же ДП, только переход описывает ход соперника.

Потренироваться в спокойной обстановке

Все задачи