Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 474723)
Консорциум Контекстум Информационная технология сбора цифрового контента

Введение в теорию комбинаторных игр (270,00 руб.)

2   0
АвторыФролов Илья Сергеевич
Страниц202
ID145760
АннотацияКнига посвящена теории комбинаторных игр ― активно развивающейся в настоящее время области математики на стыке теории графов, математической логики и теории чисел, которая лежит в основе компьютерных алгоритмов соответствующих игр. Материал книги основан на лекционном курсе, который автор читал студентам III и IV курсов специальностей "Математика", "Прикладная математика", "Компьютерная безопасность" и "Информационная безопасность". В конце каждого параграфа приведены задачи по всем рассматриваемым темам. К большинству задач приведены ответы и решения. Автор использовал данную теорию в своей практической работе при разработке компьютерных игр.
Кому рекомендованоДля студентов математических специальностей, обучающихся по программам бакалавриата, специалитета и магистратуры, а также для аспирантов и разработчиков компьютерных игр.
Введение в теорию комбинаторных игр / И.С. Фролов .— 2012 .— 202 с.

Предпросмотр (выдержки из произведения)

Несмотря на то, что такие игры (где результат целиком зависит от логических способностей игроков) известны с незапамятных времен: шашки, шахматы, игра го, — лишь сравнительно недавно к их исследованию стали привлекаться серьезные математические методы. <...> Книга может быть использована в качестве учебного пособия для студентов математических специальностей по специальным курсам «Комбинаторные игры» и «Программирование игр». <...> Комбинаторные игры по сравнению с ними — совершенный ребенок. <...> Семейство комбинаторных игр состоит из игр двух лиц с совершенной информацией (нет скрытой информации, как в некоторых карточных играх: все возможные ходы, а также история игры известны обоим игрокам), в которых нет случайных устройств (т.е. нет игральных костей или тасования карт); игроки делают ходы поочередно; игра всегда заканчивается, даже если игроки не будут чередовать ходы; результатом может быть только выигрыш–проигрыш и победителя определяет последний ход: в нормальной игре выигрывает игрок, сделавший последний ход, в игре мизер тот, кто сделал последний ход, проигрывает. <...> Вот примеры игр, которые не подпадают под эти правила: игра го, так как по окончании партии подсчитываются очки, и последний ход не гарантирует игроку, что у него окажется наибольшее или наименьшее количество очков; шахматы, так как шахматная партия может закончиться вничью; нарды, так как в них присутствует элемент случайности (игральная кость); бридж — единственное свойство этой игры, совпадающее с перечисленными выше признаками комбинаторной игры, — это то, что партия в бридж всегда заканчивается. <...> Чарльз Баутон (Charles Bouton), Эрнст Цермело (Ernst Zermelo), Эммануил Ласкер (Emmanuel Lasker), Патрик Гранди (Patrick Grundy), Роланд Шпраг (Roland Sprague), Седрик Смит (Cedric Smith), Ричард Гай (Richard Guy), Джон Конвей (John Conway), Элвин Берлекэмп (Elwyn Berlecamp), Авезри Френкель (Aviesri Fraenkel). <...> Как правило, если позиция игры разбивается на компоненты, так что игра распадается в дизъюнктивную <...>
Введение_в_теорию_комбинаторных_игр.pdf
Стр.1
Стр.2
Стр.3
Стр.4
Стр.5
Стр.6
Стр.7
Стр.8
Стр.9
Стр.10
Стр.11
Стр.12
Стр.13
Стр.14
Стр.15
Стр.16
Стр.31
Стр.32
Стр.44
Стр.45
Стр.54
Стр.55
Стр.68
Стр.69
Стр.80
Стр.81
Стр.100
Стр.101
Стр.115
Стр.116
Стр.128
Стр.129
Стр.142
Стр.143
Стр.157
Стр.158
Стр.175
Стр.176
Стр.183
Стр.184
Введение_в_теорию_комбинаторных_игр.pdf
И. Фролов ВВЕДЕНИЕ В ТЕОРИЮ КОМБИНАТОРНЫХ ИГР Учебное пособие
Стр.1
Фролов И. Введение в теорию комбинаторных игр: Учебное пособие. Книга посвящена новому направлению дискретной математики — теории комбинаторных игр. Несмотря на то, что такие игры (где результат целиком зависит от логических способностей игроков) известны с незапамятных времен: шашки, шахматы, игра го, — лишь сравнительно недавно к их исследованию стали привлекаться серьезные математические методы. Материал книги основан на лекционном курсе, который автор читал студентам механико-математического факультета Самарского государственного университета в течении ряда лет. В конце каждого параграфа приведены задачи по всем рассматриваемым темам. К большинству задач приведены ответы и решения. Изложение не предполагает у читателя специальных знаний, за исключением начал теории графов, общей алгебры и некоторого уровня математической культуры. Книга может служить учебником для начинающих и руководством для лиц, желающих составить представление об этой новой и изящной области математики. Для студентов, преподавателей, разработчиков игр.
Стр.2
Содержание Предисловие Введение 1. Направления математической теории игр 2. Комбинаторные игры 3. Исторические замечания 4. Древние и современные игры Часть I. Беспристрастные игры § 1. Простейшие комбинаторные игры 1. Игра ним 2. Что такое комбинаторная игра 3. P-позиции и N-позиции 4. Игры вычитания 5. Ним-значения 6. Ним мизер Приложение 1 Приложение 2 Задачи Решения § 2. Игры на графах. Функция Шпрага–Гранди 1. Ориентированные графы 2. Игры на графах 3. Функция Шпрага–Гранди 4. Функция Шпрага–Гранди на более общих графах 5. Симметричные графы и хроматические числа Задачи Решения § 3. Изоморфные игры 1. Примеры 2. Изоморфизм игр и другие виды эквивалентности игр 3. Модельная эквивалентность игр 4. Игры как множества Задачи Решения § 4. Сложение игр. Эквивалентные игры 1. Сумма игр 2. Эквивалентность игр по Шпрагу–Гранди 3. Ним-сложение 4. Эквивалентность игр ниму 5. Игры взятия как суммы игр вычитания 6. Группа игр Задачи Решения 3 6 8 8 10 11 12 15 15 15 18 20 21 23 23 24 25 26 28 31 31 33 35 36 37 39 41 44 44 47 48 50 51 52 54 54 55 58 60 62 63 65 66
Стр.3
4 § 5. Примеры игр 1. Игры взятия с одной кучей 2. Ладейная игра 3. Игра Цзяньшицзы 4. Игра «Евклид» 5. Игра слитер («ползунок») 6. Игра чомп («щёлк») 7. Бридж-ит 8. Игра гекс 9. Нимk (или Ним Мура) Приложение Задачи Решения § 6. Несколько классов игр 1. Игры взятия-разбиения 2. Восьмеричные игры (Octal games) 3. Игра Хакенбуш Задачи Решения § 7. Игры переворачивания монет 1. Одномерные игры переворачивания монет 2. Двумерные игры переворачивания монет 3. Шотландские игры 4. Поле нимберов Задачи Решения Часть II. Пристрастные игры § 8. Введение в пристрастные игры 1. Красно–синий Хакенбуш 2. Игра Прыгающие лыжники 3. Числа 4. Игра Жабы-и-лягушки Задачи § 9. Результативные классы игр 1. Формальное определение игры 2. Классы результативности 3. Сложение и сравнение игр 4. Упрощение игр Задачи Содержание 68 68 68 69 71 73 74 75 76 76 77 79 79 80 80 85 89 94 97 100 100 103 105 109 112 114 115 115 115 119 122 125 126 128 128 130 133 137 141
Стр.4
Содержание § 10. Примеры анализа игр 1. Ряд модификаций игры 2. T&F 3. Игра кол 4. Игра снорт 5. Игра кросскрем 6. Свитч-игры 7. Ультрамалые игры 8. Красно-синий Хакенбуш 9. x + n ·↑ +∗ 10. Игра доджем Задачи Решения § 11. Сюрреальные числа 1. Определения и следствия из определений 2. Умножение и деление чисел 3. Короткие числа и вещественные числа 4. Ординальные числа 5. Сюрреальные числа 6. День рождения игры 7. Структура числа (День рождения числа) 8. Сюрреальные числа (продолжение) 9. Функции сюрреальной переменной Задачи Решения § 12. Между играми и числами 1. Критерий: когда игра является числом 2. Правила: как играть с числами 3. Левые и правые значения 4. Позиции остановки 5. Короткие игры и числа 6. Теорема о среднем значении 7. Инфинитезимальные, малые и абсолютно малые игры Задачи § 13. Теория температуры 1. Некоторые обозначения и примеры 2. Охлаждение 3. Среднее значение и температура 4. Термограф 5. Левая и правая температура 6. Свитч-игры и их суммы 7. Игры с 3 и 4 стоп-позициями 8. Расширенный термограф 9. Разогрев Задачи Библиография Указатель обозначений 5 142 142 143 144 146 147 148 150 151 152 153 153 156 157 157 158 161 162 164 166 167 168 170 172 173 175 175 176 176 177 178 179 180 182 183 183 184 185 187 191 193 194 197 198 199 200 201
Стр.5
Предисловие Книга посвящена теории комбинаторных игр — активно развивающейся в настоящее время области математики на стыке теории графов, математической логики и теории чисел, которая лежит в основе компьютерных алгоритмов соответствующих игр. Данная область математики ставит своей целью исследование математическими методами комбинаторных игр, в обыденной лексике называемых «логическими играми»; к их числу относятся как игры с высокой комбинаторной сложностью: шашки, шахматы, го; так и игры, значительно более простые: крестики-нолики и многие другие. Материал книги представляет собой обработанную запись курса лекций по теории комбинаторных игр, прочитанного для студентов механикоматематического факультета Самарского государственного университета в 2006– 2010 годах. Вся книга разбита на параграфы, в точном соответствии с тем порядком лекций, в котором они были прочитаны. Автор использовал данную теорию в своей практической работе при разработке компьютерных игр. Книга поделена на две части, которые естественным образом возникают в теории комбинаторных игр: первая посвящена беспристрастным играм (играм, правила которых не делают различия между игроками), вторая — пристрастным играм (в которых игроки различаются своими возможными действиями: например, в шахматах игрокам разрешается управлять фигурами только своего цвета). Целью книги является доступное для начинающих математиков введение в современное состояние теории комбинаторных игр; в книге изложены как классические результаты теории, так и замечательные новейшие идеи последних лет, обуславливающие бурное развитие этой теории. Основными первоисточниками по теории комбинаторных игр служат следующие монографии, каждая из которых выдержала по два издания: Berlekamp E.R., Conway J.H., Guy R.K. Winning Ways for Your Mathematical Plays. Vol. I–II, Academic Press, New York, 1nd edition. (1982); Vol. I–IV, A.K.Peters, Ltd., Natick, Massachusetts, 2nd edition. (2003). Conway J.H. On Numbers and Games. Academic Press, New York, 1nd edition. (1976); A.K.Peters, Ltd., 2nd edition. (2000). Игры являют собой изумительную лабораторию для изучения методологий решения сложных проблем. Ограничившись очень небольшим числом ясных и понятных правил, можно воссоздать сложные ситуации, которые требуют не меньше интеллекта, интуиции, точного расчета, чем те проблемы, которые встречаются в реальном бизнесе, политике, экономике, праве и т.д. Помимо этого и в отличие от этих сфер человеческой деятельности, недоступных пока компьютеризации, игры предоставляют арену, в которой алгоритмические решения могут быть признаны абсолютными стандартами исполнения и в которой мастера и гуру игры не имеют ничего против передачи их знаний машине. Наконец, нельзя забыть, что играм присуща порой невероятно захватывающая привлекательность — привлекательность участия в игре, привлекательность ее анализа, выработки стратегии, привлекательность создания играющих (и выигрывающих!) программ. Это влечет за собой постоянный приток исследовательских талантов в данную область. 6
Стр.6
Предисловие 7 Читатель, имеющий минимальную математическую подготовку, ознакомившись с теорией Шпрага-Гранди, которая излагается в первых параграфах книги, сможет самостоятельно строить эффективную стратегию выигрыша в простых комбинаторных (логических) играх. Указанная теория полезна также для школьников старших классов и руководителей школьных математических кружков с целью ознакомления с методикой решения широкого класса задач, предлагающихся на олимпиадах различного уровня, включая всероссийские и международные. Математическая теория комбинаторных игр кладется в основу компьютерных алгоритмов соответствующих игр. В настоящее время считается решенной одна из разновидностей шашек — английские шашки. Компьютеры имеют в своем активе победы над чемпионами мира по шахматам Г.Каспаровым и В.Крамником. Данная теория в настоящее время оказывает большое влияние на (древнейшую и сложнейшую) игру го; в частности, параллельно развивается теория игры го, модифицируются ее правила. Методы, излагаемые в книге, дают возможность программистам– разработчикам игр разрабатывать компьютерные алгоритмы рациональной игры (немаловажно, что учреждаются различные премии за программы такого рода, наиболее крупная среди них учреждена фондом Инга — 40 миллионов тайваньских долларов, что составляет более 1 миллиона долларов США, за первую программу го, которая сможет победить чемпиона Тайваня среди любителей). Книга может быть использована в качестве учебного пособия для студентов математических специальностей по специальным курсам «Комбинаторные игры» и «Программирование игр». На русском языке аналогичных книг нет. Рассматриваемой тематике посвящены лишь популярные книги и фундаментальные монографии, указанные выше. Предлагаемая книга отличается от них своим учебным назначением. Автором подобрано большое количество задач, иллюстрирующих положения теории. К большинству задач приведены ответы и решения. Изложение математического материала сопровождается большим количеством примеров; мы надеемся, что книга вполне доступна студентам-математикам, начиная с младших курсов.
Стр.7
Я люблю того, кто стыдится, когда игральная кость выпадает ему на счастье, и кто тогда спрашивает: неужели я игрок-обманщик? Ф. Ницше. Так говорил Заратустра Введение 1. Направления математической теории игр. История игр начинается с незапамятных времен, но систематическое применение математики к играм — это относительно новое явление. Азартные игры стали изучаться с применением понятия вероятности в XVI–XVII вв. Комбинаторные игры по сравнению с ними — совершенный ребенок. Такие игры как предмет серьезного исследования стали привлекать внимание математиков только с начала XX века. Начало их изучению было положено статьей Чарльза Баутона в 1902 г. «Ним, игра с полной математической теорией» [10]. Теория комбинаторных игр — это математическая теория, изучающая игры двух лиц, в которых в каждый момент времени имеется позиция, которую игроки по очереди изменяют определенным образом или ходом, чтобы достичь определенного условия выигрыша. В этой теории не изучаются игры, связанные со случайностями (такие, как покер), а только игры, в которых и позиция, и все возможные ходы одинаково известны обоим игрокам. Применение теории комбинаторных игр к некоторой позиции заключается в определении оптимальной последовательности ходов для обоих игроков вплоть до конца игры, и таким образом определении оптимального хода в каждой позиции. На практике, однако, реализовать данную программу удается, лишь если игра крайне проста. Если классифицировать игры по их форме, т.е. по материальным признакам, связанным с ними, то можно выделить ряд классов игр: игры на доске, игры с фишками, игры с картами (карты не обязательно обычные игральные), игры с монетами, игры с домино, игры с бумагой и карандашом, игры с бумагой и ножницами. Помимо теории комбинаторных игр, имеется еще одна математическая теория, обычно называемая теорией игр1, используемая при исследовании экономического соперничества и сотрудничества, а также социального поведения людей. В такой теории игр есть место играм со случайностями, играм с неполной информацией и играм, в которых игроки делают ходы одновременно. Предметом упомянутой теории является игра как математическая модель коллективного поведения. Несколько агентов, обладающих различными собственными интересами, влияют на ситуацию (исход игры). Антагонизм интересов вводит в игру конфликт, в то время как близость интересов рождает координацию. Целью игры со стороны каждого агента является максимизация получаемой им полезности (выигрыша). 1 Не следует смешивать ее с нашим основным предметом, теорией комбинаторных игр. «Математическую теорию игр» точнее было бы назвать «экономической теорией игр». 8
Стр.8
1. Направления математической теории игр 9 В экономической теории игр имеется три основные формы представления игры. Это расширенная форма (дерево игры), нормальная форма (стратегические матрицы) и форма характеристической функции, которая применяется в теории кооперативных игр. Теория кооперативных игр — это теория коалиций; в ней изучаются игровые ситуации, в которых допустимы совместные действия игроков и побочные платежи (перераспределение выигрыша). Чтобы глубже прочувствовать различие экономической и комбинаторной теории, обратимся к обзору [18], в котором, в частности, рассматриваются основные виды неопределенности в игре. 1. Комбинаторная (вариантов очень много). Таковы игры, непредсказуемость результата которых проистекает от комбинаторных причин. В них имеется огромное количество вариантов, и проанализировать их в течение разумного промежутка времени невозможно даже с привлечением современной компьютерной техники. Примером игры с комбинаторной сложностью и с большим количеством вариантов являются шахматы. 2. Случайная (игроки не знают, что происходит в игре). Случайное может появляться либо в результате действия внешних (по отношению к участникам игры) сил: рассеивание попаданий при стрельбе по мишеням, метеорологические условия, случайные обстоятельства того или иного характера2, либо в результате сознательных поступков игроков, запутывающих процесс игры специально организованными действиями: бросание монеты или игральной кости, тасование карт, использование рулетки или другого механизма для выбора случайного числа. Игры, в которых неопределенность исхода связана со случайностью, называются азартными играми. Примерами могут служить орлянка, кости, рулетка. Встречается, и нередко, сочетание комбинаторной сложности со случайной, например, карточные пасьянсы — неопределенность в них имеет двоякую природу: это и случайное расположение карт в колоде, и огромное число вариантов конфигураций, составленных из открытых карт на столе. 3. Стратегическая (игрок не знает, как будут вести себя другие игроки). Данный вид неопределенности — стратегическая неопределенность очень важен при исследовании явлений социально-экономической сферы. Здесь неопределенность вплетена в саму суть игры — игрок должен делать ход, не имея информации о том, какой ход сделал его партнер, либо участники делают ходы одновременно, не сговариваясь друг с другом. Стратегические игры в их чистом виде встречаются редко — чаще можно встретить их смешанные варианты. Например, (1) Морской бой: неопределенность стратегическая + комбинаторная. (2) Покер: неопределенность стратегическая + стохастическая. (3) Преферанс: неопределенность стратегическая + стохастическая + комбинаторная. 2 Например, случайные потоки требований в обслуживающую систему; случайные потоки денежных средств в банковскую систему или на предприятие и т.д.
Стр.9
10 Введение Попытки объединить теорию игр с комбинаторикой привели к новым областям исследования, в которых определенные ограничения на правила игры дают возможность эффективно решать поставленные задачи. 2. Комбинаторные игры. Семейство комбинаторных игр состоит из игр двух лиц с совершенной информацией (нет скрытой информации, как в некоторых карточных играх: все возможные ходы, а также история игры известны обоим игрокам), в которых нет случайных устройств (т.е. нет игральных костей или тасования карт); игроки делают ходы поочередно; игра всегда заканчивается, даже если игроки не будут чередовать ходы; результатом может быть только выигрыш–проигрыш и победителя определяет последний ход: в нормальной игре выигрывает игрок, сделавший последний ход, в игре мизер тот, кто сделал последний ход, проигрывает. Вот примеры игр, которые не подпадают под эти правила: игра го, так как по окончании партии подсчитываются очки, и последний ход не гарантирует игроку, что у него окажется наибольшее или наименьшее количество очков; шахматы, так как шахматная партия может закончиться вничью; нарды, так как в них присутствует элемент случайности (игральная кость); бридж — единственное свойство этой игры, совпадающее с перечисленными выше признаками комбинаторной игры, — это то, что партия в бридж всегда заканчивается. Тем не менее принципы теории комбинаторных игр могут быть применены и к шахматам, шашкам, го и др., хотя эти игры слишком сложны, чтобы исследовать их полностью. Перечислим тех ученых, кто внес значительный вклад в современное представление о комбинаторной игре. Чарльз Баутон (Charles Bouton), Эрнст Цермело (Ernst Zermelo), Эммануил Ласкер (Emmanuel Lasker), Патрик Гранди (Patrick Grundy), Роланд Шпраг (Roland Sprague), Седрик Смит (Cedric Smith), Ричард Гай (Richard Guy), Джон Конвей (John Conway), Элвин Берлекэмп (Elwyn Berlecamp), Авезри Френкель (Aviesri Fraenkel). Игры, полностью подпадающие под определение комбинаторных игр, это ним, амазон, клоббер, гекс.3 На самом деле, игры ним, амазон и го обладают свойством, которое делает теорию чрезвычайно полезной для анализа этих игр. Доска делится на различные компоненты, и игрок выбирает, в какой компоненте играть. Более того, его противник не обязан отвечать в той же компоненте. Вот почему так важно условие окончания игры, даже если игроки не будут чередовать ходы. Данное свойство настолько важно, что отражено в следующем определении. 3 Игра ним рассматривается подробно в §1, гекс — в §5. В игре амазон, протекающей на шахматной доске, участвуют белые и черные фигуры—амазонки. Ход амазонки состоит из двух частей. Первая часть — движение фигуры по правилам, по которым ходит шахматный ферзь. Вторая часть — амазонка выпускает горящую стрелу, которая движется по тем же правилам (по горизонтали, вертикали или диагонали) и оставляет за собой выжженные поля, по которым уже невозможно ходить. Игроки ходят по очереди амазонками своего цвета, и проигрывает тот, кто не может сделать ход. Игра клоббер происходит на прямоугольной шахматной доске n Ч n, причем в начале игры на всех белых клетках стоят белые фишки, на черных клетках — черные. Игроки по очереди делают ходы, заключающиеся в том, что игрок фишкой своего цвета бьет соседнюю (по вертикали или горизонтали) фишку противника. Проигрывает тот, кто не может сделать ход.
Стр.10
3. Исторические замечания 11 Дизъюнктивной суммой игр G и H называется игра G+H, в которой игрок может выбрать, играть ему в G ли в H. Как правило, если позиция игры разбивается на компоненты, так что игра распадается в дизъюнктивную сумму, то теория будет полезной. Если же игра не представима дизъюнктивной суммой, применимость теории более ограниченна. Среди комбинаторных игр выделяются два больших класса: беспристрастные игры — в них любой ход, доступный одному игроку, доступен и другому (например, ним); и пристрастные игры, свободные от этого условия — в них, например, один игрок управляет черными фигурами, а другой — белыми. Основная цель теории — определить значение каждой компоненты, которое, в сущности, представляет собой количественное выражение преимущества позиции одного из игроков, положительное или отрицательное, в зависимости от того, имеется ли реальное преимущество, или же преимуществом владеет противник. Важным понятием является равенство игр. Две игры считаются одинаковыми, если игрокам безразлично, играть в одной или в другой. Аксиома равенства: G = H если, и только если для любой игры X результат игры G + X тот же, что и результат игры H + X. В теории комбинаторных игр имеются четыре направления исследований: беспристрастные игры с нормальным условием окончания; пристрастные игры с нормальным условием окончания; беспристрастные игры с условием окончания мизер; пристрастные игры с условием окончания мизер. Введением в теорию комбинаторных игр могут служить электронные публикации [21, 20]. 3. Исторические замечания. Считается, что первым своим появлением комбинаторные игры в виде математической задачи обязаны известному популяризатору математики Баше де Мезирьяку, который привел в своем «Сборнике математических развлечений»4, вышедшем во Франции в 1612 г., задачу: Два игрока называют поочередно произвольные числа в пределах от 1 до 10 и ведут подсчет суммы всех названных чисел. Выигрывает тот, кто сумеет первым довести до ста эту сумму. Далее теория комбинаторных игр развивалась как теория беспристрастных игр. Эрнст Цермело показал [19], что в играх двух лиц с совершенной информацией, завершающихся за конечное число ходов, либо первый игрок имеет выигрывающую стратегию, либо второй игрок имеет выигрывающую стратегию. В действительности теорема Цермело относилась к играм, в которых допускались ничьи и бесконечные повторения ходов (динамические ничьи), так что в ее формулировке либо игра выигрышна для первого игрока, либо для второго игрока, либо каждый игрок может играть так, чтобы форсировать ничью. Наконец, Чарльз Баутон в 1902 г. впервые дал полный анализ некоей комбинаторной игры, названной им ним [10], что послужило начальным пунктом развития теории. После этого появилась мода на изобретение комбинаторных игр и их решение. Некоторые из предложенных игр были очень интересными и имевшими связи с другими областями математики, но уводящими в сторону с пути 4 Клод Гаспар Баше, Claud Gaspard Bachet, Probl` emes plaisants et d` electables, 1612.
Стр.11
12 Введение развития общей теории: игра Витгоффа, ним Мура. В правильном направлении была придумана игра ним Ласкера, опубликованная им в 1931 г. Идеи буквально «носились в воздухе». Роланд Персифаль Шпраг в 1935 г. и Патрик Майкл Гранди в 1939 г.5 независимо друг от друга опубликовали полное решение задачи определения оптимальной стратегии в беспристрастных играх [15, 12]. Они доказали, что все беспристрастные игры могут быть классифицированы, поставив в соответствие каждой игре (и каждой позиции в игре) некоторое числовое значение. Впоследствии это стало известно как теория Шпрага–Гранди, а значение, связанное с беспристрастной игрой, — значением Гранди. Так как это значение равно размеру нимкучи, эквивалентной данной игре, то его иногда называют ним-значением игры. К несчастью, из-за ситуации в мире в то время, их работы не были восприняты современниками с тем вниманием, которое они заслуживали. В 1960-х гг. Элвин Берлекэмп, Джон Конвэй и Ричард Гай совместно разработали теорию пристрастных игр. Их результаты были опубликованы в их книге [1], первое издание которой, двухтомное, вышло в 1982 г. Второе издание, уже четырехтомное, вышедшее в 2001–2004 гг., справедливо считается энциклопедией теории комбинаторных игр. Однако первой книгой, посвященной данной теме, была книга Дж. Конвея [2]; в ней вводилось понятие сюрреального числа и его обобщение на комбинаторные игры. Всех трех авторов теории пристрастных игр вдохновляла классическая игра Го. 4. Древние и современные игры. В Китае игра го под именем weiqi известна более 2500 лет. При династии Хань (с 206 года до н.э.) игра го использовалась для приобщения офицеров к военному искусству. Учителя игры были разделены на три категории. В VIII веке при династии Тан была введена почетная степень по го в императорской академии. Терминология, используемая знатоками этой игры, чрезвычайно богата и «сравнима с богатством живого языка».6 «Богатство игры го выходит за чисто игровую область, ибо она служит еще удивительной моделью анализа социальноэкономических законов и военных операций». Сегодня многие специалисты убеждены, что в свойствах и достоинствах игры го как моделях поведения надо искать одно из объяснений экономических успехов Японии, Кореи и Китая в масштабах планеты ... Эта игра только в XX веке распространилась по всему миру и сейчас является по общему числу игроков одной из самых распространенных настольных игр на Земле. В го играют на прямоугольной доске, расчерченной на 19 вертикальных и 19 горизонтальных линий. У каждого из двух игроков имеется набор камней (фишек) — черного и, соответственно, белого цвета. Игроки поочередно выставляют свои камни на любой свободный пункт доски (т.е. незанятую точку пересечения линий). Камни не двигаются, но могут быть захвачены противником, если тот окружит их камнями своего цвета. Цель игры — отгородить на доске своими камнями б´ территорию, чем противник. 5 Roland Percival Sprague; Patrick Michael Grundy. 6 Pascal Reysset, Les jeux de r´ eflexion pure. Presses universitaires de France, Paris. (1995). ольшую
Стр.12
4. Древние и современные игры 13 Результат игры определяется подсчетом очков. По одному очку дается игроку за каждый из пунктов доски, окруженных камнями его цвета, а также за каждый захваченный камень противника, либо за каждый собственный камень, который остался на доске. Игрок, набравший больше очков, выигрывает. Игра го интересна еще и тем, что оказалась наиболее сложной для компьютера. Даже лучшие из существующих программ проигрывают средне играющим любителям. Сложность игры го для компьютера (по сравнению, например, с шахматами) обусловлена следующими факторами: • Большое число вариантов ходов. В шахматах в начальной позиции существует 20 разных ходов, в го — 55, с учетом симметрии доски. Дерево вариантов • Сложность формализованной оценки позиции. В шахматах давно и достаточно точно определена сравнительная ценность фигур и выработаны форНа текущий момент наибольших успехов в игре против профессиональных игроков в го достигла программа MoGo, сумев несколько раз добиться выигрыша. 7 августа 2008 года MoGo выиграла игру против корейского профессионала Kim MyungWan, 8p, имея фору в 9 камней. В феврале 2009 года MoGo добилась еще большего: с форой в 7 камней она победила игрока 9 дана Jun-Xun Zhou, а с форой в 6 камней — игрока первого дана Li-Chen Chien. Но, тем не менее, фора есть фора . . . Несколько серьезнее заявки наиболее сильных шахматных программ. Шахматный суперкомпьютер Deep Blue, разработанный компанией IBM, в мае 1997 года одержал победу в матче из 6 партий с чемпионом мира по шахматам Гарри Каспаровым. Немецкая шахматная программа Deep Fritz, в 1995 году выигравшая Чемпионат мира по шахматам среди компьютерных программ в Гонконге, победила в декабре 2006 года чемпиона мира по классическим шахматам Владимира Крамника в шести партиях со счетом 4–2. Что касается игры в шашки, то в 2007 году была была опубликована статья в журнале Science Express7 , в которой группа исследователей, возглавляемая Джонатаном Шеффером из Канады, объявила, наконец, после 18 лет напряженной работы, об успешном завершении решения игры в английские шашки8: Если двое игроков играют безошибочно, то результатом игры является ничья. Это наиболее сложная из популярных игр, решенная к настоящему времени: по приблизительным подсчетам, число позиций в шашках имеет порядок 5 · 1020. Развлекаться игрой — словосочетание, которое звучит очень легкомысленно. Но факт — то, что ряд интересных и естественных математических труднореша7 Schaeffer J. et al. Checkers Is Solved// Science Express, 14 September 2007, Vol. 317, No. 5844, pp. 1518–1522. 8 Английские шашки (в Америке называемые чекерс) располагаются на доске 8×8, и от русских шашек отличаются тем, что бить могут только вперед, а дамка может ходить только на одну клетку по диагонали (вперед или назад) и бить только через одну клетку в любую сторону. при расчете на несколько ходов вперед в го растет существенно быстрее. В шахматах после четвертого полухода может возникнуть порядка 105 позиций, в го число таких позиций имеет порядок 1, 6 · 1010. мальные критерии оценки позиции, а в игре го оценка позиции чрезвычайно сложна.
Стр.13
14 Введение емых задач дают игры двух лиц, а иногда игры одного лица (головоломки) или даже нуля лиц (игра Конвея «Жизнь»). Помимо естественной привлекательности предмета, имеются приложения и связи комбинаторных игр с различными областями, включая логику, сложность алгоритмов, графы, сети, коды, исправляющие ошибки, сюрреальные числа, алгоритмы, эволюционную биологию, а также анализ и разработку математических и коммерческих игр. Интересно, что новоизобретенные комбинаторные игры, например, амазон и клоббер (годы их рождения — 1988 и 2001, соответственно) имеют своих приверженцев, среди которых проводятся международные турниры. Мы выбираем игры не потому, что они представляются нам простыми и очевидными; скорее всего, дело в том, что они обеспечивают максимальную сложность при минимальной исходной структуре. Так что не удивительно, что мастерство в таких играх, как шашки, шахматы, го, с давних времен рассматривается как отличительная черта человеческого интеллекта. Принцип недостаточной причины (или принцип индифферентности, как назвал его Дж. Кейнс в своей книге «Исследования по теории вероятностей»9), формулируется следующим образом: если нет никаких оснований считать какое-либо из n взаимоисключающих событий более вероятным, чем любое другое, то каждому из этих событий следует приписать вероятность 1/n. Руководствуясь данным принципом, возможно неосознанно, игрок априорно оценивает свои шансы как равные с шансами другого игрока, в силу чего он бывает готов помериться силами даже с более умным и опытным противником. 9 Keynes J.M., Treatise on Probability, 1921. Кейнс больше известен как экономист, но его книга по теории вероятностей тоже стала классической.
Стр.14
Часть I. Беспристрастные игры § 1. Простейшие комбинаторные игры Игра ним — Что такое комбинаторная игра — P-позиции и N-позиции — Игры вычитания — Ним-значения — Ним мизер — Приложения — Задачи В сюрреалистическом фильме «В прошлом году в Мариенбаде»1 один персонаж (мистер M) объясняет окружающим (в том числе некоему мистеру X) правила одной простой игры. M раскладывает на столе карты в четыре ряда в треугольном порядке: | | | | | | | | | | | | | | | | Правила таковы: игроки (их двое) по очереди берут любое ненулевое количество карт, но обязательно из одного только ряда. Тот, кто берет последнюю карту, проигрывает. M по-джентльменски уступает право первого хода X, но выигрывает. То же повторяется и во второй раз (со спичками вместо карт). В третьей партии M ходит первым, но все равно выигрывает.2 Эта игра называется ним. 1. Игра ним. Ним — одна из старейших комбинаторных игр; кроме того, ним — фундамент, на котором воздвигается математическая теория комбинаторных игр. Название «ним» и исчерпывающую теорию этой игры дал Чарльз Л. Баутон (C.L. Bouton), математик из Гарвардского университета, более 100 лет назад [10].3 Два игрока поочередно берут предметы (карты, спички, камешки, монеты — словом, фишки) из кучек (рядов, коробок). Число кучек и число предметов может быть произвольным, и выкладываются они заранее, до начала игры. Взять разрешается любое число предметов из любой кучки: даже всю кучку целиком, но хотя бы один предмет взять обязательно, и брать предметы можно только из одной кучки. Игрок, взявший последний предмет, выигрывает игру.4 Существуют различные модификации правил игры, о которых речь будет идти ниже, — они приводят к различным версиям нима. Менее приятно наличие расхождений в терминологии. Так, большинство авторов называют позицию выигрышной, если игрок, делающий в ней ход, может форсировать выигрыш. Харди и 1 Фильм режиссера Алена Рене “L’Ann´ ee derni` ere ` а Marienbad” (“Last Year at Marienbad”) получил на Международном кинофестивале в Венеции в 1961 г. премию «Золотой лев». 2 Ходы игроков во всех трех играх указаны в приложении 1 к параграфу. 3 В некоторых публикациях, например, в [8], эта игра называется «фан-тан». См. по этому поводу приложение 2 к параграфу. 4 Именно такое правило — победителем объявляется игрок, делающий последний ход — считается стандартным (или нормальным), в отличие от игры в фильме Рене. 15
Стр.15
16 § 1. Простейшие комбинаторные игры Райт в своем классическом учебнике теории чисел [3], напротив, называют такую позицию проигрышной, объясняя название тем, что игрок проигрывает, если своим ходом пойдет в эту позицию. К настоящему времени установилась традиция называть подобную позицию N-позицией, т.е. дающей преимущество следующему (next) игроку, в отличие от P-позиций, дающих преимущество предыдущему (previous) игроку. Баутон, а затем Витгофф [17] называли P-позицию безопасной (safe), так как в нее ходить безопасно; а N-позицию — небезопасной: в нее ходить опасно.5 Позиция в ниме записывается путем перечисления размеров имеющихся кучек, например, (a, b, c) — позиция, в которой есть три кучки, в первой a предметов, во второй b, а в третьей — c. Назовем позицию выигрышной, если в ней очередь хода принадлежит игроку, который может довести игру до выигрыша, играя наилучшим образом.6 Любую другую позицию назовем проигрышной. Какой бы ход игрок в проигрышной позиции ни сделал, его противник сможет выиграть, если будет делать рациональные ходы. Рациональный (т.е. наилучший) ход в выигрышной позиции состоит в том, что игрок должен оставить своему противнику проигрышную позицию. Пример 1. Следующие позиции проигрышные: || || | || ||| →(1, 2, 2)→(2, 2) I II т.е. (2, 2), (1, 2, 3). Начавшись в последней позиции, игра может развиваться таким образом: (1, 2, 3) I →(1, 2)→(1, 1) I II →(1)→(0) II — игрок I, делавший первый ход, проигрывает. Если в игре остается одна непустая кучка, то игрок при своем ходе берет из нее все предметы и выигрывает. Так что позиция (m), m > 0 — выигрышная. Предложение 1. В игре ним позиция (m, n) выигрышная, если m  n, и проигрышная, если m = n. Доказательство. Если в игре две кучки одинаковых размеров, то игрок, делающий ход, проигрывает, потому что второй игрок имеет возможность копировать действия первого игрока, уравнивая размеры кучек. Если размеры кучек разные, то первый игрок, забирая из большей кучки необходимое число предметов, оставляет второму игроку проигрышную позицию.  Предложение 2. Если в игре ним кучки содержат по одному предмету каждая, то позиция выигрышная при нечетном числе предметов и проигрышная при четном.  Назовем четной позицией такую позицию, в которой, если количество предметов в каждой кучке записать в двоичной системе счисления и расположить числа столбиком, то при суммировании каждого столбца цифр получится четное число. В противном случае позиция — нечетная. Пример 2. 5 См. также главу 14 книги Мартина Гарднера [7]. 6 В следующем ниже кратком разборе игры ним мы следуем Харди и Райту [3, с. 117–120]; однако изменяем терминологию на диаметрально противоположную, поскольку она, по нашему мнению, более соответствует смыслу используемых слов. Позже мы исследуем теорию игры ним более детально.
Стр.16
§ 2. Игры на графах. Функция Шпрага–Гранди Ориентированные графы — Игры на графах — Функция Шпрага–Гранди — Функция Шпрага–Гранди на более общих графах — Симметричные графы и хроматические числа — Задачи 1. Ориентированные графы. Введем некоторые понятия, имеющие смысл для бесконечных ориентированных графов и относящиеся к различным видам конечности и ограниченности числа ветвей или длин путей. Ориентированный граф можно задать парой G = (X, F), где X — непустое множество вершин, а F — функция следования, ставящая в соответствие каждой вершине x ∈ X некоторое подмножество X: F(x) ⊂ X. Если F(x) = ∅, вершина x называется терминальной. Данный способ задания графа предложил Клод Берж [4, 5]. Обычно вершины изображаются точками плоскости, а пары вершин x, y, такие, что y = F(x), соединяются непрерывной линией (дугой) со стрелкой, направленной от x к y. Можно рассматривать также функцию предшествования F−1. Аргументы функций следования и предшествования часто будем записывать без скобок: Fx, F−1y. Пример 1. Для графа, изображенного на рис. 1а, X = {a, b, c, d, e, f }, Fa = {b, d, f }, Fb = {a, c}, Fc = ∅, Fd = {d}, Fe = {c, e}, F f = {a, b, e}. a a f e d а Рис. 1 F−1c = {b, e} и т.д. Заметим, что данный граф содержит 2 антипараллельные дуги и 2 петли. Легко вычисляются также значения функции F−1: F−1a = {b, f }, F−1b = {a, f }, Функция F (или F−1) представляет бинарное отношение на множестве X, которое может быть записано в виде матрицы (или таблицы). Для вышеприведенного примера соответствующая таблица приведена на рис. 1б. Порядком графа называется число |X| всех вершин графа. В бесконечном ным, если |X| < ∞. Граф называется прогрессивно конечным, если для любой вершины x ∈ X всякий путь, начинающийся в x, имеет конечную длину. 31 случае это кардинальное число, мощность множества X. Граф называется конечb c a b c d e f б b c d e f
Стр.31
32 § 2. Игры на графах. Функция Шпрага–Гранди Граф называется прогрессивно ограниченным, если для любой вершины x ∈ X найдется положительное целое n такое, что всякий путь, начинающийся в x, имеет длину  n. Прогрессивно ограниченный граф всегда прогрессивно конечен, но не наоборот. Контуров в прогрессивно конечном или прогрессивно ограниченном графе нет. Аналогично, исходя из рассмотрения путей, заканчивающихся в некоторой вершине, вводятся понятия регрессивной конечности и регрессивной ограниченности (рис. 2). Граф называется F-конечным, если |Fx| < ∞ для всех x ∈ X, и F−1-конечным, если |F−1x| < что |Fx| < m для всех x ∈ X. ω ∞ для всех x ∈ X. Если граф является F-конечным и F−1-конечным, то он называется локально конечным. Граф называется F-ограниченным, если существует положительное целое число m такое, 0 1 2 3 а 4 5 6 0 1 2 3 б Рис. 2: Бесконечные графы: а — F-ограниченный и прогрессивно ограниченный, но не F−1-конечный и не регрессивно конечный; б — прогрессивно конечный, но не прогрессивно ограниченный В случае конечных графов условия прогрессивной конечности, прогрессивной ограниченности, регрессивной конечности и регрессивной ограниченности эквивалентны между собой и сводятся к тому, что в графе нет контуров. Теорема 1. Если граф G = (X, F) прогрессивно ограничен, то существует функция l : X → такая, что (1) l(y) < l(x) для всех x ∈ X, y ∈ Fx; (2) l(x) = 0 для всех x ∈ X таких, что Fx = ∅. Доказательство. Пусть граф G = (X, F) прогрессивно ограничен. Тогда в силу определения для каждой вершины x ∈ X найдется число l(x), равное длине самого длинного пути, начинающегося в x. В частности, если x — терминальная вершина, l(x) = 0.  Будем называть l(x) уровнем вершины x. Множество всех вершин X разбивается на множества Xn = {x ∈ X : l(x) = n} вершин фиксированного уровня. Отметим, что, в силу свойства (1), уровень опции меньше (хотя бы на единицу) уровня позиции. Пример 2. Выпишем для представленного ниже (рис. 3) бесконтурного ориентированного графа опции вершин, функцию уровня и P/N-разбиение соответствующей игры: x A B C D E F G H I J K L M N F(x) B,C,D E,F G,H F,G F G,I,J H,K,L J,M J,L,M N M l(x) o(x) 8 7 5 6 6 5 4 0 1 0 3 2 0 1 N N N P P N N P N P N P P N 4 5 6
Стр.32
§ 3. Изоморфные игры Примеры: Нимбл, миндальный пирог, игра Норткотта, нимбл (вторая версия) — Изоморфизм игр и другие виды эквивалентности игр — Модельная эквивалентность игр — Игры как множества — Задачи 1. Примеры. Рассмотрим несколько комбинаторных игр. В их описании нет необходимости каждый раз повторять, что в игре участвует два игрока, которые ходят по очереди, и выигрывает тот, кто сделал последний ход. Пример 1. Игра нимбл (рис. 1). На ленте, расчерченной на клетки, есть несколько монет. Число клеток конечно. Монеты находятся в клетках, и в одной клетке может быть несколько монет. Ход состоит в перемещении любой монеты влево по ленте на любое число клеток, не обращая внимания на другие монеты. Пронумеруем клетки слева направо, начиная с 0. 0 1 2 3 - - 4 5 6 7 - - Рис. 1: Позиция игры нимбл Сначала предположим, что на ленте находится одна монета в клетке x. Игрок, чья очередь хода, может переместить ее в самую левую клетку, 0, что приводит к выигрышу. Подобный ход совершает игрок в игре ним, если остается одна куча с x предметами в ней. Это подсказывает решение игры. Пусть монеты находятся в клетках x1, x2, . . . , xn. Тогда каждый ход уменьшает одно из чисел xi, 1  i  n. Абсолютно идентичные действия происходят и в игре ним. Поэтому с математической точки зрения игры ним и нимбл не отличаются друг от друга. Выражаясь точнее, между множествами позиций этих игр можно установить взаимно однозначное соответствие так, что ход из одной позиции в другую в одной игре соответствует ходу из аналогичной первой позиции в аналогичную вторую позицию, но уже в другой игре. В таком случае игры называются изоморфными. Пример 2. Игра миндальный пирог (рис. 2). Имеется миндальный пирог прямоугольной формы, в виде квадратиков, один из которых заплесневел. Игроки в 8 9 10 11 - 12 13 14 - Рис. 2: Позиция игры миндальный пирог 44
Стр.44
1. Примеры 45 свою очередь хода режут пирог по прямой линии — вертикальной или горизонтальной — разделяющей квадратики, и съедают ту часть, в которой нет заплесневелости. Игра заканчивается, когда остается один квадратик, несъедобный. Будем анализировать игру, начиная с простейших позиций. (1) Сначала рассмотрим прямоугольник n Ч 1. 1 Ч Ходом в данной позиции служит отрезание справа любого числа клеток, при котором слева остается не менее одной клетки. Аналогичные ходы имеются в позиции (n−1) игры ним (с одной кучей). Если «неприкасаемая» клетка находится в середине, 1 k Ч то «подбираться» к ней возможно с двух сторон, независимо друг от друга, что аналогично позиции (k − 1, n − k) нима. (2) Теперь рассмотрим прямоугольник 2 Ч 3 с отмеченной клеткой в левом нижнем углу. Ч Игра должна протекать так1: 2 Ч 3 I → 2 Ч 2 → 1 Ч 2 I и в случае прямоугольника m Ч n есть два независимых числа, которые могут уменьшаться до 1. Соответствующая ним-позиция — (m − 1, n − 1). (3) В общем случае выберем систему координат: «неприкасаемую» клетку II поместим в начало, (0, 0), и (считая, что координаты2 возрастают: первая слева направо, вторая снизу вверх) найдем минимальные и максимальные значения координат. Пусть ими будут (−a,−b) и (c, d) (рис. 3). Ход в игре уменьшает одно (-a,-b) -b 0 d c (c,d) Рис. 3: Введение в игру системы координат из чисел a, b, c, d. Запишем позицию в виде вектора (a, b, c, d); опциями данной позиции являются: (a− x, b, c, d) (отрезание слева x клеток, 0 < x  a), (a, b− x, c, d) 1 Буквой T помечена терминальная позиция, I и II — номера игроков. 2 Координаты приписываем не точкам, а клеткам. -a 0 → 1 Ч 1 T. Ясно, что n n
Стр.45
§ 4. Сложение игр. Эквивалентные игры Сумма игр — Эквивалентность игр по Шпрагу–Гранди — Ним-сложение — Эквивалентность игр ниму — Игры взятия как суммы игр вычитания — Группа игр — Задачи Будем рассматривать нормальные беспристрастные игры без ничьих. Такие игры полностью определяются своими правилами и начальной позицией. Нас интересует разбиение позиций каждой игры на P- и N-позиции. Таким образом, при фиксированной начальной позиции каждая игра относится к классу P- или N-игр. Игру ним с начальной позицией, состоящей из одной кучи из n предметов, обозначим ∗n. Наша цель — показать, что на множестве игр можно определить отношение эквивалентности, причем так, что каждая игра окажется эквивалентной одной из игр ∗n, n ∈ . Мы предполагаем, что множество позиций в каждой игре конечное.1 1. Сумма игр. Определим сумму двух игр следующим образом. Будем разыгрывать обе игры, комбинируя их. Ходы делаются двумя игроками по очереди. Ход заключается в том, что игрок выбирает одну из двух игр и делает в ней ход, ничего не меняя в другой. Следующий игрок также выбирает одну из игр, возможно ту же самую, или другую, и делает в ней ход. Выбор, в какой из игр сделать ход, совершенно произволен и не зависит от того, в какой игре был сделан предыдущий ход. Игра продолжается до тех пор, пока один из игроков не сможет сделать ход ни в одной из игр. Игрок, у которого не осталось ходов, считается проигравшим.2 Приведем формальное определение. Каждую игру можно представить в виде игры на графе. Пусть G1 = (X1, F1) и G2 = (X2, F2) — два графа соответствующих игр. Определение 1. Суммой G1 +G2 графов называется граф G = (X, F), множество вершин которого есть X = X1×X2, а функция следования определена формулой F(x) = (F1(x1) Ч x2) ∪ (x1 Ч F2(x2)) для любой вершины x = (x1, x2) ∈ X. Игра на графе G называется суммой игр на графах G1 и G2. Если графы G1 и G2 прогрессивно ограничены, то и граф G прогрессивно ограничен. Если позиция x1 первой игры имеет r1 опций, F1(x1) = {x11, . . . , x1r1 позиция x2 второй игры — r2 опций, F2(x2) = {x21, . . . , x2r2 их суммы имеет r1 + r2 опций, образующих множество F(x) = {(x11, x2), (x12, x2), . . . (x1r1 игр. , x2), (x1, x21), (x1, x22), . . . (x1, x2r2 )}. Разумеется, точно так же можно определить и сумму любого конечного числа Ясно, что сумма двух (или более) игр ним — тоже игра ним: например, (2, 5, 7)+(3, 4, 8) = (2, 5, 7, 3, 4, 8). Игра ним с тремя кучами может быть представлена в виде суммы трех игр ним с одной кучей: (2, 5, 7) = (2) + (5) + (7) или ∗2 + ∗5 + 1 Это позволит нам не выходить за пределы ряда натуральных чисел  и не оперировать с трансфинитными числами. 2 Существуют и другие способы комбинирования игр. См., например, [2, гл. 14]. 54 }, то позиция x = (x1, x2) }, а
Стр.54
2. Эквивалентность игр по Шпрагу–Гранди 55 ∗7 в принятых нами обозначениях. Так что игру ним в позиции (m, n, k) можно записать как ∗m+∗n+∗k. Это показывает, что даже если каждая компонента игры тривиальна, сумма может быть сложной. Теорема 1. Сумма двух P-игр является P-игрой, сумма N-игры и P-игры — N-игрой. (Однако, относительно суммы двух N-игр ничего определенного сказать нельзя.) Доказательство. Неформально, сложение с P-игрой не меняет P/Nхарактеристики игры. Действительно, в сумме двух P-игр первый игрок обязан выбрать игру и сделать в ней ход в N-позицию. Тогда второй игрок может перевести эту N-позицию в P-позицию. Так что у второго игрока всегда есть ходы, и он выигрывает; исходная позиция в сумме двух игр является P-позицией. Если же рассматривается сумма N-игры и P-игры, то первый игрок делает ход в первой игре в P-позицию и предоставляет в сумме игр своему противнику (согласно предыдущему рассуждению) P-позицию. Формальное доказательство проводится с использованием двойной индукции по потомкам начальных позиций первой и второй игр. Пусть x1, x2 — начальные позиции первой и второй игр соответственно, множества опций которых суть F1(x1) и F2(x2). суть N-позиции. Всякая опция суммы двух игр G1 +G2 — это либо (x (x1, x позиций утверждение теоремы считается истинным. Но в новых позициях (x и (x1, x 2), где x 1 ∈ F1(x1) и x Предположим, что обе начальные позиции — P-позиции. Тогда все их опции 1, x2), либо Так мы заключаем относительно суммы двух игр, что все ее опции являются Nпозициями, а она сама есть P-игра. (x1, x2) игры G1 +G2 существует опция (x 2) позиция одной игры-компоненты есть P-позиция, а другой — N-позиция. 2 ∈ F2(x2). Согласно предположению индукции, для таких 1, x2) а начальная позиция x2 второй игры — P-позиция. Тогда в первой игре найдется опция x ющаяся P-позицией. Следовательно, в данном случае G1 +G2 есть N-игра.  2. Эквивалентность игр по Шпрагу–Гранди. Рассмотрим класс всех нормальных беспристрастных комбинаторных игр. Каждая игра из данного класса характеризуется своими правилами и начальной позицией. Будем отождествлять изоморфные игры — в них поведение игроков с логической точки зрения абсолютно одинаково. И когда речь будет идти о равенстве двух игр, запись G = H будет означать, что игры G и H изоморфны. Ясно, что операция сложения игр коммутативна и ассоциативна с точностью до изоморфизма, поэтому для любых трех игр G, H и K мы имеем право записать G + H = H +G, G + (H + K) = (G + H) + K. Существует нейтральный элемент, который можно складывать с любой игрой, не изменяя ее с точностью до изоморфизма — это пустая куча в ниме ∗0: G + ∗0 = G. Предположим теперь, что начальная позиция x1 первой игры — N-позиция, 1 ∈ F1(x1), являющаяся P-позицией; стало быть, для начальной позиции 1, x2), по предположению индукции явля
Стр.55
§ 5. Примеры игр Игры взятия с одной кучей — Ладейная игра — Игра Цзяньшицзы — Игра «Евклид» — Игра слитер («ползунок») — Игра чомп («щёлк») — Бридж-ит — Игра гекс — Нимk (или Ним Мура) — Приложение — Задачи 1. Игры взятия с одной кучей. Пример 1. «Четное-если-не-все — все-если-нечетное». Правила разрешают взять (1) любое четное число предметов, если это не вся куча или (2) всю кучу, если в ней нечетное число предметов. Терминальные позиции — 0 и 2. Начало последовательности Шпрага–Гранди: x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 . . . g 0 1 0 2 1 3 2 4 3 5 4 6 5 7 6 . . . В общем случае g(2k) = k − 1, g(2k − 1) = k (k  1). Для доказательства используем индукцию. Если предметов x = 2k > 2, то опциями являются 2, 4, . . . , 2k − 2, а их g-значениями 0, 1, . . . , k − 2. Следовательно, g(2k) = k − 1. Если же x = 2k − 1 > 1, то Fx = {0, 1, 3, 5, . . . , 2k − 3}, g(Fx) = {0, 1, 2, 3, . . . , k − 1}, и g(2k − 1) = mex g(Fx) = k. 2. Ладейная игра. На шахматной доске, или, в более общей ситуации, на прямоугольной доске произвольного фиксированного размера стоит ладья (рис. 1) — шахматная фигура, которая может ходить по вертикали или по горизонтали, причем в данной игре только вниз или влево, на любое число клеток, но хотя бы на одну. Ходы игроков чередуются, и проигрывает игрок, который не может сделать ход. Пронумеруем клетки по горизонтали слева направо и по вертикали снизу вверх, начиная с 0. Терминальная позиция — (0,0). Рис. 1: Ладейная игра Вычислим значения функции Шпрага–Гранди для каждой позиции на шахматной доске и запишем их в таблице 8 Ч 8. 68
Стр.68
3. Игра Цзяньшицзы 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 0 3 2 5 4 7 6 2 2 3 0 1 6 7 4 5 3 3 2 1 0 7 6 5 4 4 4 5 6 7 0 1 2 3 5 5 4 7 6 1 0 3 2 6 6 7 4 5 2 3 0 1 7 7 6 5 4 3 2 1 0 Данная игра изоморфна игре ним с двумя кучами. Действительно, ладья, расположенная в позиции (a, b), может уменьшить вплоть до нуля число a ходом влево или b ходом вниз на любое положительное целое. Таким образом, ходы совершенно аналогичны ходам в ниме с двумя кучами a и b, т.е. ∗a+∗b: g(∗a+∗b) = a ⊕ b. Таблица, таким образом, может быть построена двумя способами: с помощью mex-правила и путем ⊕-сложения. 3. Игра Цзяньшицзы. Игра Цзяньшицзы («выбирание камней»)1 разыгрывается с двумя кучами предметов по следующим правилам. Двое игроков по очереди берут либо произвольное число предметов из одной кучи (хоть все сразу), либо одинаковое число предметов из каждой кучи (в обоих случаях не менее одного предмета). Выигрывает игрок, забирающий при своем ходе все оставшиеся предметы (что соответствует нормальному правилу окончания). Данная игра называется также игрой Витгоффа (Wythoff’s game) по имени голландского математика, опубликовавшего в 1907 г. в работе [17] полный анализ игры. Позиция игры — пара неотрицательных целых чисел (m, n). Ход заключается в том, что можно 1) вычесть из одного числа положительное целое; 2) вычесть из обоих чисел одно и то же положительное целое. Несложно показать, что эта игра эквивалентна игре «раненый ферзь» 2: на прямоугольной доске произвольного фиксированного размера стоит ферзь — шахматная фигура, которая в данной игре может ходить по вертикали вниз, по горизонтали влево или по диагонали вниз-влево, на любое число клеток, но хотя бы на одну (рис. 2). Ходы игроков чередуются, и проигрывает игрок, который не может сделать ход. 1 Проведенное автором исследование показало, что все ссылки на это название якобы «китайской народной» игры ведут к книгам: Яглом А.М. и Яглом И.М. Неэлементарные задачи в элементарном изложении. - М.: ГИТТЛ, 1954 (с. 64) и Доморяд А.П. Математические игры и развлечения. - М.: ГИФМЛ, 1961 (с. 59). До появления этих изданий слово цзяньшицзы ни в русской, ни в европейской литературе не фигурировало. Источники в Китае уверяют, что там также неизвестна игра с подобными правилами, а само слово не применялось ни к какой игре. Возможно, что название и приписывание китайским традициям придумано кем-то из вышеназванных авторов, по аналогии с нимом Баутона. 2 Эту игру изобрел примерно в 1960 г. американский математик Руфус П. Айзекс, ничего не знавший об игре Витгоффа. 69
Стр.69
§ 6. Несколько классов игр Игры взятия-разбиения: ним Ласкера, Кейлс, игра Гранди, шахматы Досона — Восьмеричные игры — Игра Хакенбуш — Задачи 1. Игры взятия-разбиения. В играх взятия-разбиения (take-and-break games) правила разрешают взять предметы из кучи и/или разбить одну кучу на две или более при соблюдении некоторых условий. Число куч, таким образом, может и уменьшаться (когда игрок берет все предметы из кучи), и увеличиваться (когда куча разбивается на части). Пример 1. Игра сплит-ним, или ним Ласкера. Обобщение игры ним с включением в нее правила разбиения привел в свое книге1 Эм. Ласкер.2 Есть несколько куч камней. За ход разрешается либо (1) взять любое положительное число камней из одной кучи, либо (2) разбить кучу на две новые непустые кучи. Первое правило — это правило нима, второе — чистое правило разбиения: при разбиении кучи брать из нее камни не разрешается. Терминальная позиция — 0, отсутствие куч. Определим значения функции Шпрага–Гранди для данной игры с одной кучей, содержащей x камней. Ясно, что g(0) = 0, g(1) = 1. При x = 2 опции образуют множество F(2) = {0, 1, (1, 1)}, значения Шпрага–Гранди опций — множество g(F(2)) = {0, 1, 0}3, g(2) = mex{0, 1, 0} = 2; при x = 3 имеем F(3) = {0, 1, 2, (1, 2)}, g(F(3)) = {0, 1, 2, 3, 3} и g(3) = mex{0, 1, 2, 3, 3} = 4. Для позиции x необходимо учесть ее опции Fx = {0, 1, 2, . . . , x−1, (1, x−1), (2, x−2), . . . , ([ x числить g(x) с помощью mex-правила. Вот подробные вычисления. x g(x) Fx 2], [ x+1 0 0 ∅ 1 1 0 2 2 0, 1, (1, 1) 3 4 0, 1, 2, (1, 2) 4 3 0, 1, 2, 3, (1, 3), (2, 2) 5 5 0, 1, 2, 3, 4, (1, 4), (2, 3) g(Fx) ∅ 0 0, 1, 0 0, 1, 2, 3, 3 0, 1, 2, 4, 5, 5, 0 0, 1, 2, 4, 3, 2, 6 6 6 0, 1, 2, 3, 4, 5, (1, 5), (2, 4), (3, 3) 0, 1, 2, 4, 3, 5, 4, 1, 0 Результаты вплоть до x = 12 приведены в следующей таблице. x 0 1 2 3 4 5 6 7 8 9 10 11 12 . . . g(x) 0 1 2 4 3 5 6 8 7 9 10 12 11 . . . 1 Brettspiele der V¨ Можно подметить следующую закономерность. olker (1931), 183-196. 2 Эммануил Ласкер — известный немецкий математик, чемпион мира по шахматам с 1894 по 1921 гг. 3 Это множество из двух элементов {0, 1}; мы повторяем 0, лишь следуя правилу образования данного множества как образа множества опций при отображении g. 80 2 ])}, их g-значения и вы
Стр.80
1. Игры взятия-разбиения любого k ∈  имеют вид g(4k + 1) = 4k + 1; g(4k + 2) = 4k + 2; g(4k + 3) = 4k + 4; g(4k + 4) = 4k + 3. Доказательство. Утверждение теоремы доказывается рассуждением, использующим индукцию. Предположим, что данные равенства: g(x) = x при x ≡ 1 или 2 (mod 4), g(x) = кучи, имеют g-значения 0, 1, . . . , 4k. Опции из двух куч сравнимы по модулю 4 покомпонентно с (1, 0) или (2, 3), а два младших бита их g-значений соответственно x + 1 при x ≡ 3 (mod 4), g(x) = x − 1 при x ≡ 0 (mod 4) — справедливы для x  4k. Пусть x = 4k + 1, т.е. x ≡ 1 (mod 4). Тогда опции x, состоящие из одной равны 1 ⊕ 3 = 2 и 2 ⊕ 0 = 2, так что эти g-значения четные. В результате, g(x) = mexg(Fx) = 4k + 1. Далее, для x = 4k + 2 опции x, состоящие из одной кучи, имеют g-значения 0, 1, . . . , 4k+1, а опции из двух куч сравнимы по модулю 4 покомпонентно с (1, 1), (2, 0) или (3, 3); два младших бита их g-значений соответственно равны 0, 2⊕3 = 1 и 0, т.е. g(Fx) ≡ 0 или 1 (mod 4). Таким образом, g(x) = 4k + 2. Пусть x = 4k+3. Тогда опции x, состоящие из одной кучи, имеют g-значения 0, 1, . . . , 4k + 2. Опции из двух куч сравнимы по модулю 4 покомпонентно с (2, 1) или (3, 0), два младших бита их g-значений соответственно равны 2 ⊕ 1 = 3 и 0 ⊕ 3 = 3, в частности, наибольшим среди g-значений является 4k + 2 ⊕ 1 = 4k + 3, так что g(x) = 4k + 4. Наконец, при x = 4k+2 опции x, состоящие из одной кучи, имеют g-значения 0, 1, . . . , 4k +2, 4k +4. Опции из двух куч сравнимы по модулю 4 покомпонентно с (0, 0), (1, 3) или (2, 2); два младших бита их g-значений соответственно равны 3⊕3 = 0, 1 ⊕ 0 = 1 и 2 ⊕ 2 = 0. Таким образом, g(Fx) ≡ 0 или 1 (mod 4). Следовательно, g(x) = 4k + 3.  Пример 2. Игра Кейлс (Kayles). Нарисуем несколько рядов палочек (кеглей). Каждый игрок своим ходом может зачеркнуть (стереть, взять) одну или две соседние палочки (т.е. сбить одну или две соседние кегли). Например, для позиции (3,4,3) игра может развиваться так: ||| |||| ||| → | |||| ||| → | | | ||| → . . . Такое представление игры относит ее к классу игр с палочками. Эту игру, придуманную Г.Э. Дьюдени более ста лет назад, а позже более обстоятельно изложенную в ряде книг4, можно представить как игру взятияразбиения. Имеется нескольку куч. На каждом ходе можно (1) удалить один или два предмета из одной выбранной кучи и, при желании, (2) разбить эту кучу на 4 Sam Loyd, Mathematical Puzzles of Sam Loyd, Vol 2., 1960, Dover Publications; H.E. Dudeney, The Canterbury Puzzles and Other Curious Problems, 1958, Dover Publications, New York. Перед двумя игроками выставлены в ряд 13 кеглей без одной кегли, второй по счету, которая уже сбита. “Предположим, что в старину игроки были настолько искусны, что могли сбить любую кеглю или две соседние кегли, не задевая остальных. Их удары чередовались, а тот игрок, который сбивал последнюю кеглю, признавался победителем.” (рис. 1). 81 Теорема 1. Значения функции Шпрага–Гранди для игры ним Ласкера для
Стр.81
§ 7. Игры переворачивания монет Одномерные игры переворачивания монет — Двумерные игры переворачивания монет — Шотландские игры — Поле нимберов — Задачи Игры переворачивания монет — класс игр, которые предложил рассматривать Хендрик Ленстра с целью получить удобную модель для определения алгебраических операций над играми (сложение, умножение, возведение в степень) [13] (см. также [1, 20]). В таких играх монеты, выложенные в ряд (один или несколько) переворачиваются по определенным правилам, пока у очередного игрока не останется ни одного разрешенного правилами хода. Для иллюстрации игр две стороны монеты надо обозначить какими-то двумя символами. Будем использовать буквы Λ и О.1 1. Одномерные игры переворачивания монет. Имеется конечное число монет, выложенных в ряд, одни вверх лицевой стороной (Λ), другие — оборотной (О). Ход заключается в переворачивании по определенным правилам нескольких монет, с лицевой стороны на оборотную, или наоборот, с оборотной на лицевую. В правилах всегда должно быть предусмотрено, что (1) Самая правая переворачиваемая монета переворачивается строго в фиксированном направлении — с лицевой стороны на оборотную (Λ→О). (2) Множество переворачиваемых монет зависит только от позиции самой правой переворачиваемой монеты, но не от того, где располагаются другие монеты, обращенные вверх лицевой или оборотной стороной, не от предыдущих ходов в игре, и т.д. Цель таких ограничений — гарантировать, что игра закончится за конечное число ходов независимо от воли игроков. Игра нормальная, беспристрастная: последний игрок, сделавший ход, выигрывает. Пример 1. Опрокидывание (Turning Turtles). По правилам можно переворачивать одну или две монеты, правую — с лицевой стороны на оборотную (Λ→О).2 Считаем монеты пронумерованными слева направо, начиная с единицы. Например, в позиции О Λ О О Λ О О О Λ Λ О Λ О 1 2 3 4 5 6 7 8 9 10 11 12 13 одним из возможных ходов является: перевернуть монету 9 Λ→О и монету 4 О→Λ. Терминальная позиция единственная: ОООООО.. . Эта игра эквивалентна игре ним. Возможна следующая декомпозиция игры: позиция, в которой k монет Λ находится на местах x1, . . . , xk, есть сумма k игр, в каждой из которых ровно одна монета Λ находится в i-й игре на месте xi. Например, игра 1 Выбор мог быть совершенно произвольным: Г(герб) и Р(решка), 0 и 1, + и -, H(head) и T(tail) — именно так стороны монеты часто обозначаются в англоязычных странах. Наш выбор диктуется тем, что переворачивание — это действие, в некотором смысле увеличивающее энтропию, и потому символ, не полностью симметричный в написании, в конце концов должен замениться на более симметричный: Λ→О; чему соответствует и смысл: Λ(лицевая сторона) и О(оборотная сторона). 2 Если переворачивается одна монета — также с лицевой стороны на оборотную. 100
Стр.100
1. Одномерные игры переворачивания монет 101 ООΛΛОΛ есть сумма трех игр, ООΛ, ОООΛ и ОООООΛ. Чтобы найти значение Шпрага–Гранди позиции игры, достаточно знать значения Шпрага–Гранди позиций ровно с одной монетой, обращенной лицевой стороной. Именно, g(ООΛΛОΛ) = g(ООΛ) ⊕ g(ОООΛ) ⊕ g(ОООООΛ). Многие игры могут быть представлены в форме игры переворачивания монет, хотя правила станут весьма сложными. Некоторые игры переворачивания монет — напротив, будучи представлены в форме игры с кучами, приобретут сложные правила. Простое описание в обеих формах имеют игры вычитания. Пример 2. Игры вычитания. Пусть задано множество вычитаемых S . Считаем, что позиции монет пронумерованы слева направо, начиная с единицы. Переворачиваются две монеты: в некоторой позиции x с лицевой стороны на оборотную, и в некоторой позиции y = x − z, где z ∈ S , если только не будет x − z = 0 для некоторого z ∈ S — тогда вторая монета не переворачивается. Например, если S = {1, 2, 3}, переворачиваются монеты: одна Λ→О в позиции x и вторая в позиции x − 1, x − 2 или x − 3, кроме случая x  3, когда вторая монета может не переворачиваться. Если монета Λ — одна и находится в позиции x, значение Шпрага–Гранди легко вычисляется: x 1 2 3 4 5 6 7 8 9 10 11 12 . . . g(x) 1 2 3 0 1 2 3 0 1 2 3 0 . . . Ряд с несколькими монетами Λ соответствует нескольким кучам. Существует другой способ описания игр вычитания как игр переворачивания монет. Потребуем, чтобы всегда переворачивались ровно две монеты, расстояние между монетами равно некоторому z ∈ S , и правая монета переворачивается Λ→О. Тогда удобно начать нумерацию монет с 0. Монета Λ в 0-й позиции представляет здесь уже терминальную позицию. Пример 3. Игра Близнецы (Twins). Только что описанный метод, будучи применен к Опрокидыванию, приводит к эквивалентной игре Близнецы, которая также эквивалентна игре ним. Переворачиваются ровно две монеты, правая Λ→О. Если начать нумерацию монет с 0, функцией Шпрага–Гранди будет g(x) = x, как для нима. Пример 4. Игра Линейка (Ruler). Разрешается перевернуть любое число монет, но все они должны стоять рядом, причем правую Λ→О. Нумеруем монеты с единицы, тогда функция Шпрага–Гранди будет вычисляться по формуле g(x) = mex {0, g(x − 1), g(x − 1) ⊕ g(x − 2), . . . , g(x − 1) ⊕ g(x − 2) ⊕ . . . ⊕ g(1)} . Заполним табличку: x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . g(x) 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 . . . т.е. значение g(x) равно наибольшей степени двойки, которая делит x. Название «линейка» происходит от того, что значения функции g(x) напоминают метки на линейке.
Стр.101
Часть II. Пристрастные игры § 8. Введение в пристрастные игры Красно–синий Хакенбуш — Игра Прыгающие лыжники — Числа — Игра Жабы-и-лягушки — Задачи В пристрастных играх (partizan games) у игроков в каждой позиции имеются разные наборы возможных ходов и, тем самым, их множества опций различны. Поэтому имеет смысл в более существенном различении игроков, чем в беспристрастных играх, где мы им давали безликие имена — «первый игрок» и «второй игрок». Речь шла только о том, кто ходит первым в исходной позиции игры, а кто — вторым. Теперь же игроков надо различать безотносительно к очередности хода в игре. Дадим игрокам собственные имена, следуя Дж.Конвею [2]: одного назовем Левым, другого — Правым. Все остальные постулаты комбинаторных игр остаются для пристрастных игр в силе: играют два игрока, их ходы чередуются, оба игрока имеют полную информацию об игре, игра заканчивается за конечное число ходов, ничьей в игре быть не может, игрок, у которого нет ходов, считается проигравшим (нормальное правило игры). 1. Красно–синий Хакенбуш. Игра «Красно–синий Хакенбуш» придумана Дж.Конвеем в целях иллюстрации теории пристрастных игр. Это — то же подрезание кустов, что и «зеленый Хакенбуш» (§ 6, п. 3), но каждый игрок имеет право подрезать ветви определенного цвета: Левый — синего, Правый — красного. На рисунке Хакенбуша подрезанная ветвь удаляется (стирается), а вместе с ней удаляются и все те части рисунка, которые стали не связанными с землей (рис. 1; синии линии толще). Рис. 1: Красно–синий Хакенбуш 115
Стр.115
116 § 8. Введение в пристрастные игры Что существенно нового появляется в игре по сравнению с нейтральным вариантом1? В игре, изображенной на рис. 2,а цвета ветвей не перемешиваются (в отличие от рис. 1); поэтому оптимальными ходами игроков будут подрезание ветвей, наиа б в Рис. 2: Игры с очевидными результатами: а — = +2, б — = −1, в — = 0 более далеких от земли. И Левому, и Правому бессмысленно подрезать в первую очередь нижние ветви — кто так сделает, немедленно проиграет. Каждый игрок стремится сделать как можно больше ходов, так что выигрывает тот, у кого запас ходов больше. Фигура с синими ветвями имеет на 2 ветви больше, поэтому выигрывает Левый — независимо от того, кто ходит первым. По окончании игры у него останется еще 2 дополнительных хода. Аналогично на рис. 2,б у Правого после окончания игры останется 1 ход. Несмотря на то, что здесь фигура с ветвями разных цветов уже не разбивается на отдельные монохромные компоненты, игроки могут придерживаться своей прежней стратегии сделать как можно больше ходов. Если Правый сразу подрежет правую нижнюю красную ветвь, Левый за два хода ликвидирует правую красную часть рисунка и выиграет, а ведь у Правого при разумной игре было бы благодаря этой части 6 ходов! Теперь посмотрим на рис. 2,в. Здесь две симметричных (или, лучше сказать, антисимметричных) компоненты, и второй игрок (т.е. тот, кто ходит в данной игре не первым) имеет уже известную нам по беспристрастным играм стратегию копирования: он повторяет то, что делает первый игрок, на следующем ходе — но на другой компоненте и с ветвью другого цвета. Раз второй игрок всегда имеет возможность ходить, он выигрывает. Если начинает Левый, то выигрывает Правый, и наоборот — если начинает Правый, то выигрывает Левый. Считая по привычке количество ходов, найдем, что их число у Левого и Правого одинаково; если бы мы нумеровали ходы так, как, например, принято в шахматах или шашках: 1. первый ход Левого первый ход Правого 2. второй ход Левого второй ход Правого 3. . . . . . . 1 Мы по-прежнему молчаливо предполагаем, что каждый игрок стремится выиграть, т.е. не проиграть, и делает для этого все, исключительно все; в частности, ходы игроков оптимальны с точки зрения достижения данных целей.
Стр.116
§ 9. Результативные классы игр Формальное определение игры — Классы результативности — Сложение и сравнение игр — Упрощение игр — Задачи 1. Формальное определение игры. Для пристрастных игр следует различать опции Левого и опции Правого, поэтому для задания игры требуется два множества. Всякая игра содержит некоторое число позиций, каждая из которых будет полностью определена, если мы зададим все возможные ходы в данной позиции: и Левого, и Правого. Так что каждая позиция описывается упорядоченной парой множеств — левых опций и правых опций. Игру мы отождествляем с ее начальной позицией, и, таким образом, приходим к рекурсивному определению. Определение 1. Пусть L и R — множества игр. Тогда упорядоченная пара G = (L,R) также является игрой. Элементы множеств L и R называются соответственно левыми и правыми опциями игры G. Позициями G называются сама G и позиции всех опций G. Рекурсивное определение не говорит нам, что такое игра, но предоставляет удобное аксиоматическое описание игры. Примем в качестве аксиомы следующее предложение. Условие завершаемости. Не существует бесконечной последовательности игр Gi = (Li,Ri), где Gi+1 ∈ Li ∪ Ri, i ∈ . Игра G = (L,R) разыгрывается следующим образом. Предположим, что первый ход делает Левый. Тогда он выбирает произвольно элемент GL ∈ L — это означает ход в опцию GL. Затем Правый выбирает правую опцию позиции GL, упорядоченной пары множеств опций. Пусть L = {GL1 G = (L,R) = {GL1 делая ответный ход, и т.д. Условие завершаемости гарантирует, что игра не будет продолжаться бесконечно, а рано или поздно закончится — выигрышем одного из игроков (или, лучше сказать, проигрышем одного из игроков из-за того, что множество его опций окажется пустым). Обозначения, которые мы уже использовали, несколько отличаются от записи ,GL2 два множеств игр. Считая их соответственно множествами левых и правых опций, по определению мы должны записать , . . .} и R = {GR1 ,GL2, . . .}, {GR1,GR2, . . .} . Вместо этой записи по традиции используют более наглядную: G = {GL1 ,GL2 , . . . | GR1 ,GR2 , . . .}. Можно сказать, что игра представляет собой множество с двумя различными типами элементов. Элементы одного типа (левые опции) записываем слева от вертикальной черты, элементы другого типа (правые опции) записываем справа. Прежде чем «создавать» игры, мы должны с чего-то начать. Но вначале ничего нет, кроме пустого множества. Так что простейшая игра — это нулевая 128 ,GR2 , . . .} —
Стр.128
1. Формальное определение игры 1 = {0 | } = {{ | } | } (один ход у Левого); −1 = { | 0} = { | { | }} (один ход у Правого); 129 игра 0 = { | }; в этой игре ни у одного игрока нет ходов. Теперь уже есть непустое множество игр, и мы может построить следующие простейшие игры: ∗ = {0 | 0} = {{ | } | { | }} (один ход у каждого игрока). Итак, четыре простейшие игры таковы: 0 = { | } также рис. 1, изображающий деревья игр), 2 = {1 | } = {{{ | } | } | }, 1 = {0 | } − 1 = { | 0} ∗ = {0 | 0}. Дальнейшее конструирование игр не представляет трудностей. Например (см. 1/2 = {0 | 1} = {{ | } | {{ | } | }}, −3/4 = {−1 | −1/2} = {{ | 0} | {−1 | 0}} = {{ | 0} | {−1 | 0}}. Добавим еще две новые игры ↑= {0 | ∗} = {0 | {0 | 0}} и ↓= {∗ | 0} = {{0 | 0} | 0}. 0 0 0 1 2 а 1 2/ б 1 - 3 4/ в Рис. 1: Деревья игр: а — 2, б — 1/2, в — (-3/4), г — ↑ Пример 1. Красно–сине–зеленый Хакенбуш (RGB-Хакенбуш). В этой разновидности игры Хакенбуш к красным и синим ветвям добавлены зеленые; их подрезка разрешена обоим игрокам. На рис. 2 изображена некоторая позиция (а), 0 -1 -1 2/  г 0 -1 0 0 * 0 0 а б Рис. 2: Красно–сине–зеленый Хакенбуш ее левые опции (б) и правые опции (в). (Синии линии толще; зеленые — самые в
Стр.129
§ 10. Примеры анализа игр Ряд модификаций игры — T&F (Toads-and-Frogs с 4 фигурами) — Игра кол — Игра снорт — Игра кросскрем — Свитч-игры — Ультрамалые игры — Красно-синий Хакенбуш — x + n · ↑ +∗ — Игра доджем — Задачи 1. Ряд модификаций игры. Рассмотрим ряд модификаций игры, которые могут изменить ее значение, но вполне предсказуемым образом. Теорема 1. Значение G не изменится или возрастет, если 1) увеличить любую опцию GL или GR; 2) удалить любую опцию GR или добавить новую опцию GL; 3) заменить GR на KR, для произвольной игры K  G. Доказательство. Пусть H — игра, полученная с помощью таких модификаций из игры G. Тогда, как легко проверить, в игре H−G у Правого нет хорошего первого хода, что равносильно H  G.  Все эти модификации изменяют игру в пользу Левого, так как дают ему новые ходы или запрещают некоторые ходы Правому. Пример 1. Пример стратегического анализа. Докажем замечательное равенство ↑ + ↑= {0 |↑}+ ∗, или, что то же самое, ↑ + ↑ +∗ = {0 |↑}, используя стратегический анализ дерева игры. Рассмотрим игру ↑ + ↑ − ∗ −{0 |↑} =↑ + ↑ + ∗ +{↓| 0} (рис. 1, или рис. 2, где буквами a–t помечены все позиции игры), и докажем ее равенство нулю. 0 0 0 0 0 0 * 0 0 * Рис. 1: Игра ↑ + ↑ + ∗ +{↓| 0} c → i приходим к позиции ↑ + ↑> 0; так что c → j и d → l — плохие ходы для Правого. После a → e, b → h получаем позицию ∗ + ∗ + d = d, в которой Левый проигрывает после d → k, k → r. Наконец, после c → i, a → f получаем позицию Остается рассмотреть ходы Правого c→ j, d →l и Левого a→e, c→i. После c → j, d → k приходим к позиции ↑ + ↑ + ↓=↑> 0, а после d → l, После ходов a → f и d → k приходим к нулевой позиции ∗+ ↑ + ∗ + ↓. 0 * { | 0 } 0 0 0 ∗+ ↑ +d ( f + b + d), в которой у Левого нет хороших ходов ( f →m, b→h; b→g, f →n; d →k, f →n). Пример 2. Упрощение игры (приведение к канонической форме). Рассмотрим игру {↑|↑}. Имеем {↑|↑}  {0 |↑}, в соответствии с теоремой 1, так как ↑ 0. 142
Стр.142
2. T&F s m e a n f g b o h c p i j q k d Рис. 2: Игра ↑ + ↑ + ∗ +{↓| 0} с помеченными вершинами ∗ =↑R. Поэтому ↑, как левая опция, реверсивна, и, следовательно, может быть заменена на ∗L = 0. Таким образом, {↑|↑} = {0 |↑}. Здесь левая опция 0 не является реверсивной, поскольку у 0 нет опций; а, так как {0 |↑} положительна (Левый выигрывает независимо от очереди хода), ↑ не является реверсивной, как правая опция. Поэтому {↑|↑} = {0 |↑} приведено к канонической форме. Согласно предыдущему примеру, {0 |↑} =↑ + ↑ +∗, что, очевидно, больше, чем 2. T&F. Рассмотрим версию игры Toads-and-Frogs (п. 4 § 8) с 4 фигурами, находящимися в позиции T T F F Анализ приводит к следующей таблице: -ЧЧЧЧ Ч-ЧЧЧ 1 TTFF a — 0 TFTF b (—|d3) 0 TFFT c FFTT f 2 (a1|b4) ↑ (b1|b3) ∗ FTTF d (—|d2) −1 — 0 FTFT e (—|e2) −1 (—|f4) 0 ЧЧ-ЧЧ ЧЧЧ-Ч ЧЧЧЧ- 3 4 (a2|a4) ∗ (d1|c5) 0 2 (—|f3) −1 — 0 (e1|c4) −1 (d2|e5) 1 5 (b2|a5) ↓ — 0 (b3|b5) ∗ (c3|—) 0 2 — 0 (c4|—) 1 (f2|—) 0 (e4|—) 1 (f3|—) 1 В клетках таблицы даются ссылки на левые и правые опции, разделенные |, причем запись, скажем, (d1|c5) 0 в клетке b3 означает, что позиция TFOTF имеет левую опцию OFTTF и правую опцию TFFTO, поэтому ее значение {−1 | 1} = 0. Прочерк (—) означает отсутствие опций. Пустая клетка соответствует позициям, в которые из начальной позиции невозможно прийти. Начальная позиция имеет значение TTOFF = {TOTFF | TTFOF} = {↑|↓}. Покажем, что игра G = {↑|↓} имеет каноническую форму ∗. Для этого построим дерево позиций игры G−∗ (= G+∗), учитывая, что ↑= {0 | ∗}, ↓= {∗ | 0}, и проведем стратегический анализ (рис. 3). t r l 143
Стр.143
§ 11. Сюрреальные числа Определения и следствия из определений — Умножение и деление чисел — Короткие числа и вещественные числа — Ординальные числа — Сюрреальные числа — День рождения игры — Структура числа (День рождения числа) — Сюрреальные числа (продолжение) — Функции сюрреальной переменной — Задачи В игре Красно-синий Хакенбуш все позиции сравнимы с нулем и друг с другом — достаточно (в последнем случае) сложить одну данную позицию с отрицанием другой — получается еще одна игра Хакенбуш, относительно которой уже можно выяснить, к какому классу результативности она относится: положительному, отрицательному или нулевому. Возможность первому игроку выигрывать безотносительно к тому, что это за игрок (Левый или Правый), отсутствует в этой игре.1 Подобное поведение игры приводит к тому, что все ее значения представляются числами. Краеугольным камнем понятия числа служит то обстоятельство, что любые два числа сравнимы друг с другом. Согласно теореме 5 §9 всегда имеет место GL  G и G  GR. Если G, GL и GR являются числами, это влечет за собой GL < G < GR. Так что от опций имеет смысл потребовать выполнения неравенства GL < GR, а для сохранения чисел в процессе игры — чтобы опции чисел были числами. рациональные числа (числа вида m/2n 1/2n ≡ {0 | 1/2n−1} и −1/2n ≡ {−1/2n−1 −1 ≡ { | 0}, 2 ≡ {1 | }, −2 ≡ { | 1}, . . .Если построены числа n и −n, то на следующем шаге создаются числа n + 1 ≡ {n | } и −n − 1 ≡ { | −n}. Далее, 1/2 ≡ {0 | 1}, 1/4 ≡ {0 | 1/2}: дроби со знаменателем 2n легко строятся, | 0}. Аналогичным путем получаются диадические , m, n ∈ ): 2m + 1 2n+1 = m 2n  m + 1 2n . В действительности диадические дроби порождают все прочие рациональные числа и все вещественные числа посредством конструкции, называемой сечениями Дедекинда. Если у нас есть две последовательности, сходящиеся к одному и тому же числу и приближающие его снизу и сверху соответственно, то эти последовательности создают число как игру. Например,  i=1 ∞ 22i = 1 1 3, 1 2 −  i=1 ∞ 22i+1 = 1 1 3. 1 Для таких, неопределенных игр, мы вводили в Хакенбуше зеленые ветви. 157 левые и правые опции xL и xR суть числа, удовлетворяющие неравенству xL < xR. С конструкцией простейших чисел мы хорошо знакомы: 0 ≡ { | }, 1 ≡ {0 | }, 1. Определения и следствия из определений. Определение 1. Игра x = {xL, . . . | xR, . . .} называется числом, если все ее
Стр.157
158 Таким образом, 1 3 = 1 4, 1 4 + 1 16, 1 4 + 1 16 + 1 64, . . .  1 2, 1 2 − 1 8, 1 2 − 1 8 − 32, . . . 1  . Так же может быть построено «бесконечное» число ω ≡ {0, 1, 2, . . . | }. Однако не все игры являются числами. Мы уже рассматривали раньше нимберы ∗n, которые не являются числами. В нашей конструкции нимберы строятся так: {0 | 0} обозначается ∗ (звездочка), {0, ∗ | 0, ∗} обозначается ∗2, {0, ∗, ∗2, . . . , ∗(n− 1) | 0, ∗, ∗2, . . . , ∗(n − 1)} обозначается ∗n. Теорема 1. Для любого числа x = {xL, . . . | xR, . . .} справедливо неравенство xL < x < xR. неравенство x < xR.  Теорема 2. Если x и y — числа, то x+y и −x — тоже числа. Следовательно, то существовала бы опция (xL − x)L  0. Однако, это невозможно, что показывает следующее рассуждение. Левые опции xL−x имеют вид xL−xR или xLL−x. Имеем xL − xR < 0, так как x — число; xLL − x = (xLL − xL) + (xL − x)  0, так как xLL < xL по предположению индукции, а xL − x  0. Итак, должно выполняться xL − x < 0, т.е. xL < x. Аналогично доказывается числа (классы эквивалентных чисел) образуют абелеву подгруппу группы игр. Доказательство. Имеем x + y = {xL + y, x + yL, . . . | xR + y, x + yR, . . .}. Все опции Далее, так как −x = {−xR, . . . | −xL, . . .}, то (−x)L = −xR < −xL = (−x)R.  Пример 1. (−1) + (−1) = −2; действительно, −1 = { | 0}, { | 0} + { | 0} = { | 0 + (−1), (−1) + 0} = { | −1} = −2; 1/2 + 1/2 = 1; действительно, 1/2 = {0 | 1}, {0 | 1} + {0 | 1} = {0 + 1/2, 1/2 + 0 | 1 + 1/2, 1/2 + 1} = {1/2 | 11/2} = 1 (по теореме упрощения; нужно еще доказать равенство 1 + 1/2 = 11/2 — но оно доказывается проще). Теорема 3. Множество чисел линейно упорядочено: для любых двух чисел x и y справедливо в точности одно из трех соотношений x < y, x > y или x = y. Доказательство. Ни одно число не является неопределенным. Действительно, из z  0 вытекало бы существование опций zL  z  zR, что противоречит определению числа. Невозможность x  y для чисел следует из невозможности x − y  0.  2. Умножение и деление чисел. Чтобы наделить группу чисел структурой поля, необходимо ввести умножение и деление. Принцип, по которому определяется умножение, аналогичен используемому для беспристрастных игр. Чтобы умножение чисел было согласовано с отношением порядка, учитывая неравенства xL < x < xR, yL < y < yR, следует потребовать (x − xL)(y − yL) > 0, (xR − x)(yR − y) > 0, (x − xL)(yR − y) > 0, (xR − x)(y − yL) > 0, Доказательство. По теореме 5 §9 xL  x, т.е. xL−x  0. Если бы было xL−x  0, § 11. Сюрреальные числа x + y, очевидно, суть числа по предположению индукции. Согласно теореме 7 §9 xL + y < xR + y и x + yL < x + yR. Кроме того, xL + y < x + y < x + yR и аналогично x + yL < x + y < xR + y.
Стр.158
§ 12. Между играми и числами Критерий: когда игра является числом — Правила: как играть с числами — Левые и правые значения — Позиции остановки — Короткие игры и числа — Теорема о среднем значении — Инфинитезимальные, малые и абсолютно малые игры — Задачи 1. Критерий: когда игра является числом. Числа — это самые простые игры. Поскольку они линейно упорядочены, мы точно знаем, что случится (т.е. кто выиграет), если мы сложим несколько таких игр. Значительно сложнее иметь дело с общими играми. Чтобы сделать первый шаг по направлению к исследованию таких игр, надо научиться сравнивать игры и числа. Прежде всего нас интересует вопрос о том, когда игра является числом. Сначала установим критерий равенства двух игр, который, если заменить одну из игр числом, приведет нас к решению поставленного выше вопроса. Теорема 1. (Теорема упрощения). Пусть G и H — игры; и пусть выполнены условия: (1) ∀GL : GL  H и ∀GR : H GR; (2) ∀HL∃GL : HL  GL и ∀HR∃GR : HR  GR. Тогда G = H. Доказательство. Согласно (1), все GL суть левые подарки, а все GR — правые подарки для H. Поэтому H = {GL,HL | GR,HR}. Но теперь, согласно (2), опции H можно исключить как доминируемые, что в результате приводит к H = {GL | GR} = G.  Теорема 2. Пусть G — игра, а x — число, такое, что (1) ∀GL : GL  x и ∀GR : x GR. Тогда G равно некоторому числу, являющемуся позицией x. Если ни одна опция x не удовлетворяет условию (1), будучи подставлена вместо x, то G = x. Доказательство. Последнее утверждение является непосредственным следствием теоремы 1: считаем H числом и тогда условие (2) в точности означает, что ни одна опция H не удовлетворяет условию (1). Если же существует опция x числа x такая, что GL  x  GR, то заменим x на x и используем индукцию.  Если G — число, то эта теорема утверждает, что G(= x) равно наипростейшему числу среди подходящих (между GL и GR). Понятие более простой игры определено в терминах дней рождения: чем раньше игра создана (т.е. чем меньше ее день рождения b(G)), тем она проще. Теорема 3. Игра G, не имеющая правых (или левых) опций, является числом. Доказательство. Пусть G не имеет правых опций. Тогда GL  b(GL) < b(G), и, в силу предыдущей теоремы, G — число, которое является позицией числа b(G). (Так что G является даже ординальным числом.) Если G не имеет левых опций, следует рассмотреть −G.  175
Стр.175
176 § 12. Между играми и числами зательно является числом. Например, G = {0 |↑} — положительная игра, меньшая всех положительных чисел, и при этом 0 <↑. 2. Правила: как играть с числами. Совершенно очевидно, как играть в число: следует выбирать наибольшую (для Левого; наименьшую — для Правого) возможную опцию. Ходить в число всегда невыгодно, так как такой ход ведет в позицию худшую, чем была. В любом случае, знак числа дает возможность определить, кто выиграет, и чтобы достичь выигрыша, нужно лишь выбирать опции правильного знака. Так что игра в число не представляет интереса: результат предопределен. Менее тривиальный вопрос: как правильно играть в игру G + x, где x — число, а G — не число? Теорема 4. (Теорема избегания чисел). Если G — игра, не равная числу, Тогда либо ∃GL  x, либо ∃xR  G. В первом случае мы пришли к желаемому заключению; в последнем же случае предположим, что ∀GL : x  GL. Тогда, так как по условию G не равно числу, из теоремы 2 вытекает, что ∃GR : x  GR. В результате имеем G  xR > x  GR, что противоречит известному факту GGR.  словами, если существует выигрывающий ход в сумме G + x, то существует уже выигрывающий ход в компоненте G. Принцип избегания чисел. Наилучшим ходом в игре не может быть ход в Применим теорему к G и −x: G+x0⇔GL+x  0 для некоторого GL. Иными число, за исключением случая, когда других возможностей нет. Это не означает, однако, что другие опции G + xL избыточны (т.е. доминируемые или реверсивные). Так будет лишь в случае, когда G — короткая игра. 3. Левые и правые значения. Теорема 5. (принцип Архимеда). Какова бы ни была короткая игра G, найдется такое целое число n, что −n < G < n. Для произвольной игры G найдется такое ординальное число α, что −α < G < α. Доказательство. Для короткой игры G возьмем в качестве n число, большее общего числа позиций в G, и рассмотрим G + n. Левый выигрывает, просто уменьшая n на 1 каждым своим ходом, ожидая, когда Правый исчерпает свои ходы в G. Таким образом, G + n > 0, и G > −n; аналогично доказывается G < n. В случае произвольной игры проводим доказательство по индукции, в качестве α принимая наименьший ординал, б´ ольший, чем все GL,GR.  Исследуя игру, хотелось бы знать числа x, для которых x  G, и числа y, для которых y  G. Руководствуясь этими двумя условиями, определим два дедекиндова сечения в классе всех чисел. Положим L(G) = {x : x G | x : x  G}, R(G) = {y : y  G | y : y G}. В частности, для числа z L(z) = {x : x < z | x : x  z}, R(z) = {y : y  z | y : y > z}. а x — число, то x G ⇔∃GL : x  GL. Доказательство. Импликация ⇐ очевидна. Теперь предположим, что xG. Заметим, что игра, для которой выполнено условие ∀GL, GR : GL < GR, не обя
Стр.176
§ 13. Теория температуры Некоторые обозначения и примеры — Охлаждение — Среднее значение и температура — Термограф — Левая и правая температура — Свитч-игры и их суммы — Игры с 3 и 4 стоп-позициями — Расширенный термограф — Разогрев — Задачи 1. Некоторые обозначения и примеры. Введем несколько сокращенных обозначений. Будем опускать фигурные скобки вокруг игр, если это возможно, — например A, B | C вместо {A, B | C}. Чтобы различать игры {{A | B} | C} и {A | {B | C}}, введем символ  как более «сильный» разделитель, чем |; так что эти игры станут A | B  C и A  B | C соответственно, игра {{A | B} | {C | D}} станет A | B  C | D. Игру с симметричными опциями для Левого и Правого {A, B,C, . . . −A,−B,−C, . . .} будем записывать ±(A, B,C, . . .); в частности, ±G будет обозначать {G | −G}. В настоящем параграфе будем рассматривать только короткие игры; такие игры содержат конечное число стоп-позиций. Напомним, что одна из стоппозиций является левым значением L0(G), а еще одна — правым значением R0(G) игры G. Левое и правое значения представляют собой минимаксные значения игры при чередовании ходов игроков, если первым ходит соответственно Левый или Правый. Интервал неопределенности игры, т.е. интервал I(G) между левым и правым значениями содержит все возможные результаты игры (при условии, что игроки играют правильно). Конец интервала неопределенности исключен из интервала, если в соответствующей ему стоп-позиции очередь хода принадлежит тому же игроку, который делал первый ход (т.е. оба игрока сделали одинаковое количество ходов), и включен в интервал, если первый игрок сделал на один ход больше. Пример 1. Для игры G = 3 | 2  0,±1 левое и правое значения суть L0(G) = 2, R0(G) = 0; однако для сечений имеют место равенства: L(G) = L(2), R(G) = L(0), так как, когда начинает Левый, игра приходит к стоп-позиции 2 с ходом Левого, а когда начинает Правый — к стоп-позиции 0 тоже с ходом Левого. Поэтому интервал неопределенности I(G) = [0, 2). В общем случае, если L0(G) = a, R0(G) = b, то I(G) = (b, a) при L(G) = L(a), R(G) = R(b); I(G) = [b, a) при L(G) = L(a), R(G) = L(b); I(G) = (b, a] при L(G) = R(a), R(G) = R(b); I(G) = [b, a] при L(G) = R(a), R(G) = L(b). Чем шире интервал неопределенности, тем больше неопределенность в игре, тем более значительный стимул имеет каждый игрок для того, чтобы делать ход первым, тем более накалена игра. Можно вообразить, что в процессе игры чаша весов колеблется между правым и левым значениями, имея некоторое среднее значение m(G). Напомним, что среднее значение представляет собой то значение, которое игра будет иметь в среднем, когда разыгрывается много копий данной игры. Это вовсе не обязательно середина интервала неопределенности. 183 |
Стр.183
184 § 13. Теория температуры хотя I(H) = (−1, 1). Определение 1. Будем говорить, что игра G инфинитезимально близка к числу x, если левое и правое значения G равны x. В этом случае интервал неопределенности состоит из одного числа или пуст. Пример 3. Для ∗ = 0 | 0, L(∗) = R(0), R(∗) = L(0), интервал неопределенности I(∗) = [0]; для ↑= 0  0 | 0, L(↑) = R(↑) = R(0), I(↑) пуст; для ↓= 0 | 0  0, L(↓) = R(↓) = L(0), I(↓) = ∅. 2. Охлаждение. Мы хотим уменьшить неопределенность, чтобы определить среднее значение игры; поэтому найдем способ охладить игру, чтобы погасить колебания, и при достаточно долгом охлаждении совсем прекратить колебания, заморозив игру в точке m(G). Игра накаляется, когда позиция такова, что каждый игрок может получить значительный выигрыш, делая подходящий ход. Например, игра {1000 | −1000} очень горячая, так как в ней, несмотря на нулевое среднее значение, игрок, делающий первый ход, получает выигрыш 1000. Чтобы охладить игру, будем снижать ее накал (напряженность), облагая ходы налогом: заставим каждого игрока платить t за каждый свой ход, пока значение не станет числом. Левый, желая, чтобы значение игры было как можно б´ ольшим, станет меньше беспокоиться о ходе, если значения опций станут меньшими; поэтому вычтем положительное число t из всех опций Левого. Правый желает, чтобы игра имела как можно меньшее значение, поэтому мы прибавим положительное число t ко всем его опциям. Если налог, которым облагаются ходы, будет достаточно большим, и охлажденная игра будет инфинитезимально близка к числу, то ни один игрок не будет иметь стимула делать ход, так что от дальнейших налогов игроков следует освободить. Определение 2. Пусть G — короткая игра, t — вещественное число  0. Игра G, охлажденная на t, определяется формулой Gt =  {GL где Gt x, если t > t, t − t | GR инфинитезимально близка к числу x. Первая строка определения будет в силе до тех пор, пока эта формула не определяет число (что будет иметь место для всех достаточно больших t). Для наименьших значений t, при которых последнее имеет место, число является константой x. Заметим, что данное определение содержит в себе утверждение (которое будет доказано в следующем п.). Это утверждение не верно для общего класса игр, поэтому мы ограничиваемся короткими играми. t + t}, если t  t, 1 | −2 = 1, поэтому m(G) = 1/2. Однако, для игры H = 2 | 1  −1∗ имеет место 4H = 1, поэтому m(H) = 1/4, Пример 2. Для игры G = 2 | −1 имеем 2G = G +G = 2 +G | −1 +G = 4 | 1 
Стр.184