Комбинаторная теория игр

K
Y
M

В -х годах прошлого века
известный американский
математик Дж. Конвей обнаружил,
что исследование свойств
различных математических игр
ведет к построению удивительных
«сюрреальных чисел»,
обобщающих действительные.
В брошюре доступно излагается
эта красивая и оригинальная
теория.

M
Y
K

Летняя школа «Современная математика»,
Дубна, июль 2009

Пьер Деорнуа

Комбинаторная теория игр

Электронное издание

Москва
Издательство МЦНМО
2018

УДК 519.83
ББК 22.18
Д34

Деорнуа П.
Комбинаторная теория игр.
Электронное издание.
М.: МЦНМО, 2018.
39 с.
ISBN 978-5-4439-3172-2

Оказывается, позициям в самых разных играх можно сопоставить своеобразные числа, оценивающие положение игроков. Возникающие «сюрреальные числа» включают в себя все действительные
числа (но не только). В брошюре рассказывается, как возникающая
теория помогает проанализировать ним, хакенбуш и другие игры.
Брошюра написана по материалам лекций, прочитанных автором на летней школе «Современная математика» в Дубне в июле
2009 года. Она доступна школьникам старших классов.

12+

Перевод с английского

М. А. Веретенниковой, Н. С. Медянкина,
М. А. Раскина, А. С. Трепалина и В. А. Клепцына

Подготовлено на основе книги: Деорнуа П. Комбинаторная теория
игр. — М.: МЦНМО, 2017. — 40 с. ISBN 978-5-4439-1172-4.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11
тел. (499) 241–08–04
http://www.mccme.ru

ISBN 978-5-4439-3172-2
ffi П. Деорнуа, 2017
ffi МЦНМО, 2017

Введение

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

⊂ ⊂ заменяется на цепочку

⊂ двоично-рациональные числа ⊂ сюрреальные числа.

Всё, что будет рассказано ниже, изложено в замечательных книгах
Берлекампа, Конвея и Гая [1] и Конвея [3]. На русском языке кое-что
о сюрреальных числах можно узнать из главы 4 книги Гарднера [5],
а также из книги Кнута [6]. Я рекомендую начать с [1], а потом
посмотреть полное изложение теории в [3].
Этот текст является расширенными записками мини-курса, прочитанного автором в июле 2009 года на Летней школе «Современная
математика» в Дубне.

* * *

Игры, которые мы будем изучать, обладают следующими свойствами:

• играют два игрока (далее мы будем называть их Левым и Правым);
• имеется набор позиций и правила, определяющие, в какие позиции разрешается делать ход из данной;

• обоим игрокам известна вся информация (нет никаких спрятанных карт и невидимых противнику ходов, а правила известны
обоим игрокам);

• в игре нет никакой случайности (ни бросания кубика, ни перетасовки карт);

• игра всегда заканчивается за конечное число шагов (при этом
конечности множества всех позиций мы, вообще говоря, не предполагаем!);

• всегда есть победитель — ничьих не бывает.

3

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

Определение 1. Будем называть игрой (возможно, бесконечное)
множество G («позиции») вместе с выделенным элементом g0 («начальная позиция») и зафиксированными для каждой позиции g ∈ G
двумя подмножествами g 𝐿, g 𝑅 ⊂ G («допустимые ходы Левого и Правого из позиции g»). При этом потребуем ещё, чтобы любая цепочка
допустимых ходов имела конечную длину (в частности, не существует
циклов из разрешённых ходов).
Два игрока играют в такую игру, начиная с начальной позиции
и каждый раз делая по допустимому ходу; проигрывает тот, кто не может сделать ход.

Последнее условие в определении игры гарантирует, что с какой
бы позиции мы ни начинали, партия завершается за конечное время.

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

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

Предложение 0.2. Для любой позиции реализуется ровно одна
из следующих возможностей:

• Левый обладает выигрышной стратегией вне зависимости от
того, кто начинает;

• Правый обладает выигрышной стратегией вне зависимости от
того, кто начинает;

• начинающий игрок обладает выигрышной стратегией;
• второй игрок обладает выигрышной стратегией.

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

Определение 2. Игра g — это два множества:

g 𝐿 = {g𝐿
1, g𝐿
2, ...}
и
g 𝑅 = {g𝑅
1 , g𝑅
2 , ...},

4

