Теория Игр и функция Шпрага-Гранди

Доброго времени суток, уважаемое Хабрасообщество.

В последнее время все большее и большее распространение получает олимпиадное программирование, неотъемлемой частью которого является знание алгоритмов (и, разумеется, умение их применять).

Я хочу рассказать вам основы теории Игр, доказать функцию Шпрага-Гранди, разобрать несколько классических impartial-задач и проиллюстрировать их кодом на python.


Вместо предисловия


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

Начать стоит с того, что теория, разработанная Роландом Шпрагом и Патриком Гранди в середине прошлого века, распространяется на игры, которые можно назвать «равноправными» (impartial). К этой категории относятся игры, в которых соблюдаются следующие условия:
  1. игра конечна
  2. в игре невозможна ничья
  3. игроки видят всю информацию о состоянии соперника

В качестве примеров подобных игр можно привести игру Ним, Баше и прочие игры. О них мы поговорим чуть позже, а пока обсудим, что же следует из условий.

Основным пунктом, разумеется, является конечность игры, из которой следует, что сам процесс можно представить в виде движения по ацикличному ориентированному графу, вершинами которого являются состояния игры, а ребрами — переходы между ними в результате хода игрока.
Из того, что в игре невозможна ничья, следует, что состояния игры можно разделить на выигрышные и проигрышные. К первым относятся те, из которых можно перейти в проигрышное состояние, а ко вторым — из которых никуда нельзя перейти, или можно, но только в выигрышное состояние.

Таким образом, решение задач на теорию Игр, связанных с «равноправными» играми, можно свести к изучению графа состояний игры и определению итогового результата.

Игра Ним


image
Рассмотрим пример нахождения выигрышной стратегии на примере игры Ним. Почему? Потому что впоследствии можно будет доказать, что условия всех «равноправных» игр можно свести к условиям игры Ним.
Итак, у нас есть N кучек, в каждой из которых расположено положительное количество камней. Игроки по очереди берут из кучек положительное количество камней. Когда все кучки становятся пустыми, игра заканчивается поражением того игрока, который не может сделать ход. Следовательно, состояние игры можно описать набором из N положительных натуральных0 чисел, а игра заканчивается, когда сумма этих чисел становится равной нулю.

Теорема #1:


Для текущего игрока стратегия является выигрышной тогда и только тогда, когда xor-сумма1 размеров кучек положительна.


Докажем это.
Пусть у нас есть два массива значений (before[], after[]), в одном из которых (before[]) хранятся размеры кучек до хода игрока, а в другом (after[]) — после хода игрока.
Будем хранить в переменных bf и af xor-суммы до и после хода игрока (где «^» — операция xor):
bf = before[0] ^ before[1] ^… ^ before[N — 1] ^ before[N]
af = after[0] ^ after[1] ^… ^ after[N — 1] ^ after[N]
Тогда, воспользовавшись следствием из свойств xor, мы можем записать:
af = bf ^ before[i] ^ after[i], где «i» — номер кучки, из которой брал камни сделавший ход игрок.

Основываясь на вышесформулированном, докажем теорему #1 по индукции (рассмотрим два случая: bf == 0 и bf != 0):
Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
Рассмотрим битовую запись числа bf. Возьмем старший ненулевой бит, обозначив его номер за q. Пусть k — номер того из чисел before[], у которого q-ый бит отличен от нуля (иными словами, номер искомой кучки).
Предположим, что after[k] = before[k] ^ bf (предполагается, что это и есть искомый ход). Почему он корректен? Потому что after[k] < before[k]. Это следует из того, что все биты, старше q-ого у after[k] и before[k] совпадают, а в q-ом бите у before[k] записана единица, а у after[k] — ноль.
Тогда посчитаем:
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0
Так как при это ходе xor-сумма равна нулю, то теорема доказана.

Что следует из теоремы #1? Из нее следует, что любое состояние ним-подобной («равноправной») игры можно заменить эквивалентным, но состоящим из единственной кучки, размер которой равен XOR-сумме размеров кучек в старом состоянии.

Функция Шпрага-Гранди


Состояние любой «равноправной» игры можно изобразить в виде ним-кучки. Если размер кучки равен нулю, то состояние проигрышное. Если не равен — выигрышное.
Пусть мы располагаем неким состоянием G[], эквивалентным некой ним-кучке размером X. Это число можно найти по индукции. Если мы знаем, что состоянию G[i] соответствует m[i], то m[] будет находиться следующим образом:
m = mex{m[1], ..., m[k]} 2.

