Игры и выигрышные стратегии



Содержание


Определение игры

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

Определимся сразу, что мы будем рассматривать не все игры, а только их определенный класс. Нас будут интересовать игры с противоречивыми интересами сторон (антагонистические игры) и полной информацией об игре, и в первую очередь такая разновидность подобных игр, как игра двух лиц с нулевой суммой.

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

В рассматриваемых нами играх участвуют два игрока, которые ходят по очереди, причем оба они обладают полной информацией о текущей игровой ситуации (это определение исключает большинство карточных игр) и о возможных ходах очередного игрока. Игра считается оконченной, если достигнута позиция, являющаяся согласно правилам игры “терминальной” (конечной, заключительной), например, матовая позиция в шахматах. Правилами игры также устанавливается, каков исход игры в этой терминальной позиции.

Чтобы задать конечную игру с полной информацией 4, нужно:

· указать конечное множество, элементы которого называются позициями игры;

· указать начальную позицию игры;

· указать множество заключительных позиций и задать результат игры в каждой из них;

· для каждой из остальных позиций указать возможные ходы, т.е. позиции, которые могут случиться после хода первого или второго игрока соответственно (в некоторых играх возможные ходы не зависят от того, какой именно игрок ходит).

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

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

Примерами рассматриваемых нами игр являются большинство настольных игр: шахматы, шашки, го, крестики-нолики, реверси и многие другие. В математике большое распространение получили игры с камнями, в которых в распоряжении двух игроков имеются несколько кучек камней (одна или более). Игроки ходят по очереди. Также определено, сколько камней и из какого количества кучек может взять игрок за один ход. Если за один ход можно взять любое ненулевое число камней, но только из одной из кучек, то такая игра называется ним. Позициями в таких играх являются различные состояния кучек, которые можно получить из начального состояния (очевидно, что в каждой из кучек может оказаться не больше камней, чем было изначально). Пусть у нас было n кучек по k камней в каждой. Тогда общее число позиций равно (k + 1)n. Здесь учитывается, что в каждой из кучек в процессе игры камней может и не остаться. Поэтому в первой кучке может находиться от 0 до k камней, для каждого состояния первой кучки во второй также может находиться от 0 до k камней и т.д. Часть позиций, возможно, неотличимы друг от друга с точки зрения игры. Заключительной является единственная позиция, в которой ни в одной из кучек камней не осталось. Обычно по правилам она считается проигрышной (тот, кто не может сделать очередной ход, проигрывает), но можно считать ее и выигрышной, тогда такую игру называют “в поддавки”.

Классификация позиций и стратегии игроков

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

Нетерминальная позиция x называется выигрышной для игрока, которому предоставлен ход, если существует хотя бы один ход, переводящий игру в проигрышную позицию. Нетерминальная позиция x называется проигрышной, если все ходы из позиции x ведут в выигрышные позиции.

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

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

Конечную игру с полной информацией можно представить в виде ориентированного графа (см. “Структуры данных”), вершинами которого являются все допустимые позиции игры, а ребра указывают возможные ходы. Данный граф обязательно будет ациклическим (не будет содержать циклов), в противном случае окончание игры не гарантировано. Будем назначать значение для каждой вершины этого графа (выигрышная или проигрышная) по таким правилам:

· значение вершин, соответствующих терминальным позициям, однозначно определено правилами игры;

· все вершины, из которых хотя бы одно ребро графа ведет в вершину, помеченную как проигрышную, помечаем как выигрышные;

· все вершины, из которых все ребра графа ведут в выигрышные позиции, помечаем как проигрышные.

Эти правила применяем в любом порядке, пока это возможно. Утверждается, что рано или поздно всем позициям игры будут присвоены определенные значения. В самом деле, если какая-то вершина графа оказалась непомеченной, то она не может быть заключительной. Более того, какая-то из следующих за ней позиций тоже осталась непомеченной (иначе мы смогли бы пометить и эту), значит, и у нее какая-то из следующих не имеет пометки и т.д.
В результате мы получаем бесконечную партию, которая по условию невозможна.

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

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

Программирование игр

Говоря даже об определенном классе игр, нельзя не упомянуть компьютерные программы, играющие в различные игры из данного класса. Как, например, компьютеры играют (и, как мы знаем, весьма успешно) в шахматы? Ведь полный анализ данной игры пока невозможен. Как и люди, компьютеры просчитывают варианты для текущей позиции — они смотрят, какие возможны ходы, какие ответы возможны на каждый из ходов и т.д. Просмотр приходится на каком-то уровне прерывать и грубо оценивать позицию как выигрышную или проигрышную в зависимости от материального перевеса и расположения фигур. К этому еще добавляется библиотека начал (дебютов), накопленная многовековым опытом шахматистов, а также сведения об окончаниях (эндшпилях), часть из которых, в свою очередь, удалось за последние годы просчитать на компьютере.

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

К счастью, для ряда игр просчитывать большое число позиций для определения результата игры не требуется. В них удается выигрышную стратегию описать с помощью простой функции, аргументом которой является позиция, а значением — выигрышный ход для данной позиции или сообщение о том, что позиция является проигрышной. Рассмотрим пример такой игры 5.

На столе лежат N камней. Играющие по очереди могут взять от одного до четырех камней. Кто не может сделать ход (камней не осталось) — проигрывает. Если N делится на 5 без остатка, то второй игрок может гарантировать себе выигрыш, дополняя ход противника до 5 (если первый взял одну, то второй берет четыре и т.д.). Если N на 5 не делится, то выигрывает первый игрок: он должен сначала взять число камней, равное остатку от деления N на 5, а потом дополнять ход противника до 5. Здесь все позиции с числом камней кратным 5 являются проигрышными, остальные — выигрышными. Программирование выигрышной стратегии для такой игры не составит труда.

Часто в играх используется и так называемая “симметричная стратегия”. Например, двое игроков кладут одинаковые круглые монеты на прямоугольный стол. Монеты могут свешиваться за край, но не должны падать и перекрываться. Кто не может положить монету — проигрывает. В этой игре первый игрок может выиграть, положив первым ходом свою монету в центр стола, а затем повторяя ходы второго игрока симметрично относительно центра. Очевидно, что если второй игрок нашел место для монеты, то есть и пустое симметричное ему место. В этой игре число позиций бесконечно (хотя сама игра конечна), но идея симметрии применяется и в ситуациях с конечным числом позиций.

Методические рекомендации

Тема выигрышные стратегии в играх появилась в профильном уровне стандарта среднего (полного) общего образования по информатике. Изучение темы “Игры и выигрышные стратегии” позволяет показать ученику научный подход к решению ряда бытовых задач, расширяет их кругозор с точки зрения практической применимости знаний математики и алгоритмов. Ранее подобные задачи встречались лишь на олимпиадах по информатике и программированию и опирались на знания, полученные учащимися математических классов в углубленном курсе математики. Начиная с 2005 г. задачи на поиск выигрышной стратегии встречаются и в материалах ЕГЭ по информатике. Приведем пример задачи из демоверсии ЕГЭ 2007 г.

Задача. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет один камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Решение. Выигрывает второй игрок.

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

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

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


4 См. книгу А.Шеня “Игры и стратегии с точки зрения математики”. М.: изд-во МЦНМО, 2007.

5 Игра приведена, в частности, в книге А.Шеня “Игры и стратегии с точки зрения математики”.




Наверх