Теорема Шпрага–Гранді. Нім

Вступ

Ця теорема описує так звані безсторонні (impartial) ігри для двох гравців, тобто такі, де доступні ходи та виграш/програш залежать лише від стану гри. Іншими словами, єдина різниця між двома гравцями полягає в тому, що один із них ходить першим.

Крім того, ми вважаємо, що гра має повну інформацію (perfect information), тобто від гравців нічого не приховано (вони знають правила та можливі ходи).

Припускається, що гра скінченна, тобто після певної кількості ходів один із гравців опиниться у програшній позиції — з якої він не може перейти в іншу позицію. А той гравець, який створив суперникові цю позицію, виграє. Зрозуміло, що нічиїх у цій грі немає.

Такі ігри можна повністю описати орієнтованим ациклічним графом: вершини — це стани гри, а ребра — переходи (ходи). Вершина без вихідних ребер є програшною (гравець, який має зробити хід із цієї вершини, програє).

Оскільки нічиїх немає, ми можемо класифікувати всі стани гри як виграшні або програшні. Виграшні стани — це ті, з яких існує хід, що неминуче призводить до поразки суперника навіть за його найкращої відповіді. Програшні стани — це ті, з яких усі ходи ведуть до виграшних станів для суперника. Підсумовуючи: стан є виграшним, якщо існує хоча б один перехід у програшний стан, і програшним, якщо такого переходу в програшний стан немає.

Наше завдання — класифікувати стани заданої гри.

Теорію таких ігор незалежно розвинули Роланд Шпраг (Roland Sprague) у 1935 році та Патрік Майкл Гранді (Patrick Michael Grundy) у 1939 році.

Коли підходить цей алгоритм?

• Чи гра неупереджена — доступні ходи залежать лише від стану, а не від того, хто ходить? (якщо ні, для ігор з нічиєю та циклами → Ігри на довільних графах)
• Чи гра скінченна й ациклічна — після скінченної кількості ходів настане позиція без ходів?
• Чи розпадається позиція на незалежні підігри, результати яких можна об'єднати XOR-сумою чисел Гранді?

Нім

Ця гра задовольняє описані вище обмеження. Більше того, будь-яку безсторонню гру двох гравців з повною інформацією можна звести до гри нім. Вивчення цієї гри дозволить нам розв'язувати всі інші подібні ігри, але про це згодом.

Історично ця гра була популярна ще в давнину. Її походження, ймовірно, з Китаю — або принаймні гра Jianshizi дуже на неї схожа. У Європі найперші згадки про неї датуються 16 століттям. Назву їй дав Чарльз Бутон (Charles Bouton), який у 1901 році опублікував повний аналіз цієї гри.

Опис гри

Є кілька купок, у кожній — кілька каменів. За один хід гравець може взяти будь-яку додатну кількість каменів з однієї купки і викинути їх. Гравець програє, якщо не може зробити хід, що трапляється, коли всі купки порожні.

Стан гри однозначно описується мультимножиною додатних цілих чисел. Хід полягає у строгому зменшенні обраного числа (якщо воно стає нулем, його прибирають із множини).

Розв'язок

Розв'язок Чарльза Л. Бутона (Charles L. Bouton) виглядає так:

Теорема. Поточний гравець має виграшну стратегію тоді й лише тоді, коли XOR-сума розмірів купок ненульова. XOR-сума послідовності $a$ — це $a_1 \oplus a_2 \oplus \ldots \oplus a_n$, де $\oplus$ — це побітове виключне або.

Доведення. Ключем до доведення є наявність симетричної стратегії для суперника. Покажемо, що опинившись у позиції з XOR-сумою, рівною нулю, гравець не зможе зробити її ненульовою у довгостроковій перспективі — якщо він переходить у позицію з ненульовою XOR-сумою, суперник завжди матиме хід, який повертає XOR-суму назад у нуль.

Доведемо теорему методом математичної індукції.

Для порожнього німа (де всі купки порожні, тобто мультимножина порожня) XOR-сума дорівнює нулю, і теорема правдива.

Тепер припустимо, що ми перебуваємо у непорожньому стані. Користуючись припущенням індукції (та ациклічністю гри), ми вважаємо, що теорема доведена для всіх станів, досяжних із поточного.

