Pull to refresh

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

Reading time 6 min
Views 34K
Доброго времени суток, уважаемое Хабрасообщество.

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

Я хочу рассказать вам основы теории Игр, доказать функцию Шпрага-Гранди, разобрать несколько классических 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: перенес в «Спортивное программирование».
Tags:
Hubs:
+51
Comments 30
Comments Comments 30

Articles