Теорема Спрага – Гранди - Sprague–Grundy theorem

В комбинаторная теория игр, то Теорема Спрага – Гранди заявляет, что каждый беспристрастная игра под обычная игровая конвенция эквивалентно игре с одной кучей ним, или до бесконечного обобщения ним. Поэтому его можно представить как натуральное число, размер кучи в эквивалентной игре нима, как порядковый номер в бесконечном обобщении или, альтернативно, как проворный, значение этой игры с одной кучей в алгебраической системе, операция сложения которой объединяет несколько куч, чтобы сформировать единую эквивалентную кучу в ним.

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

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

Определения

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

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

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

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

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

Пример игры Nim

Размеры кучи Перемещения ABC 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\}}$, как описано в шаге 4. Однако удаление 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 из A'0 1 1 Боб берет один из B'0 0 1 Алиса берет один из C'0 0 0 У Боба нет ходов, поэтому Алиса выигрывает.

Мы можем совместить это с нашим первый пример чтобы получить комбинированную игру с шестью кучками: ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$, ${\displaystyle A'}$, ${\displaystyle B'}$, и ${\displaystyle C'}$:

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

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

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

Разработка

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

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

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

Смотрите также

• Теория родов
• Коэффициент неразличимости

Рекомендации

1. Спраг, Р. П. (1935–36). "Uber Mathematische Kampfspiele". Математический журнал Тохоку. 41: 438–444.
2. Гранди, П. М. (1939). «Математика и игры». Эврика. 2: 6–8. Архивировано из оригинал на 2007-09-27. Переиздано, 1964 г., 27: 9–11.
3. Смит, Седрик А. (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.

внешняя ссылка

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