Тоді доведення розпадається на дві частини: якщо для поточної позиції XOR-сума $s = 0$, ми маємо довести, що цей стан програшний, тобто всі досяжні стани мають XOR-суму $t \neq 0$. Якщо $s \neq 0$, ми маємо довести, що існує хід, який веде до стану з $t = 0$.

• Нехай $s = 0$ і розглянемо будь-який хід. Цей хід зменшує розмір купки $x$ до розміру $y$. Користуючись елементарними властивостями $\oplus$, маємо

  $$t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y$$

  Оскільки $y < x$, то $y \oplus x$ не може бути нулем, тому $t \neq 0$. Це означає, що будь-який досяжний стан є виграшним (за припущенням індукції), отже, ми перебуваємо у програшній позиції.

• Нехай $s \neq 0$. Розглянемо двійкове подання числа $s$. Нехай $d$ — індекс його старшого (найбільшого за значенням) ненульового біта. Наш хід буде з тієї купки, у розмірі якої встановлено біт номер $d$ (така купка має існувати, інакше цей біт не був би встановлений у $s$). Ми зменшимо її розмір $x$ до $y = x \oplus s$. Усі біти на позиціях, більших за $d$, у $x$ та $y$ збігаються, а біт $d$ встановлений у $x$, але не встановлений у $y$. Отже, $y < x$, а це все, що нам потрібно для того, щоб хід був дозволеним. Тепер маємо:

  $$t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0$$

  Це означає, що ми знайшли досяжний програшний стан (за припущенням індукції), а отже, поточний стан є виграшним.

Наслідок. Будь-який стан німа можна замінити еквівалентним станом, доки XOR-сума не змінюється. Більше того, аналізуючи нім із кількома купками, ми можемо замінити його однією купкою розміру $s$.

Гра misère

У грі misère мета гри протилежна, тому гравець, який забирає останню паличку, програє. Виявляється, що нім у режимі misère можна оптимально грати майже так само, як стандартний нім. Ідея в тому, щоб спочатку грати misère-гру як стандартну, але змінити стратегію наприкінці гри. Нова стратегія застосовується в ситуації, коли після наступного ходу кожна купка міститиме щонайбільше одну паличку. У стандартній грі ми маємо обрати хід, після якого буде парна кількість купок з однією паличкою. Однак у misère-грі ми обираємо хід так, щоб була непарна кількість купок з однією паличкою. Ця стратегія працює, бо стан, у якому стратегія змінюється, завжди виникає у грі, і цей стан є виграшним, оскільки він містить рівно одну купку, у якій більше ніж одна паличка, тож нім-сума не дорівнює 0.

Еквівалентність безсторонніх ігор та німа (теорема Шпрага–Гранді)

Тепер ми навчимося знаходити для будь-якого стану будь-якої безсторонньої гри відповідний стан німа.

Лема про нім зі збільшеннями

Розглянемо таку модифікацію німа: ми також дозволяємо додавати камені до обраної купки. Точні правила про те, як і коли дозволено збільшення, нас не цікавлять, однак ці правила мають залишати нашу гру ациклічною. У наступних розділах розглядаються приклади ігор.

Лема. Додавання збільшень до німа не змінює того, як визначаються виграшні та програшні стани. Іншими словами, збільшення марні, і нам не треба використовувати їх у виграшній стратегії.

Доведення. Припустимо, гравець додав камені до купки. Тоді його суперник може просто скасувати цей хід — зменшити кількість назад до попереднього значення. Оскільки гра ациклічна, рано чи пізно поточний гравець не зможе застосувати хід зі збільшенням і змушений буде зробити звичайний хід німа.

Теорема Шпрага–Гранді

Розглянемо стан $v$ безсторонньої гри двох гравців і нехай $v_i$ — стани, досяжні з нього (де $i \in \{ 1, 2, \dots, k \} , k \ge 0$). Цьому стану ми можемо зіставити повністю еквівалентну гру нім з однією купкою розміру $x$. Число $x$ називається числом Гранді (німбером) стану $v$.

Більше того, це число можна знайти таким рекурсивним способом:

$$x = \text{mex}\ \{ x_1, \ldots, x_k \},$$

де $x_i$ — це число Гранді для стану $v_i$, а функція $\text{mex}$ (minimum excludant) — це найменше невід'ємне ціле число, якого немає у заданій множині.

Розглядаючи гру як граф, ми можемо поступово обчислювати числа Гранді, починаючи з вершин без вихідних ребер. Те, що число Гранді дорівнює нулю, означає, що стан програшний.

