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

Функція Шпрага-Гранді широко використовується в теорії ігор для знаходження виграшної стратегії в комбінаційних іграх, наприклад, гра Нім. Ця функція визначається для ігор з двома гравцями, в яких програє той, який не має можливості зі своєї позиції зробити черговий крок. Теорема була незалежно сформульована й доведена Р. Шпрагом (1935) та П. М. Гранді (1939).

Означення

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

У будь-яку мить гри позиція гравця — це множина ходів, які йому дозволено зробити. Як приклад, ми можемо означити нульову гру як гру для двох гравців, де жоден гравець не має дозволених ходів. Позначаючи двох гравців як $A$ (для Аліси) і $B$ (для Боба), через те що множина ходів доступних кожному гравцеві порожня, ми позначаємо їхні позиції як $(A,B)=(\{\},\{\})$.

Безстороння гра — це така гра, в якій у будь-яку мить гри кожному гравцеві дозволено геть однаковий набір ходів. Звичайна гра нім це приклад безсторонньої гри. У німі є одна або кілька куп об’єктів, і два гравці (ми назвемо їх Алісою та Бобом), які по черзі вибирають купу та видаляють з неї 1 або більше об’єктів. Переможцем стає гравець, який видалить останній об’єкт із останньої купи. Гра безстороння (неупереджена), тому що для будь-якої заданої множини розмірів куп ходи, які може зробити Аліса якщо це її хід, точно такі ж, як і в Боба, якби це була його черга. Навпаки, така гра, як шашки, не безстороння (упереджена), бо, припустивши, що Аліса грає червоними, а Боб грає чорними, для будь-якого заданого розташування фігур на дошці, якби настала черга Аліси, їй було б дозволено рухати лише червоні шашки, а якби настала черга Боба, йому було б дозволено рухати лише чорні шашки.

Зауважте, що будь-яку конфігурацію неупередженої гри можна записати як одну позицію, бо ходи будуть однаковими незалежно від того, чий хід. Наприклад, позицію нульової гри можна просто записати $\{\}$, тому що якщо це черга Аліси, то вона не має ходів, і якщо це черга Боба, то в нього теж нема ходів. Хід можна прив'язати до позиції, в якій він залишає наступного гравця.

Це дозволяє визначати позиції рекурсивно. Наприклад, розглянемо наступну гру Нім, в яку грають Аліса та Боб.

Приклад гри нім

Розміри куп     Ходи
 A B C
  
 1 2 2           Аліса бере 1 з A
 0 2 2           Боб   бере 1 з B 
 0 1 2           Аліса бере 1 з C 
 0 1 1           Боб   бере 1 з B 
 0 0 1           Аліса бере 1 з C
 0 0 0           Боб   не має ходів, тож Аліса виграла

• На 6-му кроці гри (коли всі купи порожні) маємо позицію $\{\}$, тому що у Боба нема прийнятних ходів. Назвемо цю позицію $*0$.
• На 5-му кроці Аліса мала лише один варіант: видалити один об’єкт із купи C, не залишивши Бобу жодного можливого ходу. А що її хід залишає Боба в позиції $*0$, запишемо її позицію як $\{*0\}$, а назвемо цю позицію $*1$.
• На 4-му кроці у Боба було два варіанти: видалити один з B або видалити один з C. Однак зауважте, що насправді не мало значення, з якої купи Боб видалив об’єкт: у будь-якому разі Аліса залишилась би рівно з одним об’єктом у рівно одній купі. Отже, використовуючи наше рекурсивне означення, у Боба насправді є лише один хід: $*1$. Таким чином, позиція Боба така $\{*1\}$.
• На 3-му кроці Аліса мала 3 варіанти: видалити два з C, видалити один із C або видалити один із B. Видалення двох із C залишить Боба на місці $*1$ . Видалення одного з C залишає Боба з двома купками, кожна розміром один, тобто позицією $\{*1\}$, як описано в попередньому пункті. Однак, видалення 1 із B залишить Боба з двома об’єктами в одній купі. Його ходи тоді були б $*0$ і $*1$, тому її хід призведе до позиції $\{*0,*1\}$ . Ми називаємо цю позицію $*2$ . Тоді позиція Аліси є множиною всіх її ходів: ${\big \{}*1,\{*1\},*2{\big \}}$ .
• Дотримуючись тієї ж рекурсивної логіки, на 2-му кроці позиція Боба це
  $${\big \{}\{*1,\{*1\},*2\},*2{\big \}}.$$
• Нарешті, на 1-му кроці позиція Аліси така
  $${\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}.$$

Німсла

Особливі імена $*0$, $*1$, і $*2$ згадані в нашому прикладі гри називаються німслами. Загалом, німсло $*n$ відповідає позиції в німі, де наявно рівно $n$ об’єктів рівно в одній купі. Формально ці числа визначаються індуктивно таким чином: $*0$ це $\{\}$, $*1=\{*0\}$, $*2=\{*0,*1\}$ і для всіх $n\geq 0$, $*(n+1)=*n\cup \{*n\}$ .

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

Поєднання ігор

Дві гри можна поєднати, додавши їхні позиції. Наприклад, розглянемо іншу гру нім з купами $A'$, $B'$ і $C'$.

Приклад гри 2

Розміри куп      Ходи
 
A' B' C'
1  1  1           Аліса бере 1 from A'
0  1  1           Боб бере один з B'
0  0  1           Аліса бере один з C'
0  0  0           Боб не має ходів, тож Аліса виграла.

Ми можемо поєднати це з нашим першим прикладом, щоб отримати об'єднану гру зі шістьма купами: $A$, $B$, $C$, $A'$, $B'$ і $C'$:

Об'єднана гра

Розміри куп        Ходи
 A  B  C  A' B' C'  
  
 1  2  2  1  1  1   Аліса бере 1 з A
 0  2  2  1  1  1   Боб бере 1 з A'
 0  2  2  0  1  1   Аліса бере 1 з B'
 0  2  2  0  0  1   Боб бере 1 з C'
 0  2  2  0  0  0   Аліса бере 2 з B
 0  0  2  0  0  0   Боб бере 2 з C
 0  0  0  0  0  0   Аліса не має ходів, тож Боб виграв.

Щоб розрізнити дві ігри, для гри з першого прикладу ми позначимо її початкову позицію як $\color {blue}S$ і пофарбуємо її в синій колір:

$$\color {blue}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}$$

Для гри з другого прикладу ми позначимо початкову позицію як $\color {red}S'$ і пофарбуємо її в червоний колір:

$$\color {red}S'={\Big \{}\{*1\}{\Big \}}.$$

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

$$\color {blue}S\color {black}+\color {red}S'\color {black}={\Big \{}\color {blue}S\color {black}+\color {red}\{*1\}\color {black}{\Big \}}\cup {\Big \{}\color {red}S'\color {black}+\color {blue}\{*1,\{*1\},*2\}\color {black},\color {red}S'\color {black}+\color {blue}\{*2,\{*1,\{*1\},*2\}\}\color {black},\color {red}S'\color {black}+\color {blue}\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\color {black}{\Big \}}$$

Формула додавання позицій можна явно записати так $S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}$, що означає, що додавання як комутативне, так і асоціативне.

Еквівалентність

Позиції в неупереджених іграх поділяються на два наслідкові класи: або наступний гравець (той, чия черга) виграє (${\boldsymbol {\mathcal {N}}}$-позиція), або виграє попередній гравець (${\boldsymbol {\mathcal {P}}}$-позиція). Так, наприклад, $*0$ це ${\mathcal {P}}$-позиція, тоді як $*1$ це ${\mathcal {N}}$-позиція.

Дві позиції $G$ і $G'$ еквівалентні якщо, незалежно від позиції $H$ доданої до них, вони завжди опиняються в одному наслідковому класі. Формально, $G\approx G'$ тоді і тільки тоді, коли $\forall H$, $G+H$ перебуває в тому ж наслідковому класі, що й $G'+H$ .

Щоб скористатися нашими прикладами перебігу, зауважте, що як у першій, так і в другій іграх вище ми можемо показати, що на кожному кроці Аліса робить хід, який заводить Боба в ${\mathcal {P}}$-позицію. Таким чином, обидва $\color {blue}S$ і $\color {red}S'$ це ${\mathcal {N}}$-позиції. (Зауважте, що в об'єднаній грі Боб це гравець з ${\mathcal {N}}$-позиціями. Насправді, $\color {blue}S\color {black}+\color {red}S'$ це ${\mathcal {P}}$-позиція, яка, як ми побачимо в лемі 2, означає $\color {blue}S\color {black}\approx \color {red}S'$.)

Перша лема

Як проміжний крок до доведення основної теореми ми покажемо це для кожної позиції $G$ і кожної ${\mathcal {P}}$-позиції $A$, виконується $G\approx A+G$. Згідно з наведеним вище означенням рівнозначності, це означає показати, що $G+H$ і $A+G+H$ мають той самий наслідковий клас для всіх $H$.

Припустімо, що $G+H$ це ${\mathcal {P}}$-позиція. Тоді попередній гравець має виграшну стратегію для $A+G+H$: реагувати на рухи в $A$ відповідно до виграшної стратегії для $A$ (яка існує, бо $A$ це ${\mathcal {P}}$-позиція) і реагувати на рухи $G+H$ відповідно до виграшної стратегії для $G+H$ (що існує з аналогічної причини). Отже $A+G+H$ також має бути a ${\mathcal {P}}$-позицією.