состоящие из игр; мы будем также писать

g = {g𝐿
1, g𝐿
2, ... | g𝑅
1 , g𝑅
2 , ...}.

Играют двое, Левый и Правый. Ход состоит в том, что игрок выбирает
одну из игр из множества g 𝐿 (если это Левый игрок) или g 𝑅 (если это
Правый игрок) и передаёт её противнику (дальше тот берёт эту игру
и делает ход аналогичным образом и т. д.). Тот, кто не может сделать
ход, проигрывает.

Такое рекурсивное определение выглядит парадоксально: мы определяемпонятие игры, используя‌ понятие игры. Понимать это нужно
так: мы называем играми то, что в силу этого определения не можем
не считать играми. Например, g = {|} является игрой: множества g 𝐿

и g 𝑅 пусты, так что все их элементы являются играми. Значит, {{|}|}
и {|{|}} являются играми и т. д. 1

Это определение, на самом деле, довольно тонкое. Существуют
игры с бесконечным числом позиций, построение которых требует
«бесконечного числа итераций» описанной конструкции. Мы столкнёмся с такими играми в п. 1.7, но для начала можно думать только
про игры с конечным числом позиций.

1 Подобным образом в теории множеств «из ничего» строятся натуральные числа:
0 = {}, 1 = {0}, 2 = {0, 1} и т. д. — подробности можно найти, например, в брошюре [8].

5

1. Пристрастные игры и числа

Пристрастные (partizan) игры — это игры, в которых для каких-то
позиций g множества g𝐿 и g𝑅 различны. Это — общая ситуация, в отличие от частного случая беспристрастных (impartial) игр, для которых в каждой позиции возможные ходы для обоих игроков одинаковы. Для начала мы рассмотрим игру Конвея хакенбуш («рубка
кустарника»), обладающую одним замечательным свойством: в ней
никогда не обладает выигрышной стратегией именно начинающий
игрок (см. лемму 1.2 ниже).

1.1. Игра хакенбуш

Правила 1.1 (Хакенбуш). Позиции: граф, рёбра которого раскрашены в синий и красный цвета, а некоторые из вершин объявлены находящимися на земле, причём от каждого из рёбер можно дойти до земли.
Ходы: Левый перерезает произвольное синее ребро, при этом все
остальные рёбра, которые перестают быть связанными с землёй, исчезают; Правый перерезает красное ребро, при этом все остальные
рёбра, которые перестают быть связанными с землёй, исчезают.

Разберём ход одной из партий: на первой картинке приведённого
ниже рис. 1 показана начальная позиция и последовательность ходов

1

7
6
5
3
2
4

Рис. 1

6

игроков, затем мы видим последовательность возникавших позиций.
После седьмого хода у Правого не остаётся красных рёбер, которые
он мог бы перерезать, и поэтому он проигрывает.
Замечательное свойство этой игры, из-за которого мы и начнём
изучение игр с неё, следующее.

Лемма 1.2. Для заданной позиции в игре хакенбуш первый игрок
никогда не обладает выигрышной стратегией, т. е. всегда выигрывает или Левый, или Правый, или второй игрок.

Доказательство. Предположим, в некоторой позиции Левый игрок,
начиная, выигрывает. Покажем, что он же тогда выиграет и ходя вторым.
Действительно, пусть, когда он начинает, его выигрышная стратегия говорит ему разрезать ребро E (в результате, возможно, исчезнут
и рёбра E1, E2, ... , держащиеся только на E).
Допустим теперь, что начинает Правый. Тогда Левый может следовать той же стратегии, что и раньше, считая, что ребро E уже разрезано. Единственной ситуацией, когда он будет вынужден от неё отклониться, будет разрезание Правым одного из рёбер E𝑖 или какого-то
из рёбер, которое в текущий момент держится только на E (и поэтому
в рамках исходной стратегии должно было бы уже исчезнуть). В ответ на это Левый стирает E и возвращается в точности к ситуации
применимости исходной стратегии.

1.2. Сумма игр. Нулевые, положительные
и отрицательные игры

При игре в хакенбуш часто возникает позиция, состоящая из двух
отдельных «кустов». С этого момента можно считать, что у нас есть
две разные игры (соответствующие каждому из «кустов») и каждый
раз игрок делает ход в одной из них; игрок проигрывает, если не может сделать ход ни на одной из досок. Это наблюдение приводит
к следующему определению суммы игр.

