Теорема Спрэга – Гранди

В комбинаторной теории игр теорема Спрэга -Грунди утверждает, что каждая беспристрастная игра в соответствии с соглашением о нормальной игре эквивалентна игре с одной кучей nim или бесконечному обобщению nim. Следовательно, его можно представить как натуральное число , размер кучи в эквивалентной ему игре «ним», как порядковое число в бесконечном обобщении, или, альтернативно, как нимбер , значение этой игры с одной кучей в алгебраической системе, Операция сложения объединяет несколько куч в одну эквивалентную кучу в nim.

Значение Гранди или значение нима любой беспристрастной игры — это уникальный номер, которому игра эквивалентна. В случае игры, позиции которой индексируются натуральными числами (как и сам nim, который индексируется по размерам кучи), последовательность нимберов для последовательных позиций игры называется ним-последовательностью игры.

Теорема Спрага-Грунди и ее доказательство воплощают основные результаты теории, открытой независимо Р. П. Спрэгом (1936). ^[1] и П.М. Гранди (1939). ^[2]

Определения

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

В любой момент игры позиция игрока — это набор ходов, которые ему разрешено сделать. В качестве примера мы можем определить нулевую игру как игру для двух игроков, в которой ни один из игроков не имеет допустимых ходов. Ссылаясь на двух игроков как $A$ (для Алисы) и $B$ (для Боба) мы бы обозначили их позиции как $(A,B)=(\{\},\{\})$ , поскольку набор ходов, которые может сделать каждый игрок, пуст.

Беспристрастная игра — это игра, в которой в любой момент игры каждому игроку разрешен одинаковый набор ходов. в обычной игре Ним является примером беспристрастной игры. В ним есть одна или несколько куч предметов, и два игрока (назовем их Алисой и Бобом) по очереди выбирают кучу и убирают из нее 1 или несколько предметов. Победителем становится тот игрок, который уберет последний предмет из финальной кучи. Игра беспристрастна , поскольку для любой заданной конфигурации размеров стопок ходы, которые Алиса может сделать в свой ход, — это точно такие же ходы, которые Бобу было бы разрешено сделать, если бы настал его ход. Напротив, такая игра, как шашки, не является беспристрастной, потому что, предположим, что Алиса играет красными, а Боб играет черными, для любого данного расположения фигур на доске, если бы наступила очередь Алисы, ей было бы разрешено перемещать только красные фигуры. , и если бы настала очередь Боба, ему было бы разрешено передвигать только черные фигуры.

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

Это позволяет определять позиции рекурсивно. Например, рассмотрим следующую игру «Ним», в которую играют Алиса и Боб.

Пример игры Ним

Sizes of heaps  Moves
 A B C
  
 1 2 2           Alice takes 1 from A
 0 2 2           Bob   takes 1 from B 
 0 1 2           Alice takes 1 from C 
 0 1 1           Bob   takes 1 from B 
 0 0 1           Alice takes 1 from C
 0 0 0           Bob   has no moves, so Alice wins

На шаге 6 игры (когда все стопки пусты) позиция $\{\}$ , потому что у Боба нет действительных ходов. Мы называем эту должность $*0$ .
На шаге 5 у Алисы был ровно один вариант: удалить один объект из кучи C, оставив Боба без ходов. Поскольку ее ход оставляет Боба на позиции $*0$ , ее позиция написана $\{*0\}$ . Мы называем эту должность $*1$ .
На шаге 4 у Боба было два варианта: удалить один из B или удалить один из C. Однако обратите внимание, что на самом деле не имело значения, из какой кучи Боб удалил объект: в любом случае у Алисы останется ровно один объект в ровно одна стопка. Итак, используя наше рекурсивное определение, у Боба действительно есть только один ход: $*1$ . Таким образом, позиция Боба такова: $\{*1\}$ .
На шаге 3 у Алисы было 3 варианта: удалить два из C, удалить один из C или удалить один из B. Удаление двух из C оставляет Боба на месте. $*1$ . Удаление одной стопки из C оставляет Бобу две стопки, каждая размером в единицу, т. е. позицию $\{*1\}$ , как описано в шаге 4. Однако удаление 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\}$ .

Хотя слово nimber происходит от игры nim , nimbers можно использовать для описания позиций в любой конечной, беспристрастной игре, и фактически теорема Спрэга–Грунди утверждает, что каждый случай конечной, беспристрастной игры может быть связан с одиночный нимбер.

Объединение игр

Две игры можно объединить, сложив их позиции. Например, рассмотрим еще одну игру в ним с кучами. $A'$ , $B'$ , и $C'$ .

Пример игры 2

Sizes of heaps    Moves
 
A' B' C'
1  1  1           Alice takes 1 from A'
0  1  1           Bob takes one from B'
0  0  1           Alice takes one from C'
0  0  0           Bob has no moves, so Alice wins.

Мы можем объединить его с нашим первым примером , чтобы получить комбинированную игру с шестью стопками: $A$ , $B$ , $C$ , $A'$ , $B'$ , и $C'$ :

Комбинированная игра