З іншого боку, якщо $G+H$ це ${\mathcal {N}}$-позиція, то $A+G+H$ також ${\mathcal {N}}$-позиція, бо наступний гравець має виграшну стратегію: вибрати ${\mathcal {P}}$-позицію з числа варіантів у $G+H$, а з попереднього абзацу робимо висновок, що додавання $A$ до цієї позиції це все ще a ${\mathcal {P}}$ -позиція. Таким чином, в цьому випадку, $A+G+H$ має бути a ${\mathcal {N}}$-позицією, так само як $G+H$ .

А що це єдині два випадки, то лема доведена.

Друга лема

Як наступний крок ми показуємо, що $G\approx G'$ тоді і тільки тоді, коли $G+G'$ це ${\mathcal {P}}$-позиція.

Необхідність: Припустимо, що $G\approx G'$. Застосовуючи означення еквівалентності з $H=G$, ми знаходимо, що $G'+G$ (рівне $G+G'$ завдяки комутативності додавання) є в тому самому наслідковому класі, що й $G+G$ . Але $G+G$ має бути a ${\mathcal {P}}$-позицією: для кожного зробленого ходу в одній копії $G$, попередній гравець може відповісти тим самим ходом в іншій копії, тому завжди робить останній хід.

Достатність: А що $A=G+G'$ це ${\mathcal {P}}$-позиція за гіпотезою, то з першої леми випливає, що $G\approx G+A$, тобто $G\approx G+(G+G')$ . Так само, з того що $B=G+G$ також ${\mathcal {P}}$ -позиція, що випливає з першої леми у вигляді $G'\approx G'+B$, що $G'\approx G'+(G+G)$ . За асоціативністю та комутативністю праві частини цих результатів рівні. Крім того, $\approx$ це відношення еквівалентності, бо рівність це відношенням еквівалентності в наслідкових класах. Завдяки транзитивністі $\approx$, можна зробити висновок, що $G\approx G'$ .

Доведення

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

Розглянемо позицію $G=\{G_{1},G_{2},\ldots ,G_{k}\}$ . За індукційною гіпотезою всі варіанти еквівалентні німслам, скажімо, $G_{i}\approx *n_{i}$ . Тож нехай $G'=\{*n_{1},*n_{2},\ldots ,*n_{k}\}$ . Ми покажемо, що $G\approx *m$, де $m$ це mex (мінімальне виключення) чисел $n_{1},n_{2},\ldots ,n_{k}$, тобто найменше ціле невід’ємне число, яке не рівне жодному з $n_{i}$ .

Перше, що ми повинні зауважити, це те, що $G\approx G'$, згідно з другою лемою. Якщо $k$ дорівнює нулю, твердження є тривіально істинним. В іншому випадку розгляньте $G+G'$. Якщо наступний гравець переходить до $G_{i}$ в $G$, тоді попередній гравець може перейти до $*n_{i}$ в $G'$ і навпаки, якщо наступний гравець робить хід в $G'$. Отже, $G+G'$ це ${\mathcal {P}}$-позиція, і, посилаючись на доведення достатності леми, $G\approx G'$.

Тепер давайте покажемо, що $G'+*m$ це ${\mathcal {P}}$-позиція, що, використовуючи ще раз другу лему, означає, що $G'\approx *m$ . Ми зробимо це, явно даючи стратегію для попереднього гравця.

Припустимо, що $G'$ і $*m$ порожні. Тоді $G'+*m$ це нульова множина і очевидно ${\mathcal {P}}$-позиція.

Або розглянемо випадок, коли наступний гравець ходить у складнику $*m$ до варіанту $*m'$ де $m'<m$ . А що $m$ була мінімальною виключеною кількістю, попередній гравець може перейти в $G'$ до складника $*m'$ . І, як було показано раніше, будь-яка позиція плюс вона ж сама це ${\mathcal {P}}$-позиція.

Нарешті, припустимо, що наступний гравець переходить в $G'$ до варіанту $*n_{i}$ . Якщо $n_{i}<m$ тоді попередній гравець переходить з $*m$ до $*n_{i}$; інакше, якщо $n_{i}>m$, то попередній гравець переходить з $*n_{i}$ до $*m$; у будь-якому разі наслідок це сама позиція плюс вона ж. (Неможливо, щоб $n_{i}=m$, бо $m$ було визначене як відмінне від усіх $n_{i}$.)

Підсумовуючи, ми маємо $G\approx G'$ і $G'\approx *m$ . За транзитивністю висновуємо, що $G\approx *m$, що і треба було довести.

Гра «Нім»

Опис гри

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

Розв'язок

Розв'язок цієї гри опублікував у 1901 році Чарльз Бутон (Charles L. Bouton), і виглядає він так.

Теорема

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

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

Доведення

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

Доводити теорему будемо за допомогою математичної індукції.

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

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

Тоді доведення розпадається на дві частини: 1) якщо XOR-сума (s) в поточному стані рівна 0, то треба довести, що поточний стан є програшним, тобто всі переходи з нього ведуть в стану з XOR-сумою t != 0.

2) якщо s != 0, то треба довести, що знайдеться перехід, що приводить нас в стан з t = 0.