Определение 3. Сумма двух игр g и h — это игра, позиции в которой суть пары (позиция в g, позиция в h), а каждый ход является
либо ходом в игре g, либо ходом в игре h.

Можно определить сумму и в терминах определения 2 игр — рекуррентным образом.

Определение 4. Сумма двух игр g и h — это игра
g 𝐿
1 +h, g 𝐿
2 +h,..., g+h𝐿
1, g+h𝐿
2,...| g 𝑅
1 +h, g 𝑅
2 +h,..., g+h𝑅
1, g+h𝑅
2,...
.

7

Ключевую роль при анализе позиций играет следующее замечание.

Лемма 1.3. Предположим, что h — игра, в которой второй игрок
обладает выигрышной стратегией. Тогда для любой игры g в игре
g + h побеждает тот же игрок, кто и в игре g.

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

Эта лемма говорит, что при сложении игр мы всегда можем выбросить игру, в которой второй игрок обладает выигрышной стратегией — аналогично тому, как мы можем выкинуть нулевые слагаемые
при операциях с обычными числами!

Определение 5. Игра называется нулевой, если второй игрок обладает выигрышной стратегией, положительной — если Левый обладает выигрышной стратегией, отрицательной — если Правый обладает выигрышной стратегией, нечёткой (fuzzy) — если первый игрок
обладает выигрышной стратегией.

Например, {|} — нулевая игра. Но это не единственная нулевая
игра: например, позиция с одним синим ребром и одним красным
ребром, каждое из которых связано с землёй, тоже нулевая игра. Эта
неоднозначность исчезнет, как только мы определим равенство игр.
Мы теперь хотим определить равенство игр. Для чисел утверждение A = B может быть переписано как A − B = 0. Определение равенства нулю для игр у нас уже есть, осталось для игры A определить
игру −A. Определение станет понятным, если начать с хакенбуша.

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

Доказательство. Выигрышная стратегия для второго игрока —
симметричная: копировать ходы первого во втором экземпляре
игры.

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

Определение 6. Для игры

g = {g 𝐿
1 , g 𝐿
2 , ... | g 𝑅
1 , g 𝑅
2 , ...}

8

противоположная — это игра

−g := {−g 𝑅
1 , −g 𝑅
2 , ... | −g 𝐿
1 , −g 𝐿
2 , ...}.

В частности, −0 = 0.

Определение 7. Будем называть игры g и h равными, если сумма
g + (−h) — нулевая игра. В этом случае мы будем писать g = h.

Мы дали несколько определений — и, по-хорошему, должны были бы проверить, что они согласованы друг с другом. Эту проверку
мы оставим читателю в качестве самостоятельного — и очень полезного! — упражнения.

Упражнение 1.5. Проверьте, что:

• A = A. Если A = B, то B = A. Если A = B и B = C, то A = C.
• Если A = B, то A + C = B + C для любой игры C.

Упражнение 1.6. Более того, если A = B, то A и B взаимозаменяемы как варианты позиций.

Поэтому мы можем, к примеру, записать игру C ={0|}, не вдаваясь
в детали — какой именно вариант нулевой игры предлагается Левому
в качестве единственно возможного хода: все такие игры C равны.

Упражнение 1.7. Сумма двух положительных игр положительна,
сумма двух отрицательных игр отрицательна.

Будем говорить, что A > B, если A − B > 0. В силу упражнения 1.7
неравенства можно складывать обычным образом.

1.3. Целые значения

Рассмотрим позицию в хакенбуше с единственным синим ребром.
Тогда, кто бы ни начинал, Левый выигрывает. Поэтому эта позиция
является положительной. А чему она равна? Так как у Левого есть
ровно один «свободный» ход в этой позиции, мы будем считать её
равной 1. Так же, как мы определили число(!) 0, мы определим число 1
как эту игру.
Рассмотрев противоположную игру, мы видим, что число −1 —
это позиция с одним красным ребром (рис. 2).
Вспомнив определение суммы игр, мы видим, что число p − q —
это позиция с p синими рёбрами и q красными рёбрами, каждое
из которых касается земли. Это согласуется с тем фактом, что выигрывает Левый, если p > q, Правый, если p < q, и второй игрок, если
p =q. Заметим, что какие-либо другие позиции также могут оказаться

9