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

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

Означення

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

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

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

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

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

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

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

Німсла

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

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

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

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

Приклад гри 2

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

Ми можемо поєднати це з нашим першим прикладом, щоб отримати об'єднану гру зі шістьма купами: ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$, ${\displaystyle A'}$, ${\displaystyle B'}$ і ${\displaystyle 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 Аліса не має ходів, тож Боб виграв.

Щоб розрізнити дві ігри, для гри з першого прикладу ми позначимо її початкову позицію як ${\displaystyle \color {blue}S}$ і пофарбуємо її в синій колір:$${\displaystyle \color {blue}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}}$$Для гри з другого прикладу ми позначимо початкову позицію як ${\displaystyle \color {red}S'}$ і пофарбуємо її в червоний колір:$${\displaystyle \color {red}S'={\Big \{}\{*1\}{\Big \}}.}$$Щоб обчислити початкову позицію в об'єднаній грі, пам’ятайте, що гравець може або зробити хід у першій грі, залишивши другу гру недоторканою, або зробити хід у другій грі, залишивши першу гру недоторканою. Отже, початкова позиція комбінованої гри:$${\displaystyle \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 \}}}$$Формула додавання позицій можна явно записати так ${\displaystyle S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}}$, що означає, що додавання як комутативне, так і асоціативне.

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

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

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

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

Перша лема

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

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

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

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

Друга лема

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

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

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

Доведення

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

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

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

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

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

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

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

Підсумовуючи, ми маємо ${\displaystyle G\approx G'}$ і ${\displaystyle G'\approx *m}$ . За транзитивністю висновуємо, що ${\displaystyle 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.

Примітки

1. Sprague, R. (1936). Über mathematische Kampfspiele. Tohoku Mathematical Journal (German) . Т. 41. с. 438—444. ISSN 0040-8735. Процитовано 7 березня 2023.