E140. Теория Шпрага-Гранди. Ним

Источник: e-maxx.ru/algo, страница PDF 458.

Введение

Теория Шпрага-Гранди — это теория, описывающая так называемые равноправные (англ. "impartial") игры двух игроков, т.е. игры, в которых разрешённые ходы и выигрышность/проигрышность зависят только от состояния игры. От того, какой именно из двух игроков ходит, не зависит ничего: т.е. игроки полностью равноправны. Кроме того, предполагается, что игроки располагают всей информацией (о правилах игры, возможных ходах, положении соперника). Предполагается, что игра конечна, т.е. при любой стратегии игроки рано или поздно придут в проигрышную позицию, из которой нет переходов в другие позиции. Эта позиция является проигрышной для игрока, который должен делать ход из этой позиции. Соответственно, она является выигрышной для игрока, пришедшего в эту позицию. Понятно, ничейных исходов в такой игре не бывает. Иными словами, такую игру можно полностью описать ориентированным ациклическим графом: вершинами в нём являются состояния игры, а рёбрами — переходы из одного состояния игры в другое в результате хода текущего игрока (повторимся, в этом первой и второй игрок равноправны). Одна или несколько вершин не имеют исходящих рёбер, они является проигрышными вершинами (для игрока, который должен совершать ход из такой вершины). Поскольку ничейных исходов не бывает, то все состояния игры распадаются на два класса: выигрышные и проигрышные. Выигрышные — это такие состояния, что найдётся ход текущего игрока, который приведёт к неминуемому поражению другого игрока даже при его оптимальной игре. Соответственно, проигрышные состояния — это состояния, из которых все переходы ведут в состояния, приводящие к победе второго игрока, несмотря на "сопротивление" первого игрока. Иными словами, выигрышным будет состояние, из которого есть хотя бы один переход в проигрышное состояние, а проигрышным является состояние, из которого все переходы ведут в выигрышные состояния (или из которого вообще нет переходов). Наша задача — для любой заданной игры провести классификацию состояний этой игры, т.е. для каждого состояния определить, выигрышное оно или проигрышное. Теорию таких игр независимо разработали Роланд Шпраг (Roland Sprague) в 1935 г. и Патрик Майкл Гранди (Patrick Michael Grundy) в 1939 г.

Игра "Ним"

Эта игра является одним из примеров описываемых выше игр. Более того, как мы увидим чуть позже, любая из равноправных игр двух игроков на самом деле эквивалентна игре "ним" (англ. "nim"), поэтому изучение этой игры автоматически позволит нам решать все остальные игры (впрочем, об этом позже). Исторически, эта игра была популярна ещё в древние времена. Вероятно, игра берёт своё происхождение в Китае — по крайней мере, китайская игра "Jianshizi" очень похожа на ним. В Европе первые упоминания о ниме относятся к XVI в. Само название "ним" придумал математик Чарлз Бутон (Charles Bouton), который в 1901 г. опубликовал полный анализ этой игры. Происхождение названия "ним" доподлинно неизвестно.

Описание игры

Игра "ним" представляет из себя следующую игру. Есть несколько кучек, в каждой из которых по нескольку камней. За один ход игрок может взять из какой-нибудь одной кучки любое ненулевое число камней и выбросить их. Соответственно, проигрыш наступает, когда ходов больше не осталось, т.е. все кучки пусты. Итак, состояние игры "ним" однозначно описывается неупорядоченным набором натуральных чисел. За один ход разрешается строго уменьшить любое из чисел (если в результате число станет нулём, то оно удаляется из набора).

Решение нима

Решение этой игры опубликовал в 1901 г. Чарлз Бутон (Charles L. Bouton), и выглядит оно следующим образом. Теорема. Текущий игрок имеет выигрышную стратегию тогда и только тогда, когда XOR-сумма размеров кучек отлична от нуля. В противном случае текущий игрок находится в проигрышном состоянии. (XOR-суммой чисел

называется выражение

, где

— операция побитового исключающего или)

