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

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

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

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

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

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

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

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

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

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

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

Специальные имена , и , упомянутые в нашем примере игры, называются нимберами . В общем случае нимбер соответствует позиции в игре ним, где ровно объектов в ровно одной куче. Формально нимберы определяются индуктивно следующим образом: это , и для всех , .${\displaystyle *0}$${\displaystyle *1}$${\displaystyle *2}$${\displaystyle *н}$${\displaystyle n}$${\displaystyle *0}$${\displaystyle \{\}}$${\displaystyle *1=\{*0\}}$${\displaystyle *2=\{*0,*1\}}$${\displaystyle n\geq 0}$${\displaystyle *(n+1)=*n\чашка \{*n\}}$

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

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

Размеры куч Ходы А' Б' В'1 1 1 Алиса берет 1 из A'0 1 1 Боб берет один из B'0 0 1 Алиса берет один из C'0 0 0 У Боба нет ходов, поэтому Алиса выигрывает.

Мы можем объединить его с нашим первым примером, чтобы получить комбинированную игру с шестью кучами: , , , , , и :${\displaystyle А}$${\displaystyle Б}$${\displaystyle С}$${\displaystyle А'}$${\displaystyle B'}$${\displaystyle 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 {синий}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 {красный}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}$

Чтобы использовать наши текущие примеры, обратите внимание, что и в первой, и во второй игре выше мы можем показать, что на каждом ходу у Алисы есть ход, который заставляет Боба занять -позицию. Таким образом, и являются -позициями. (Обратите внимание, что в объединенной игре Боб является игроком с -позициями. Фактически, является -позицией, что, как мы увидим в Лемме 2, означает .)${\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}}}$${\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'}$

Мы доказываем, что все позиции эквивалентны нимберу с помощью структурной индукции . Более конкретный результат, что начальная позиция данной игры должна быть эквивалентна нимберу, показывает, что сама игра эквивалентна нимберу.

Рассмотрим позицию . По предположению индукции все варианты эквивалентны числам, скажем . Итак, пусть . Покажем, что , где — mex (минимальное исключение) чисел , то есть наименьшее неотрицательное целое число, не равное некоторому .${\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}$${\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}}}$
• Значение Гранди суммы конечного набора позиций — это просто ним-сумма значений Гранди ее слагаемых.

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

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

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