Именно в этом и заключается функция Шпрага-Гранди: если нам нужно определить победителя «равноправной» игры, то мы сводим ее к ним-кучкам, считаем G() для каждой из кучек и находим их xor-сумму.
Иными словами, G(k, n, m) = G(k) ^ G(n) ^ G(m).

Задачи


Теперь разберем функцию Шпрага-Гранди на примере олимпиадной задачи, встретившейся мне в отборочном туре Летней Компьютерной Школы. Условия задачи сводились к следующему:
На неком острове бушуют пожары. Робот смог затушить все города, кроме одного.
Пламя распространяется очень быстро, поэтому каждый день огонь пожирает все города,
соединенные дорогой с уже горящими городами. Тушить робот уже ничего не может,
единственное, что ему остается — это бежать от огня. Скорость робота совпадает со
скоростью огня, поэтому за один день робот может перебраться в соседний город.
Роботом посменно управляют два пилота Николай и Владимир, которые находятся на
естественном спутнике Земли. Не смотря на то, что робота уже не спасти и пользы от него
никакой нет, пилоты очень заинтересованы, чтобы он был уничтожен не в их смену. За
потерю робота полагается приличный вычет из заработной платы.
В первый день робот находится в столице (городе номер 1). Николай управляет роботом
в первый день и может направить его в произвольный город соединенный с 1. Далее пилоты
чередуются. Таким образом, каждый день единственное что может сделать робот — это
передвинуться на любой соседний с его текущим положением город.
В первый день горит только столица. Каждый следующий день дополнительно
загораются все города, соединенные дорогами с уже горящими.
Если пилот оставляет робота в горящем городе или направляет его в уже горящий
город, то робот не выдерживает огня и уничтожается.


Нужно определить, кто при оптимальной игре, заплатит за робота штраф. Очевидно, что эта игра ним-подобна: она конечна, в ней невозможна ничья и оба игрока видят информацию о ходе противника.
К чему она сводится? Правильно, к определению G-функции от города с номером 1.
image
Рассмотри на примере кода. Будем считать, что у нас есть матрица смежностей с удаленными ребрами (удалять ребро a —> b будем, если город b сгорит раньше города a).
Тогда функция Шпрага-Гранди для этой задачи будет высчитываться так:

def Grundy():
	for i in range(N):
		if matrix[v][i] == 1:
			if Grundy(i) == 0:
				return 1
				exit
	return 0

Если функция возвращает «1», то при оптимальной игре победит Владимир.

Теперь рассмотрим ситуацию с ним-подобной игрой, но обладающей множеством условий. Пусть есть кучка камней, число которых нечетное. За раз можно взять не больше четырех камней из кучки. Игра продолжается до тех пор, пока камни не закончатся. Не побеждает тот, кто взял четное количество камней.
На первый взгляд, игра уже не анализируется с помощью функции Шпрага-Гранди. Почему? Потому что состояние игры определяет не только количество камней в кучке — важны еще и камни игроков. Но это легко учесть, если взять в качестве состояния игры
G() от чисел n, m и p, где n — количество камней в кучке, а m и p — четность камней у игроков (0 — нечетное количество, 1 — четное количество).

Возможно две ситуации окончания игры, при которых n == 0:
G(0, 0, 1) и G(0, 1, 0).
Первая ситуация немного нехарактерна для обычных ним-игр — игрок не может сделать ход, но так как количество его камней четное, то он и не проиграл. Чтобы изобразить это на графе, добавим переход:
(0, 0, 1) —> (0, 1, 0)
Если теперь изобразить граф, то можно отметить следующую периодичность:
G(n, m, p) = G(a, m, p),
где a = n mod 6
Что это нам дает? Пусть камней в кучке 27. Тогда G(27, 0, 0) = G(3, 0, 0) = 3. Начинающий выигрывает, а ход, который создает выигрышную позицию, должен переводить (3, 0, 0) —> (1, 0, 0). Следовательно, для победы начинающему нужно взять два камня.

Подведем итоги


Функция Шпрага-Гранди — неотъемлемая часть ним-подобных («равноправных») игр и теории Игр в целом. Решение задач с ее помощью сводится к определению функции G() от каждого состояния игры и нахождению их xor-суммы (еще это называется «суммой игры»).
Для игр, в которых число состояний настолько велико, что считать его ресурсозатратно, можно найти определенные закономерности. Кроме того, довольно часто функция Шпрага-Гранди бывает периодичной.