Доказательство. Основная суть приведённого ниже доказательства — в наличии симметричной стратегии для противника. Мы покажем, что, оказавшись в состоянии с нулевой XOR-суммой, игрок не сможет выйти из этого состояния — при любом его переходе в состояние с ненулевой XOR-суммой у противника найдётся ответный ход, возвращающий XOR-сумму обратно в ноль. Приступим теперь к формальному доказательству (оно будет конструктивным, т.е. мы покажем, как именно выглядит симметричная стратегия противника — какой именно ход нужно будет ему совершать). Доказывать теорему будем по индукции. Для пустого нима (когда размеры всех кучек равны нулю) XOR-сумма равна нулю, и теорема верна. Пусть теперь мы хотим доказать теорему для некоторого состояния игры, из которого есть хотя бы один переход. Пользуясь предположением индукции (и ацикличностью игры) мы считаем, что теорема доказана для всех состояний, в которые мы можем попасть из текущего.

Тогда доказательство распадается на две части: если XOR-сумма

в текущем состоянии

, то надо доказать,

что текущее состояние проигрышно, т.е. все переходы из него ведут в состояния с XOR-суммой

. Если же

, то надо доказать, что найдётся переход, приводящий нас в состояние с .

● Пусть

, тогда мы хотим доказать, что текущее состояние — проигрышно. Рассмотрим любой переход из

текущего состояния нима: обозначим через

номер изменяемой кучки, через

(

) — размеры кучек

до хода, через

(

) — после хода. Тогда, пользуясь элементарными свойствами функции , мы имеем:

Но поскольку

, то это означает, что

. Значит, новое состояние будет иметь ненулевую XOR-сумму, т. е., согласно базе индукции, будет выигрышным, что и требовалось доказать.

● Пусть

. Тогда наша задача — доказать, что текущее состояние — выигрышно, т.е. из него существует ход в проигрышное состояние (с нулевой XOR-суммой).

Рассмотрим битовую запись числа

. Возьмём старший ненулевой бит, пусть его номер равен

. Пусть

— номер

той кучки, у размер

которой

-ый бит отличен от нуля (такое

найдётся, иначе бы в XOR-сумме

этот бит

не получился бы отличным от нуля).

Тогда, утверждается, искомый ход — это изменить

-ую кучку, сделав её размера

. Убедимся в этом.

Сначала надо проверить, что это ход корректный, т.е. что

. Однако это верно, поскольку все биты, старшие

-го, у

и

совпадают, а в

-ом бите у

будет ноль, а у

будет единица. Теперь посчитаем, какая XOR-сумма получится при этом ходе: Таким образом, указанный нами ход — действительно ход в проигрышное состояние, а это и доказывает, что текущее состояние выигрышно. Теорема доказана. Следствие. Любое состояние ним-игры можно заменить эквивалентным состоянием, состоящим из единственной кучки размера, равного XOR-сумме размеров кучек в старом состоянии. Иными словами, при анализе нима с несколькими кучками можно посчитать XOR-сумму

их размеров, и перейти к

анализу нима из единственной кучки размера

— как показывает только что доказанная теорема,

выигрышность/проигрышность от этого не изменится.

Эквивалентность любой игры ниму. Теорема

Шпрага-Гранди

Здесь мы покажем, как любой игре (равноправной игре двух игроков) поставить в соответствие ним. Иными словами, любому состоянию любой игры мы научимся ставить в соответствие ним-кучку, полностью описывающее состояние исходной игры.

Лемма о ниме с увеличениями

