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

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

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

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

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

Определения [ править ]

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

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

Беспристрастный игра является тот , в котором в любой данный момент в игре, каждый игрок имеет точно такой же набор движений. Нормаль-игра NIM является примером беспристрастных игр. В нем есть одна или несколько куч объектов, и два игрока (назовем их Алиса и Боб) по очереди выбирают кучу и удаляют из нее 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 оставляет Боба на месте . Удаление одного из 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 {\ Big \ {} {\ big \ {} * 1, \ {* 1 \}, * 2 {\ big \}}, {\ big \ {} * 2, \ {* 1, \ { * 1 \}, * 2 \} {\ big \}}, {\ big \ {} \ {* 1 \}, \ {\ {* 1 \} \}, \ {* 1, \ {* 1 \ }, * 2 \} {\ big \}} {\ Big \}}}$.

Нимберы [ править ]

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

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

Объединение игр [ править ]

Две игры можно объединить, сложив их позиции вместе. Например, рассмотрим еще одну игру NIM с кучами , и .${\ 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}}}}$${\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}$

Развитие [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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