Введение
Каждая беспристрастная позиция в игре эквивалентна позиции в игре ним.
В комбинаторной теории игр теорема Спрага — Гранди утверждает, что любая беспристрастная игра при стандартных правилах игры эквивалентна игре в ним с одной кучей или бесконечному обобщению игры в ним. Следовательно, её можно представить в виде натурального числа, равного размеру кучи в эквивалентной игре в ним, в виде порядкового числа в бесконечном обобщении, или, альтернативно, в виде нимбера – значения этой игры с одной кучей в алгебраической системе, где операция сложения объединяет несколько куч в одну эквивалентную кучу в игре ним. Значение Грунди, или ним-значение, любой беспристрастной игры — это уникальный нимбер, которому эта игра эквивалентна. В случае игры, позиции которой индексируются натуральными числами (как, например, сама игра ним, индексируемая размерами её куч), последовательность нимберов для последовательных позиций игры называется ним-последовательностью этой игры. Теорема Спрага — Гранди и её доказательство обобщают основные результаты теории, открытой независимо друг от друга Р. П. Спрагом (1936) и П. М. Гранди (1939).
Определения
Для целей теоремы Спрага–Гранди игра — это последовательная игра двух игроков с полной информацией, удовлетворяющая условию завершения (все игры заканчиваются: нет бесконечных вариантов развития игры) и нормальному условию игры (игрок, который не может сделать ход, проигрывает). В любой момент игры позиция игрока — это множество допустимых для него ходов. В качестве примера можно определить нулевую игру как игру для двух игроков, где ни у одного из них нет допустимых ходов. Обозначая двух игроков как (для Алисы) и (для Боба), мы будем обозначать их позиции как , поскольку множество ходов, доступных каждому игроку, пусто. Беспристрастная игра — это игра, в которой в любой момент игры каждому игроку доступно одно и то же множество ходов. Нормальный ним — пример беспристрастной игры. В ниме есть одна или несколько куч объектов, и два игрока (назовем их Алисой и Бобом) по очереди выбирают кучу и удаляют из нее один или несколько объектов. Победителем становится игрок, удаливший последний объект из последней кучи. Игра беспристрастна, поскольку для любой заданной конфигурации размеров куч ходы, которые может сделать Алиса в свой ход, точно такие же, как те, которые Боб мог бы сделать, если бы был его ход. В отличие от этого, игра в шашки не является беспристрастной, поскольку, предположим, Алиса играет красными, а Боб — черными, то для любого расположения фигур на доске, если ход Алисы, она может перемещать только красные фигуры, а если ход Боба, он может перемещать только черные фигуры. Важно отметить, что любую конфигурацию беспристрастной игры можно представить как одну позицию, поскольку ходы будут одинаковыми независимо от того, чей ход. Например, позицию нулевой игры можно просто записать как , поскольку, если ход Алисы, она не может сделать ход, и если ход Боба, он также не может сделать ход. Ход можно связать с позицией, в которую он переводит следующего игрока. Это позволяет определять позиции рекурсивно. Например, рассмотрим следующую игру в ним, которую играют Алиса и Боб.
Нимберы
Специальные имена, , и , упомянутые в нашей примерной игре, называются нимберами. В общем случае, нимбер соответствует позиции в игре ним, где есть ровно объектов в ровно одной куче. Формально нимберы определяются индуктивно следующим образом: = , = , и для всех , . Хотя слово "нимбер" происходит от игры ним, нимберы могут использоваться для описания позиций любой конечной, беспристрастной игры, и, фактически, теорема Спрага — Гранди утверждает, что каждый экземпляр конечной, беспристрастной игры может быть соотнесен с одним нимбером.
While the word nimber comes from the game nim, nimbers can be used to describe the positions of any finite, impartial game, and in fact, the Sprague–Grundy theorem states that every instance of a finite, impartial game can be associated with a single nimber.
Комбинирующие игры
Две игры можно объединить, сложив их позиции. Например, рассмотрим другую игру ним с кучами , , и .
Первая лемма
В качестве промежуточного шага к доказательству основной теоремы, мы показываем, что для каждой позиции и каждой позиции , выполняется эквивалентность . Согласно определению эквивалентности, это сводится к доказательству того, что и имеют общий класс исходов для всех . Предположим, что является позицией. Тогда предыдущий игрок имеет выигрышную стратегию для : отвечать на ходы в соответствии со своей выигрышной стратегией для (которая существует, поскольку является позицией), и отвечать на ходы в соответствии со своей выигрышной стратегией для (которая существует по аналогичной причине). Следовательно, также должна быть позицией. С другой стороны, если является позицией, то также является позицией, потому что у следующего игрока есть выигрышная стратегия: выбрать позицию из числа доступных вариантов, и из предыдущего абзаца следует, что добавление к этой позиции все еще дает позицию. Таким образом, в этом случае также должна быть позицией, как и . Поскольку это единственные два возможных случая, лемма доказана.
Suppose that is a position. Then the previous player has a winning strategy for : respond to moves in according to their winning strategy for (which exists by virtue of being a position), and respond to moves in according to their winning strategy for (which exists for the analogous reason). So must also be a position. On the other hand, if is an position, then is also an position, because the next player has a winning strategy: choose a position from among the options, and we conclude from the previous paragraph that adding to that position is still a position. Thus, in this case, must be a position, just like
As these are the only two cases, the lemma holds.
Вторая лемма
Далее мы покажем, что ⇔ является позицией. В прямом направлении, предположим, что . Применяя определение эквивалентности с , мы находим, что (что равно по коммутативности сложения) находится в том же классе исходов, что и . Но должно быть позицией: для каждого хода, сделанного в одной копии , предыдущий игрок может ответить тем же ходом в другой копии, и таким образом всегда делать последний ход. В обратном направлении, поскольку по гипотезе является позицией, из первой леммы следует, что . Аналогично, поскольку также является позицией, из первой леммы в форме следует, что . По ассоциативности и коммутативности, правые части этих равенств равны. Более того, является отношением эквивалентности, поскольку равенство является отношением эквивалентности на классах исходов. Благодаря транзитивности , мы можем заключить, что .
Доказательство
Мы докажем, что все позиции эквивалентны нимберу, используя структурную индукцию. Более конкретный результат, заключающийся в том, что начальная позиция данной игры должна быть эквивалентна нимберу, показывает, что сама игра эквивалентна нимберу. Рассмотрим позицию. По гипотезе индукции, все варианты эквивалентны нимберам, скажем S₀. Пусть мы покажем, что P = mex(S₀), где mex – это минимальное исключенное число из множества S₀, то есть наименьшее неотрицательное целое число, не равное ни одному из чисел в S₀.
The first thing we need to note is that , by way of the second lemma. If is zero, the claim is trivially true. Otherwise, consider If the next player makes a move to in , then the previous player can move to in , and conversely if the next player makes a move in After this, the position is a position by the lemma's forward implication. Therefore, is a position, and, citing the lemma's reverse implication,
Now let us show that is a position, which, using the second lemma once again, means that We do so by giving an explicit strategy for the previous player. Suppose that and are empty. Then is the null set, clearly a position. Or consider the case that the next player moves in the component to the option where Because was the minimum excluded number, the previous player can move in to And, as shown before, any position plus itself is a position. Finally, suppose instead that the next player moves in the component to the option If then the previous player moves in to ; otherwise, if , the previous player moves in to ; in either case the result is a position plus itself. (It is not possible that because was defined to be different from all the .) In summary, we have and By transitivity, we conclude that , as desired.
Первое, что нужно отметить, это P > 0, согласно второй лемме. Если P равно нулю, утверждение тривиально верно. В противном случае рассмотрим P. Если следующий игрок делает ход в позицию Q из P, то предыдущий игрок может перейти в позицию Q' из P, и наоборот, если следующий игрок делает ход из P в Q. После этого позиция Q является проигрышной (N-позицией) по прямой импликации леммы. Следовательно, P – выигрышная (P-позиция), и, ссылаясь на обратную импликацию леммы, P = Q + 1.
The first thing we need to note is that , by way of the second lemma. If is zero, the claim is trivially true. Otherwise, consider If the next player makes a move to in , then the previous player can move to in , and conversely if the next player makes a move in After this, the position is a position by the lemma's forward implication. Therefore, is a position, and, citing the lemma's reverse implication,
Now let us show that is a position, which, using the second lemma once again, means that We do so by giving an explicit strategy for the previous player. Suppose that and are empty. Then is the null set, clearly a position. Or consider the case that the next player moves in the component to the option where Because was the minimum excluded number, the previous player can move in to And, as shown before, any position plus itself is a position. Finally, suppose instead that the next player moves in the component to the option If then the previous player moves in to ; otherwise, if , the previous player moves in to ; in either case the result is a position plus itself. (It is not possible that because was defined to be different from all the .) In summary, we have and By transitivity, we conclude that , as desired.
Теперь покажем, что P – выигрышная позиция, что, используя вторую лемму еще раз, означает, что P > 0. Мы делаем это, предоставив явную стратегию для предыдущего игрока. Предположим, что S₀ и S₁ пустые. Тогда S₀ – пустое множество, очевидно, являющееся проигрышной позицией. Или рассмотрим случай, когда следующий игрок переходит в компонент i к варианту Q, где Q < P. Поскольку P было минимальным исключенным числом, предыдущий игрок может перейти в компонент i к варианту P ⊕ Q. И, как показано ранее, любая позиция, сложенная с самой собой, является проигрышной позицией. Наконец, предположим, что следующий игрок переходит в компонент i к варианту Q. Если Q < P, то предыдущий игрок переходит в компонент i к варианту P ⊕ Q; в противном случае, если Q = P, предыдущий игрок переходит в компонент i к варианту Q ⊕ P; в любом случае результат – проигрышная позиция, сложенная с самой собой. (Это невозможно, поскольку P было определено как отличное от всех чисел в S₀.) В итоге мы имеем P = Q + 1 и Q = P ⊕ Q. По транзитивности мы заключаем, что P = P ⊕ Q, как и требовалось.
The first thing we need to note is that , by way of the second lemma. If is zero, the claim is trivially true. Otherwise, consider If the next player makes a move to in , then the previous player can move to in , and conversely if the next player makes a move in After this, the position is a position by the lemma's forward implication. Therefore, is a position, and, citing the lemma's reverse implication,
Now let us show that is a position, which, using the second lemma once again, means that We do so by giving an explicit strategy for the previous player. Suppose that and are empty. Then is the null set, clearly a position. Or consider the case that the next player moves in the component to the option where Because was the minimum excluded number, the previous player can move in to And, as shown before, any position plus itself is a position. Finally, suppose instead that the next player moves in the component to the option If then the previous player moves in to ; otherwise, if , the previous player moves in to ; in either case the result is a position plus itself. (It is not possible that because was defined to be different from all the .) In summary, we have and By transitivity, we conclude that , as desired.
Разработка
Если позиция является позицией беспристрастной игры, то уникальное целое число *g*, такое что *g* = mex(*N*(p)), называется значением Грунди, или числом Грунди этой позиции, а функция, которая присваивает это значение каждой такой позиции, называется функцией Спрага — Грунди. Р. Л. Спраг и П. М. Грунди независимо дали явное определение этой функции, не основанное на какой-либо концепции эквивалентности позициям ним, и показали, что она обладает следующими свойствами:
The Grundy value of a single nim pile of size (i. e. of the position ) is ;
A position is a loss for the next player to move (i. e. a position) if and only if its Grundy value is zero; and
The Grundy value of the sum of a finite set of positions is just the nim sum of the Grundy values of its summands. It follows straightforwardly from these results that if a position has a Grundy value of , then has the same Grundy value as , and therefore belongs to the same outcome class, for any position Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them. These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.
Значение Грунди одной кучи ним размера *n* (т. е. позиции *n*) равно *n*;
The Grundy value of a single nim pile of size (i. e. of the position ) is ;
A position is a loss for the next player to move (i. e. a position) if and only if its Grundy value is zero; and
The Grundy value of the sum of a finite set of positions is just the nim sum of the Grundy values of its summands. It follows straightforwardly from these results that if a position has a Grundy value of , then has the same Grundy value as , and therefore belongs to the same outcome class, for any position Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them. These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.
Позиция является проигрышной для следующего игрока (т. е. является *N*-позицией), если и только если её значение Грунди равно нулю; и
The Grundy value of a single nim pile of size (i. e. of the position ) is ;
A position is a loss for the next player to move (i. e. a position) if and only if its Grundy value is zero; and
The Grundy value of the sum of a finite set of positions is just the nim sum of the Grundy values of its summands. It follows straightforwardly from these results that if a position has a Grundy value of , then has the same Grundy value as , and therefore belongs to the same outcome class, for any position Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them. These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.
Значение Грунди суммы конечного набора позиций равно побитовому исключающему ИЛИ (ним-сумме) значений Грунди составляющих её позиций. Непосредственно из этих результатов следует, что если позиция *p* имеет значение Грунди *g*, то *N*(p) имеет то же значение Грунди, что и *g*, и, следовательно, принадлежит к тому же классу исходов для любой позиции *p*. Таким образом, хотя Спраг и Грунди никогда явно не формулировали теорему, описанную в этой статье, она непосредственно вытекает из их результатов и приписывается им. Эти результаты впоследствии были развиты в область комбинаторной теории игр, в частности, Ричардом Гаем, Элвином Берлекампом, Джоном Хортоном Конвеем и другими, где они теперь заключены в теореме Спрага — Грунди и её доказательстве в форме, описанной здесь. Эта область представлена в книгах «Winning Ways for your Mathematical Plays» и «On Numbers and Games».
The Grundy value of a single nim pile of size (i. e. of the position ) is ;
A position is a loss for the next player to move (i. e. a position) if and only if its Grundy value is zero; and
The Grundy value of the sum of a finite set of positions is just the nim sum of the Grundy values of its summands. It follows straightforwardly from these results that if a position has a Grundy value of , then has the same Grundy value as , and therefore belongs to the same outcome class, for any position Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them. These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.