Sizes of heaps     Moves
 A  B  C  A' B' C'  
  
 1  2  2  1  1  1   Alice takes 1 from A
 0  2  2  1  1  1   Bob takes 1 from A'
 0  2  2  0  1  1   Alice takes 1 from B'
 0  2  2  0  0  1   Bob takes 1 from C'
 0  2  2  0  0  0   Alice takes 2 from B
 0  0  2  0  0  0   Bob takes 2 from C
 0  0  0  0  0  0   Alice has no moves, so Bob wins.

Чтобы различать эти две игры, для первой игры-примера мы обозначим ее начальную позицию $\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}}}$ - позиция ), или побеждает предыдущий игрок (a ${\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$ также должен быть ${\mathcal {P}}$ -позиция.

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

Поскольку это единственные два случая, лемма верна.

Вторая лемма

В качестве дальнейшего шага мы покажем, что $G\approx G'$ тогда и только тогда, когда $G+G'$ это ${\mathcal {P}}$ -позиция.

Предположим, что в прямом направлении $G\approx G'$ . Применяя определение эквивалентности с $H=G$ , мы находим это $G'+G$ (что равно $G+G'$ по коммутативности сложения) находится в том же классе результатов, что и $G+G$ . Но $G+G$ должно быть ${\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'$ . После этого позиция ${\mathcal {P}}$ -позиция по прямой импликации леммы. Поэтому, $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$ , по желанию.

Разработка

Если $G$ – позиция беспристрастной игры, единственное целое число $m$ такой, что $G\approx *m$ называется его значением Гранди, или числом Гранди, а функция, присваивающая это значение каждой такой позиции, называется функцией Спрага–Грунди. Р. Л. Спрэг и П. М. Гранди независимо друг от друга дали явное определение этой функции, не основанное на какой-либо концепции эквивалентности ним-позициям, и показали, что она обладает следующими свойствами:

Стоимость Гранди для одной стопки нимов размером $m$ (т.е. позиции $*m$ ) является $m$ ;
Позиция – это проигрыш следующего игрока, который сделает ход (т. ${\mathcal {P}}$ -позиция) тогда и только тогда, когда его значение Гранди равно нулю; и
Значение Гранди суммы конечного набора позиций - это просто нимм -сумма значений Гранди его слагаемых.

Из этих результатов непосредственно следует, что если позиция $G$ имеет значение Гранди $m$ , затем $G+H$ имеет то же значение Гранди, что и $*m+H$ , и, следовательно, принадлежит к одному и тому же классу результатов для любой позиции $H$ . Таким образом, хотя Спрэг и Гранди никогда явно не формулировали теорему, описанную в этой статье, она следует непосредственно из их результатов и принадлежит им. ^[3]^[4] Эти результаты впоследствии были развиты в области комбинаторной теории игр , в частности, Ричардом Гаем , Элвином Берлекэмпом , Джоном Хортоном Конвеем и другими, где они теперь заключены в теорему Спрага-Грунди и ее доказательство в форме, описанной здесь. Эта область представлена в книгах « Пути к победе в математических играх» и «О числах и играх» .

См. также

Ссылки

^ Спрэг, Р.П. (1936). «О математических файтингах» . Математический журнал Тохоку (на немецком языке). 41 : 438-444. ЖФМ 62.1070.03 . Например, 0013.29004 .
^ Гранди, премьер-министр (1939). «Математика и игры» . Эврика . 2 :6–8. Архивировано из оригинала 27 сентября 2007 г. Перепечатано, 1964, 27 : 9–11.
^ Смит, Седрик AB (1960), «Патрик Майкл Гранди, 1917–1959», Журнал Королевского статистического общества, серия A , 123 (2): 221–22.
^ Шлейхер, Дирк; Столл, Майкл (2006). «Введение в игры и числа Конвея». Московский математический журнал . 6 (2): 359–388. arXiv : math.CO/0410026 . дои : 10.17323/1609-4514-2006-6-2-359-388 . S2CID 7175146 .

Внешние ссылки

Игра Гранди в «разрубить узел»
Легко читаемый вводный отчет математического факультета Калифорнийского университета в Лос-Анджелесе.
Игра Ним на sputsoft.com
Милванг-Йенсен, Брит, Калифорния (2000), Комбинаторные игры, теория и приложения (PDF) , CiteSeerX 10.1.1.89.805

[SpraguePaper-1] Спрэг, Р.П. (1936). «О математических файтингах» . Математический журнал Тохоку (на немецком языке). 41 : 438-444. ЖФМ 62.1070.03 . Например, 0013.29004 .

[GrundyPaper-2] Гранди, премьер-министр (1939). «Математика и игры» . Эврика . 2 :6–8. Архивировано из оригинала 27 сентября 2007 г. Перепечатано, 1964, 27 : 9–11.

[3] Смит, Седрик AB (1960), «Патрик Майкл Гранди, 1917–1959», Журнал Королевского статистического общества, серия A , 123 (2): 221–22.

[4] Шлейхер, Дирк; Столл, Майкл (2006). «Введение в игры и числа Конвея». Московский математический журнал . 6 (2): 359–388. arXiv : math.CO/0410026 . дои : 10.17323/1609-4514-2006-6-2-359-388 . S2CID 7175146 .

[1]

[2]

[3]

[4]

v т и Темы теории игр
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Miscellaneous	Alpha–beta pruning Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons