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

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