Докажем сначала очень важную лемму — лемму о ниме с увеличениями. А именно, рассмотрим следующий модифицированный ним: всё так же, как и в обычном ниме, однако теперь разрешается дополнительный вид хода: вместо уменьшения, наоборот, увеличить размер некоторой кучки. Если быть более точным, то ход игрока теперь заключается в том, что он либо забирает ненулевое количество камней из какой-нибудь кучки, либо увеличивает размер какой-либо кучки (в соответствии с некими правилами, см. следующий абзац). Здесь важно понимать, что правила того, как именно игрок может совершать увеличения, нас не интересуют — однако такие правила всё же должны быть, чтобы наша игра по-прежнему была ациклична. Ниже в разделе "Примеры игр" рассмотрены примеры таких игр: "лестничный ним", "nimble-2", "turning turtles". Повторимся, лемма будет доказана нами вообще для любых игр такого вида — игр вида "ним с увеличениями"; конкретные правила увеличений в доказательстве никак не используются. Формулировка леммы. Ним с увеличениями эквивалентен обычному ниму, в том смысле, что выигрышность/проигрышность состояния определяется по теореме Бутона согласно XOR-сумме размеров кучек. (Или, иными словами, суть леммы в том, что увеличения бесполезны, их нет смысла применять в оптимальной стратегии, и они никак не меняют выигрышность/проигрышность по сравнению с обычным нимом.) Доказательство. Идея доказательства, как и в теореме Бутона — в наличии симметричной стратегии. Мы покажем, что увеличения ничего не меняют, поскольку после того, как один из игроков прибегнет к увеличению, другой сможет симметрично ответить ему. В самом деле, предположим, что текущий игрок совершает ход-увеличение какой-либо кучки. Тогда его соперник сможет просто ответить ему, уменьшив обратно эту кучку до старого значения — ведь обычные ходы нима у нас по-прежнему могут свободно использоваться. Таким образом, симметричным ответом на ход-увеличение будет ход-уменьшение обратно до старого размера кучки. Следовательно, после такого ответа игра вернётся обратно к тем же размерам кучек, т.е. игрок, совершивший увеличение, ничего от этого не выиграет. Т.к. игра ациклична, то рано или поздно ходы- увеличения кончатся, и текущему игроку придётся делать ход-уменьшение, а это и означает, что наличие увеличивающих ходов не меняет ровным счётом ничего.

Теорема Шпрага-Гранди об эквивалентности любой игры ниму

Перейдём теперь к самому главному в данной статье факту — теореме об эквивалентности ниму любой равноправной игры двух игроков.

Теорема Шпрага-Гранди. Рассмотрим любое состояние

некоторой равноправной игры двух игроков. Пусть

из него есть переходы в некоторые состояния

(где

). Утверждается, что состоянию

этой

игры можно поставить в соответствие кучку нима некоторого размера

(которая будет полностью описывать состояние

нашей игры — т.е. эти два состояния двух разных игр будут эквивалентны). Это число

— называется

значением Шпрага-Гранди состояния

.

Более того, это число

можно находить следующим рекурсивным образом: посчитаем значение Шпрага-Гранди

по каждому переходу

, и тогда выполняется:

где функция

от множества чисел возвращает наименьшее неотрицательное число, не встречающееся в этом множестве (название "mex" — это сокращение от "minimum excludant"). Таким образом, мы можем, стартуя от вершин без исходящих рёбер, постепенно посчитать значения Шпрага-Гранди для всех состояний нашей игры. Если значение Шпрага-Гранди какого- либо состояния равно нулю, то это состояние проигрышно, иначе — выигрышно. Доказательство. Доказывать теорему будем по индукции.

Для вершин, из которых нет ни одного перехода, величина

согласно теореме будет получаться как

от

пустого множества, т.е. . Но, в самом деле, состояние без переходов — это проигрышное состояние, и

ему действительно должна соответствовать ним-кучка размера

.

Рассмотрим теперь любое состояние

, из которого есть переходы. По индукции мы можем считать, что для

всех состояний

, в которые мы можем перейти из текущего состояния, значения

уже подсчитаны.

Посчитаем величину

. Тогда, согласно определению функции

, мы получаем, что

для любого числа

в промежутке

найдётся хотя бы один соответствующий переход в какое-то из

-ых

состояние. Кроме того, могут существовать также дополнительные переходы — в состояния со значениями

Гранди, большими

. Это означает, что текущее состояние эквивалентно состоянию ниму с увеличениями с

кучкой размера

: в самом деле, у нас есть переходы из текущего состояния в состояния с кучками всех меньших размеров, а также могут быть переходы в состояния больших размеров.

Следовательно, величина

действительно является искомым значением Шпрага-Гранди

