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

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

Означення

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

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

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

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

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

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

• На 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$ . Тоді позиція Аліси є множиною всіх її ходів: $\{*1,\{*1\},*2\}$ .
• Дотримуючись тієї ж рекурсивної логіки, на 2-му кроці позиція Боба це $$\{\{*1,\{*1\},*2\},*2\}.$$
• Нарешті, на 1-му кроці позиція Аліси така $$\left\{\right\{*1,\{*1\},*2\},\{*2,\{*1,\{*1\},*2\}\},\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\left\}\right\}.$$

Німсла

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

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

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

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

Приклад гри 2

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

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

Шаблон:Pre Щоб розрізнити дві ігри, для гри з першого прикладу ми позначимо її початкову позицію як $S$ і пофарбуємо її в синій колір:$$S=\{\{*1,\{*1\},*2\},\{*2,\{*1,\{*1\},*2\}\},\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\}$$Для гри з другого прикладу ми позначимо початкову позицію як $S^{\prime }$ і пофарбуємо її в червоний колір:$$S^{\prime }=\{\{*1\}\}.$$Щоб обчислити початкову позицію в об'єднаній грі, пам’ятайте, що гравець може або зробити хід у першій грі, залишивши другу гру недоторканою, або зробити хід у другій грі, залишивши першу гру недоторканою. Отже, початкова позиція комбінованої гри:$$S+S^{\prime }=\{S+\{*1\}\}\cup \{S^{\prime }+\{*1,\{*1\},*2\},S^{\prime }+\{*2,\{*1,\{*1\},*2\}\},S^{\prime }+\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\}$$Формула додавання позицій можна явно записати так $S+S^{\prime }=\{S+s^{\prime }\mid s^{\prime }\in S^{\prime }\}\cup \{s+S^{\prime }\mid s\in S\}$, що означає, що додавання як комутативне, так і асоціативне.

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

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

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

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

Перша лема

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

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

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

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

Друга лема

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

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

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

Доведення

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

Розглянемо позицію $G=\{G_1,G_2,\dots ,G_k\}$ . За індукційною гіпотезою всі варіанти еквівалентні німслам, скажімо, $G_i\approx *n_i$ . Тож нехай $G^{\prime }=\{*n_1,*n_2,\dots ,*n_k\}$ . Ми покажемо, що $G\approx *m$, де $m$ це mex (мінімальне виключення) чисел $n_1,n_2,\dots ,n_k$, тобто найменше ціле невід’ємне число, яке не рівне жодному з $n_i$ .

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

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

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

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

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

Підсумовуючи, ми маємо $G\approx G^{\prime }$ і $G^{\prime }\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.