Примечания


0 несмотря на спорность этого вопроса, ноль тоже будем считать натуральным числом.
1 xor-суммой чисел a[N] называется выражение a[1] ^ a[2] ^… ^ a[N].
2 mex от множества чисел является наименьшее неотрицательное число, не встречающееся в этом множестве (от англ. minimum excludant).

Литература


Для более подробного изучения этой темы рекомендую книги:
E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays
J. H. Conway. On Numbers And Games.
И довольно интересный курс лекций.
К сожалению, все это на английском.

Задачи для самостоятельной проработки


Если вы хотите порешать задачи на эту тематику, то рекомендую вот эту и прочие похожие задачи.

Успехов!

UPD: перенес в «Спортивное программирование».
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 30

    0
    Ну что сказать, сразу вспоминается «Ford Bayard» c игрой в палочки
      0
      Точно! Если бы все участники в обязательном порядке изучали перед игрой функцию Шпрага-Гранди, то «Форт Боярд» бы обанкротились ;).
        0
        Не знаю, мне всегда в детстве удавалось понять и просчитать наперед, как я выиграю или проиграю… Благо у них был набор небольшой в игре. А еще помню, как мы сами играли, набирали трубочек из под чупа-чупсов и рубились =)
      +3
      Извините, но с вашей статьи трудно понять как применяется функция Шпраг-Гранди в теории игр в общем случае. В двух приведенных примерах даже не используется функции mex и xor (другими словами они могут быть решени без каких-либо знаний об игре Ним и функции Шпрага-Гранди).
      Вот ссылка где очень доступно все объясняется: e-maxx.ru/algo/sprague_grundy
        +2
        Cпасибо за конструктивную критику! Да, на e-maxx довольно доступное объяснение, но примеров там тоже нет.

        Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.

        Но можно рассмотреть и для mex с xor:
        Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.

        Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
        Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
        G(n) можно вычислить так:
        G(1) = 0,
        G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
        Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
          +1
          Это уже лучший пример.
          Хотя данная задача имеет тривиальное решение, поскольку количество ходов для кучки n всегда равно n-1. Тогда количество ходов для кучек (a, b, c) будет a+b+c-3.
            0
            Верно :). Для доказательства достаточно представить, что кучки — это полоски бумаги состоящие из n клеточек в ряд, и за один ход разрешается разрезать на две любую из имеющихся бумажек, на длине от края кратной длине клеточки. Очевидно в игре изначально можно сделать (a — 1 + b — 1 + c — 1) разрезов, и игра закончится только в момент, когда все эти разрезы будут сделаны, а порядок их неважен.

            Но хотелось проиллюстрировать именно решением с помощью Шпрага-Гранди.
        0
        Cпасибо за конструктивную критику! Да, на e-maxx довольно доступное объяснение, но примеров там тоже нет.

        Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.

        Но можно рассмотреть и для mex с xor:
        Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.

        Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
        Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
        G(n) можно вычислить так:
        G(1) = 0,
        G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
        Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
          0
          Упс, простите за даблпост.
          0
          «Следовательно, состояние игры можно описать набором из N положительных чисел, а игра заканчивается, когда сумма этих чисел становится равной нулю», — несколько раз перечитывал эту волшебную формулировку, но так и не понял, КАК это может получиться.

            0
            Например, у нас есть кучки из пяти, шести и семи камней. Тогда состояние игры на данный момент можно описать как G(5, 6, 7), где «5, 6, 7» — тот самый набор положительных чисел, а N — количество кучек.

            Когда сумма этих чисел становится равна нулю, можно сделать вывод, что камни закончились, т.е ход сделать невозможно. А если ход сделать невозможно, то игру можно считать оконченной.
              0
              При всём уважении, я не понимаю, как складывая три положительных(!) числа, можно получить 0.
                0
                Хм, спасибо, исправил на «натуральных».
                  0
                  Тогда нулю сумма равна тогда и только тогда, когда все эти числа равны 0. Может лучше написать, что эти числа целые?
                    0
                    Тогда нулю сумма равна тогда и только тогда, когда все эти числа равны 0

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

                    Или вы имеете в виду что-то другое?
                      0
                      Раз это и имеется в виду, то вопросов больше нет. Извините.
                    0
                    Натуральные и положительные числа в сумме не дают 0, если их самих не ноль. Это, хотел сказать GORKOFF. Если конечно там не имеется в виду xor-сумма, но вроде там еще рано.
                    Мне кажется эту фразу просто можно выкинуть.
                      0
                      Я думаю, что выкинуть эту фразу нельзя — именно в ней и заключается вся суть решения ним-подобных игр.

                      Натуральные и положительные числа в сумме не дают 0, если их самих не ноль

                      Не смотря на спорность этого вопроса, я отношу ноль к натуральным числам.
                        0
                        В наших школах и университетах почти всегда преподают, что 0 не натуральное.
                        А статья на русском, значит логично заменить на неотрицательные.
                          0
                          «Неотрицательное» — это еще и вещественное положительное. А в кучке не может быть, например, 5.6 камня.

                          Спасибо за идеи, я вынес в сноску уточнение по поводу «натуральности» нуля.
              +1
              Тоже странное предложение:

              Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], а bf != 0, то переход ведет в выигрышное состояние.

              1. Вначале предполагается, что bf == 0, а затем используется, что bf != 0.
              2. В одном предложении используются то before[i], то bf[i]. Разные ли это вещи?
              Предлагаю переписать, на что-то вроде:

              Если bf = 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af = bf[i] ^ af[i], но так как bf[i] != af[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
                0
                Точно, опечатался. Спасибо, исправил.
                0
                Тогда еще одно непонятное предложение:

                Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
                af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (af ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.

                Вообще переход не простой. ИМХО можно написать подробнее, а тут еще и ошибка, так что врубиться в него могут только настойчивые.

                Как минимум надо переписать так:
                Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
                af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
                  0
                  Cпасибо, исправил. А что, по-вашему, в переходе стоит расписать подробнее?
                    0
                    1. Написать, что after[k] берется равным bf * before[k].
                    2. Фраза где K — количество камней… явно имеется в виду где K — номер кучки и т.д.
                    3. Показать, что, что after[k] < before[k], за счет выбора k.
                      0
                      Дополнил, спасибо.
                  0
                  На неком острове бушуют пожары. Робот смог затушить все города, кроме одного.
                  Пламя распространяется очень быстро, поэтому каждый день огонь пожирает все города,
                  соединенные дорогой с уже горящими городами. Тушить робот уже ничего не может,
                  единственное, что ему остается — это бежать от огня. Скорость робота совпадает со
                  скоростью огня, поэтому за один день робот может перебраться в соседний город.
                  Роботом посменно управляют два пилота Николай и Владимир, которые находятся на
                  естественном спутнике Земли. Не смотря на то, что робота уже не спасти и пользы от него
                  никакой нет, пилоты очень заинтересованы, чтобы он был уничтожен не в их смену. За
                  потерю робота полагается приличный вычет из заработной платы.
                  В первый день робот находится в столице (городе номер 1). Николай управляет роботом
                  в первый день и может направить его в произвольный город соединенный с 1. Далее пилоты
                  чередуются. Таким образом, каждый день единственное что может сделать робот — это
                  передвинуться на любой соседний с его текущим положением город.
                  В первый день горит только столица. Каждый следующий день дополнительно
                  загораются все города, соединенные дорогами с уже горящими.
                  Если пилот оставляет робота в горящем городе или направляет его в уже горящий
                  город, то робот не выдерживает огня и уничтожается.

                  По этой задаче можно кино снимать. Или даже минисериал.
                    0
                    Ага, или аниме.
                    Если интересно — посмотрите остальные задачи, которые были в этом году в списке вступительных:
                    lksh.ru/sis/2011/vstupit/prakt.pdf
                    Там есть и довольно интересные, на мой взгляд.
                    0
                    Немного не понял, откуда в последнем примере взялось «a = n mod 6», это как-то связано с тем, что можно «за раз можно взять не больше четырех камней»?
                      0
                      Да, верно, связано.
                      Нам известно, что за раз можно взять не больше четырех камней. Тогда, если нарисовать граф состояний игры, будет очевидно, что из каждой вершины выходит не больше четырех дуг.
                      Так же известно, что
                      G(0, 1, 0) = 0 (по условиям).
                      Если теперь определить функцию для каждого состояния, то можно заметить, что функция оказывается периодической с периодом длины 6, из чего уже следует
                      a = n mod 6.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое