В комбинаторной теории игр , в Спрэге-Гранди теорема утверждает , что каждая беспристрастная игра под нормальной игровой конвенцией эквивалентна одной кучи игры NIM , или к бесконечному обобщении NIM. Следовательно, его можно представить как натуральное число , размер кучи в эквивалентной ему игре ним, как порядковое число в бесконечном обобщении, или, альтернативно, как нимбер , значение этой игры с одной кучей в алгебраической системе, чья операция сложения объединяет несколько куч, чтобы сформировать единую эквивалентную кучу в ним.
Гранди значение или NIM-значение любых беспристрастных игр является уникальным Nimber , что игра эквивалентна. В случае игры, позиции которой индексируются натуральными числами (например, сам ним, который индексируется размером его кучи), последовательность нимберов для последовательных позиций в игре называется ним-последовательностью игры.
Теорема Спрэга – Гранди и ее доказательство заключают в себе основные результаты теории, независимо открытой Р.П. Спрагом (1935) [1] и П.М. Гранди (1939). [2]
Определения
Для целей теоремы Спрага-Гранди игра - это последовательная игра двух игроков с идеальной информацией, удовлетворяющая конечному условию (все игры подходят к концу: нет бесконечных игровых линий) и условию нормальной игры (игрок кто не может двигаться проигрывает).
В любой момент игры позиция игрока - это набор ходов, которые ему разрешено делать. В качестве примера мы можем определить нулевую игру как игру для двух игроков, в которой ни один из игроков не имеет допустимых ходов. Ссылаясь на двух игроков как на (для Алисы) и (для Боба) мы бы обозначили их позиции как , поскольку набор ходов, который может сделать каждый игрок, пуст.
Беспристрастный игра является тот , в котором в любой данный момент в игре, каждый игрок имеет точно такой же набор движений. Нормаль-игра NIM является примером беспристрастных игр. В нем есть одна или несколько куч объектов, и два игрока (назовем их Алиса и Боб) по очереди выбирают кучу и удаляют из нее 1 или несколько объектов. Победителем становится игрок, убравший последний объект из последней кучи. Игра беспристрастна, потому что при любой конфигурации размеров стопки ходы, которые Алиса может делать в свой ход, точно такие же, как Бобу было бы позволено сделать, если бы это был его ход. Напротив, такая игра, как шашки , не является беспристрастной, потому что, предположим, что Алиса играет красным, а Боб - черным, для любого заданного расположения фигур на доске, если бы была очередь Алисы, ей было бы разрешено перемещать только красные фигуры , и если бы настала очередь Боба, ему было бы разрешено двигать только черными фигурами.
Обратите внимание, что любую конфигурацию беспристрастной игры можно записать как одну позицию, потому что ходы будут одинаковыми независимо от того, чей это ход. Например, позицию нулевой игры можно просто записать, потому что, если сейчас очередь Алисы, ей нечего делать, а если сейчас очередь Боба, у него тоже нет ходов. Ход может быть связан с позицией, в которой он оставляет следующего игрока.
Это позволяет рекурсивно определять позиции. Например, рассмотрим следующую игру «Ним», в которую играют Алиса и Боб.
Пример игры 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 игры (когда все кучи пусты) позиция , потому что у Боба нет допустимых ходов. Мы называем эту позицию.
- На шаге 5 у Алисы был только один вариант: удалить один объект из кучи C, оставив Боба без ходов. Поскольку ее ход оставляет Боба на месте, ее позиция написана. Мы называем эту позицию.
- На шаге 4 у Боба было два варианта: удалить один из B или удалить один из C. Однако обратите внимание, что на самом деле не имело значения, из какой кучи Боб удалил объект: в любом случае у Алисы останется ровно один объект в ровно одна стопка. Итак, используя наше рекурсивное определение, у Боба действительно есть только один ход:. Таким образом, позиция Боба такова..
- На шаге 3 у Алисы было 3 варианта: удалить два из C, удалить один из C или удалить один из B. Удаление двух из C оставляет Боба на месте. . Удаление одной из C оставляет у Боба две стопки, каждая размером один, т. Е. Положение, как описано в шаге 4. Однако удаление 1 из B оставит Бобу с двумя объектами в одной стопке. Его движения тогда были бы а также , поэтому ее ход приведет к позиции. Мы называем эту позицию. Позиция Алисы - это набор всех ее ходов:.
- Следуя той же рекурсивной логике, на шаге 2 позиция Боба .
- Наконец, на шаге 1 позиция Алисы равна
.
Нимберы
Особые имена , , а также упомянутые в нашем примере игры называются « Нимберами» . В общем шустрый соответствует позиции в игре ним, где ровно объекты ровно в одну кучу. Формально нимберы индуктивно определяются следующим образом: является , , и для всех , .
Хотя слово NIM бер приходит из игры NIM , nimbers может быть использован для описания положения любого конечного, беспристрастной игры, и в самом деле, Спрэг-Гранди состояния теоремы , что каждый экземпляр конечных, беспристрастная игра может быть связана с одиночка .
Объединение игр
Две игры можно объединить, сложив их позиции вместе. Например, рассмотрим другую игру ним с кучей, , а также .
Пример игры 2
Размеры отвала Ходы A 'B' C '1 1 1 Алиса берет 1 из A '0 1 1 Боб берет один из B '0 0 1 Алиса берет одну из C '0 0 0 У Боба нет ходов, поэтому Алиса выигрывает.
Мы можем объединить это с нашим первым примером, чтобы получить комбинированную игру с шестью кучами:, , , , , а также :
Комбинированная игра
Размеры отвала Ходы 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 У Алисы нет ходов, поэтому Боб выигрывает.
Чтобы различать эти две игры, для первого примера мы обозначим его начальную позициюи раскрасьте его в синий цвет:
Во втором примере игры мы обозначим начальную позицию и раскрасьте его в красный цвет:
.
Чтобы вычислить начальную позицию комбинированной игры , помните, что игрок может сделать ход в первой игре, оставив вторую игру нетронутой, или сделать ход во второй игре, оставив первую игру нетронутой. Итак, стартовая позиция комбинированной игры:
Явная формула для добавления позиций: , что означает, что сложение одновременно коммутативно и ассоциативно.
Эквивалентность
Позиции в беспристрастных играх делятся на два класса исходов : либо побеждает следующий игрок (тот, чья очередь идет) (- позиция ), либо предыдущий игрок побеждает (a- положение ). Так, например, это -позиция, а является -должность.
Две позиции а также являются эквивалентными , если, независимо от того , какой позициидобавляется к ним, они всегда находятся в одном классе результатов. Формально, если и только если , находится в том же классе результатов, что и .
Чтобы использовать наши рабочие примеры, обратите внимание, что как в первой, так и во второй играх, описанных выше, мы можем показать, что на каждом ходу Алиса делает ход, который заставляет Боба-должность. Таким образом, оба а также находятся -позиции. (Обратите внимание, что в комбинированной игре Боб является игроком с-позиции. По факту, это -положение, которое, как мы увидим в лемме 2, означает .)
Первая лемма
В качестве промежуточного шага к доказательству основной теоремы покажем, что для каждой позиции и каждый -должность , эквивалентность держит. По приведенному выше определению эквивалентности это означает, что а также поделиться классом результатов для всех .
Предположим, что это -должность. Тогда у предыдущего игрока есть выигрышная стратегия для: реагировать на шаги в в соответствии с их выигрышной стратегией для (который существует в силу быть -позиция) и реагировать на движения в в соответствии с их выигрышной стратегией для (который существует по аналогичной причине). Так также должен быть -должность.
С другой стороны, если является -позиция, то также -позиция, потому что у следующего игрока есть выигрышная стратегия: выберите -позиция из числа варианты, и мы делаем вывод из предыдущего абзаца, что добавление на эту позицию по-прежнему -должность. Таким образом, в этом случае должен быть -позиция, как и .
Поскольку это только два случая, лемма верна.
Вторая лемма.
В качестве дальнейшего шага покажем, что если и только если это -должность.
В прямом направлении предположим, что . Применяя определение эквивалентности с, мы находим, что (что равно от коммутативности сложения) находится в том же классе , как итоговый. Но должен быть -позиция: за каждый сделанный ход в одном экземпляре , предыдущий игрок может ответить тем же ходом в другой копии, и поэтому всегда будет делать последний ход.
В обратном направлении, поскольку это -позиция по условию следует из первой леммы, , что . Аналогично, поскольку также -позиции следует из первой леммы в виде что . По ассоциативности и коммутативности правые части этих результатов равны. Более того,является отношением эквивалентности, потому что равенство является отношением эквивалентности для классов результатов. Через транзитивности из, можно сделать вывод, что .
Доказательство
Мы доказываем, что все позиции эквивалентны нимберу, методом структурной индукции . Более конкретный результат, что начальная позиция данной игры должна быть эквивалентна нимберу, показывает, что сама игра эквивалентна нимберу.
Рассмотрим позицию . По предположению индукции, все варианты эквивалентны нимберам, скажем,. Так что давайте. Мы покажем, что, где это мексика (минимальное исключение) чисел, то есть наименьшее целое неотрицательное число, не равное некоторому .
Первое, что нам нужно отметить, это то, что , согласно второй лемме. Еслиравен нулю, утверждение тривиально верно. В противном случае рассмотрите. Если следующий игрок делает ход на в , то предыдущий игрок может перейти на в , и наоборот, если следующий игрок сделает ход в . После этого позиция становится-позиция по прямой импликации леммы. Следовательно, это -позиция, и, ссылаясь на обратную импликацию леммы, .
Теперь покажем, что это -позиция, что, еще раз используя вторую лемму, означает, что . Мы делаем это, давая явную стратегию предыдущему игроку.
Предположим, что а также пусты. потом является нулевым набором, очевидно, -должность.
Или рассмотрим случай, когда следующий игрок перемещается в компоненте к варианту где . Так какбыло минимальным исключенным числом, предыдущий игрок может перейти в к . И, как было показано ранее, любая позиция плюс сама по себе является-должность.
Наконец, предположим, что следующий игрок перемещается в компоненте к варианту . Если тогда предыдущий игрок переходит в к ; в противном случае, если, предыдущий игрок заходит к ; в любом случае результат - это позиция плюс сама себя. (Это невозможно, чтобы так как был определен как отличный от всех .)
Таким образом, у нас есть а также . По транзитивности заключаем, что, по желанию.
Разработка
Если позиция беспристрастной игры, единственное целое число такой, что называется его значением Гранди или числом Гранди, а функция, которая присваивает это значение каждой такой позиции, называется функцией Спрага – Гранди. Р.Л. Спраг и П.М. Гранди независимо друг от друга дали явное определение этой функции, не основанное на какой-либо концепции эквивалентности ним позиций, и показали, что она обладает следующими свойствами:
- Ценность Гранди одной кучи ним размером (т.е. позиции ) является ;
- Позиция - это проигрыш для следующего игрока (т. Е. -position) тогда и только тогда, когда его значение Grundy равно нулю; а также
- Значение Гранди суммы конечного набора позиций - это всего лишь ним-сумма значений Гранди его слагаемых.
Из этих результатов прямо следует, что если позиция имеет значение Гранди, равное , тогда имеет то же значение Гранди, что и , и, следовательно, принадлежит к одному классу результатов для любой позиции . Таким образом, хотя Спраг и Гранди никогда явно не формулировали теорему, описанную в этой статье, она непосредственно следует из их результатов и им приписывается. [3] [4] Эти результаты впоследствии были развиты в области комбинаторной теории игр , в частности Ричардом Гаем , Элвином Берлекэмпом , Джоном Хортоном Конвеем и другими, где они теперь заключены в теорему Спрэга – Гранди и ее доказательство в форма описана здесь. Поле представлено в книгах « Выигрышные способы для ваших математических игр» и « О числах и играх» .
Смотрите также
Рекомендации
- Перейти ↑ Sprague, RP (1935–36). "Uber Mathematische Kampfspiele" . Математический журнал Тохоку . 41 : 438–444.
- ^ Гранди, PM (1939). «Математика и игры» . Эврика . 2 : 6–8. Архивировано из оригинала на 2007-09-27.Перепечатано, 1964 г., 27 : 9–11.
- ^ Смит, Седрик А.Б. (1960), «Патрик Майкл Гранди, 1917–1959», Журнал Королевского статистического общества, серия A , 123 (2): 221–22
- ^ Шлейхер, Дирк; Столл, Майкл (2006). «Введение в игры и числа Конвея». Московский математический журнал . 6 (2): 359–388. arXiv : math.CO/0410026 . DOI : 10.17323 / 1609-4514-2006-6-2-359-388 .
Внешние ссылки
- Игра Гранди на пороге
- Легко читаемый вводный отчет от математического факультета Калифорнийского университета в Лос-Анджелесе
- Игра Нима на sputsoft.com
- Milvang-Jensen, Brit CA (2000), Комбинаторные игры, теория и приложения (PDF) , CiteSeerX 10.1.1.89.805