Доведення. Скористаємося доведенням за індукцією.

Для вершин без ходу значення $x$ — це $\text{mex}$ порожньої множини, тобто нуль. Це правильно, оскільки порожній нім є програшним.

Тепер розглянемо будь-яку іншу вершину $v$. За індукцією ми вважаємо, що значення $x_i$, які відповідають її досяжним вершинам, уже обчислено.

Нехай $p = \text{mex}\ \{ x_1, \ldots, x_k \}$. Тоді ми знаємо, що для будь-якого цілого $i \in [0, p)$ існує досяжна вершина з числом Гранді $i$. Це означає, що $v$ еквівалентна стану гри нім зі збільшеннями з однією купкою розміру $p$. У такій грі ми маємо переходи до купок будь-якого розміру, меншого за $p$, і, можливо, переходи до купок із розмірами, більшими за $p$. Отже, $p$ дійсно є шуканим числом Гранді для стану, що розглядається.

Застосування теореми

Нарешті, опишемо алгоритм визначення результату (виграш/програш) гри, який застосовний до будь-якої безсторонньої гри двох гравців.

Щоб обчислити число Гранді заданого стану, потрібно:

• Отримати всі можливі переходи з цього стану

• Кожен перехід може вести до суми незалежних ігор (однієї гри у виродженому випадку). Обчислити число Гранді для кожної незалежної гри та взяти їхню XOR-суму. Звісно, XOR нічого не робить, якщо гра лише одна.

• Після того, як ми обчислили числа Гранді для кожного переходу, ми знаходимо значення стану як $\text{mex}$ цих чисел.

• Якщо значення дорівнює нулю, то поточний стан програшний, інакше — виграшний.

Порівняно з попереднім розділом, ми враховуємо те, що можуть бути переходи до комбінованих ігор. Ми розглядаємо їх як нім із розмірами купок, рівними числам Гранді незалежних ігор. Ми можемо взяти їхню XOR-суму так само, як у звичайному німі, згідно з теоремою Бутона.

Закономірності у числах Гранді

Дуже часто під час розв'язання конкретних задач за допомогою чисел Гранді буває корисно дослідити таблицю значень у пошуках закономірностей.

У багатьох іграх, які можуть здаватися доволі складними для теоретичного аналізу, числа Гранді виявляються періодичними або мають легко зрозумілий вигляд. У переважній більшості випадків помічена закономірність виявляється правдивою і за бажання може бути доведена за індукцією.

Однак числа Гранді далеко не завжди містять такі регулярності, і навіть для деяких дуже простих ігор задача про те, чи існують такі регулярності, досі відкрита (наприклад, «гра Гранді»).

Приклади ігор

Хрестики-хрестики

Правила. Розглянемо клітчасту смужку розміру $1 \times n$. За один хід гравець має поставити один хрестик, але заборонено ставити два хрестики поряд (у сусідніх клітинках). Як зазвичай, гравець, який не має дозволеного ходу, програє.

Розв'язок. Коли гравець ставить хрестик у будь-яку клітинку, ми можемо вважати, що смужка розбивається на дві незалежні частини: ліворуч від хрестика та праворуч від нього. При цьому клітинка з хрестиком, а також її лівий і правий сусіди знищуються — у них уже нічого не можна поставити. Тому, якщо ми пронумеруємо клітинки від $1$ до $n$, то постановка хрестика в позицію $1 < i < n$ розбиває смужку на дві смужки довжиною $i-2$ та $n-i-1$, тобто ми переходимо до суми ігор $i-2$ та $n-i-1$. Для крайового випадку, коли хрестик ставиться в позицію $1$ або $n$, ми переходимо до гри $n-2$.

Отже, число Гранді $g(n)$ має вигляд:

$$g(n) = \text{mex} \Bigl( \{ g(n-2) \} \cup \{g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1\} \Bigr) .$$

Так ми отримали розв'язок за $O(n^2)$.

Насправді $g(n)$ має період довжиною 34, починаючи з $n=52$.

Задачі для практики

• KATTIS S-Nim
• CodeForces - Marbles (2018-2019 ACM-ICPC Brazil Subregional)
• KATTIS - Cuboid Slicing Game
• HackerRank - Tower Breakers, Revisited!
• HackerRank - Tower Breakers, Again!
• HackerRank - Chessboard Game, Again!
• Atcoder - ABC368F - Dividing Game

Відеоматеріали