для текущего состояния, что и требовалось доказать.

Применение теоремы Шпрага-Гранди

Опишем наконец целостный алгоритм, применимый к любой равноправной игре двух игроков для

определения выигрышности/проигрышности текущего состояния

. Функция, которая каждому состоянию игры ставит в соответствие ним-число, называется функцией Шпрага-Гранди. Итак, чтобы посчитать функцию Шпрага-Гранди для текущего состояния некоторой игры, нужно:

● Выписать все возможные переходы из текущего состояния.

● Каждый такой переход может вести либо в одну игру, либо в сумму независимых игр.

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

● После того, как мы посчитали функцию Гранди для каждого возможного перехода — считаем

от этих значений,

и найденное число — и есть искомое значение Гранди для текущего состояния.

● Если полученное значение Гранди равно нулю, то текущее состояние проигрышно, иначе — выигрышно.

Таким образом, по сравнению с теоремой Шпрага-Гранди здесь мы учитываем то, что в игре могут быть переходы из отдельных состояний в суммы нескольких игр. Чтобы работать с суммами игр, мы сначала заменяем каждую игру её значением Гранди, т.е. одной ним-кучкой некоторого размера. После этого мы приходим к сумме нескольких ним-кучек, т.е. к обычному ниму, ответ для которого, согласно теореме Бутона — XOR-сумма размеров кучек.

Закономерности в значениях Шпрага-Гранди

Очень часто при решении конкретных задач, когда требуется научиться считать функцию Шпрага-Гранди для заданной игры, помогает изучение таблиц значений этой функции в поисках закономерностей. Во многих играх, кажущихся весьма трудными для теоретического анализа, функция Шпрага-Гранди на практике оказывается периодичной, либо же имеющей очень простой вид, который легко заметить "на глаз". В подавляющем большинстве случаев увиденные закономерности являются верными, и при желании доказываемыми с помощью математической индукции. Впрочем, далеко не всегда функция Шпрага-Гранди содержит простые закономерности, а для некоторых, даже весьма простых по формулировке, игр вопрос о наличии таких закономерностей до сих пор открыт (например, "Grundy's game" ниже).

Примеры игр

Для наглядной демонстрации теории Шпрага-Гранди, разберём несколько задач. Особо следует обратить внимание на задачи "лестничный ним", "nimble-2", "turning turtles", в которой демонстрируется нетривиальное сведение исходной задачи к ниму с увеличениями.

"Крестики-крестики"

Условие. Рассмотрим клетчатую полоску размера

клеток. За один ход игроку надо поставить один крестик,

но при этом запрещено ставить два крестика рядом (в соседние клетки). Проигрывает тот, кто не может сделать ход. Сказать, кто выиграет при оптимальной игре. Решение. Когда игрок ставит крестик в какую-либо клетку, можно считать, что вся полоска распадается на две независимые половинки: слева от крестика и справа от него. При этом сама клетка с крестиком, а также её левый и правый сосед уничтожаются — т.к. в них больше ничего нельзя будет поставить.

Следовательно, если мы занумеруем клетки полоски от

до

, то, поставив крестик в позицию

,

полоска распадётся на две полоски длины

и

, т.е. мы переходим в сумму двух игр

и

. Если же крестик ставится в позицию

или

, то это особый случай — мы просто перейдём в

состояние

.

Таким образом, функция Гранди

имеет вид (для

): Т.е.

получается как

от множества, состоящего из числа

, а также всевозможных

значений выражения

.

Итак, мы получили решение этой задачи за

. На самом деле, посчитав на компьютере таблицу значений для первой сотни значений

, можно увидеть, что, начиная

с

, последовательность

становится периодичной с периодом

. Эта закономерность сохраняется

и дальше (что, вероятно, можно доказать по индукции).

"Крестики-крестики — 2"

Условие. Снова игра ведётся на полоске

клеток, и игроки по очереди ставят по одному крестику. Выигрывает тот, кто поставит три крестика подряд.

Решение. Заметим, что если

