Комбинаторная теория игр, Деорнуа П., 2017

Комбинаторная теория игр, Деорнуа П., 2017.

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




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

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

Оглавление
Введение
1.Пристрастные игры и числа
1.1.Игра хакенбуш
1.2.Сумма игр. Нулевые, положительные и отрицательные игры
1.3.Целые значения
1.4.Позиция
1.5.Двоично-рациональные позиции
1.6.Новая конструкция для чисел
1.7.Вещественные и сюрреальные числа
2.Беспристрастные игры и ним-числа: теория Шпрага — Гранди
2.1.Ним-числа
2.2.Покерный ним и правило наименьшего исключенного
2.3.Голодный конь
3.Смешиваем числа и ним-числа
3.1.Числа и ним-числа
3.2.Странное поведение рядом с нулём
3.3.Вполне малые игры
4.Горячие игры. Температура
4.1.Горячие игры
4.2.Прибавление переключателей
4.3.Переключатели как возможные ходы
4.4.Охлаждаем игру
Литература.

Купить .





Теги: книги для студентов и школьников :: Деорнуа