и мы оставили после своего хода два крестика рядом или через один пробел, то противник следующим ходом выиграет. Следовательно, если один игрок поставил где-то крестик, то другому игроку невыгодно ставить крестик в соседние с ним клетки, а также в соседние с соседними (т.е. на расстоянии

и

ставить невыгодно, это приведёт к поражению). Тогда решение получается практически аналогичным предыдущей задаче, только теперь крестик удаляет у каждой половинки не по одной, а сразу по две клетки.

"Пешки"

Условие. Есть поле

, на котором в первом и третьем ряду стоят по

пешек — белых и чёрных,

соответственно. Первый игрок ходит белыми пешками, второй — чёрными. Правила хода и удара — стандартные шахматные, за исключением того, что бить (при наличии такой возможности) обязательно. Решение. Проследим, что происходит, когда одна пешка сделает ход вперёд. Следующим ходом противник будет обязан съесть её, затем мы будем обязаны съесть пешку противника, затем снова он съест, и, наконец, наша пешка съест вражескую пешку и останется, "упёршись" в пешку противника. Таким образом, если мы в самом

начале пошли пешкой в колонке

, то в результате три колонки

доски

фактически уничтожатся, и мы перейдём к сумме игр размера

и

. Граничные случаи

и

приводят нас просто к доске размера

. Таким образом, мы получили выражения для функции Гранди, аналогичные рассмотренной выше задаче "Крестики-крестики".

"Lasker's nim"

Условие. Имеется

кучек камней заданных размеров. За один ход игрок может взять любое ненулевое число камней из какой-либо кучки, либо же разделить какую-либо кучку на две непустые кучки. Проигрывает тот, кто не может сделать ход. Решение. Записывая оба вида переходов, легко получить функцию Шпрага-Гранди как:

Однако можно построить таблицу значений для малых

и увидеть простую закономерность:

Здесь видно, что

для чисел, равных

или

по модулю

, и

для чисел, равных

и

по модулю

. Доказать это можно по индукции.

"The game of Kayles"

Условие. Есть

кегель, выставленных в ряд. За один удар игрок может выбить либо одну кеглю,

...

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int mex (List<int> a) {
            set<int> b (a.begin(), a.end());
            for (int i=0; ; ++i)
                    if (! b.count (i))
                            return i;
    }
    int mex (const List<int> & a) {
            static bool[] used = new bool[D+1] = { 0 };
            int c = (int) a.size();
            for (int 8  i=0; i<c; ++i)
                    if (a[i] <= D)
                            used[a[i]] = true;
            int result;
            for (int i=0; ; ++i)
                    if (!used[i]) {
                            result = i;
                             2 break;
                    }
            for (int  1 i=0; i<c; ++i)
                    if (a[i] <= D)
                            used[a[i]] = false;
            return result;
    }
}

int mex (vector<int> a) {
        set<int> b (a.begin(), a.end());
        for (int i=0; ; ++i)
                if (! b.count (i))
                        return i;
}
int mex (const vector<int> & a) {
        static bool used[D+1] = { 0 };
        int c = (int) a.size();
        for (int 8  i=0; i<c; ++i)
                if (a[i] <= D)
                        used[a[i]] = true;
        int result;
        for (int i=0; ; ++i)
                if (!used[i]) {
                        result = i;
                         2 break;
                }
        for (int  1 i=0; i<c; ++i)
                if (a[i] <= D)
                        used[a[i]] = false;
        return result;
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int mex (ArrayList<Integer> a) {
            set<int> b (a.begin(), a.end());
            for (int i=0; ; ++i)
                    if (! b.count (i))
                            return i;
    }
    int mex (const ArrayList<Integer> & a) {
            static boolean used[D+1] = { 0 };
            int c = (int) a.size();
            for (int 8  i=0; i<c; ++i)
                    if (a[i] <= D)
                            used[a[i]] = true;
            int result;
            for (int i=0; ; ++i)
                    if (!used[i]) {
                            result = i;
                             2 break;
                    }
            for (int  1 i=0; i<c; ++i)
                    if (a[i] <= D)
                            used[a[i]] = false;
            return result;
    }
}