Позиционные игры

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

Пример 7. Игра «ним». В этой игре на стол между двумя игроками выкладывается неко-торое количество фишек. При каждом ходе игрок должен разделить одну из имеющихся групп фишек на два непустых подмножества разных размеров. Например, 6 фишек можно разделить на группы 5 и 1 или 4 и 2, но не 3 и 3. В начале игры все фишки образуют одну группу. После 1-го деления появится две группы, после 2-го деления – 3 группы, и т.д. Игрок, который не смо-жет больше сделать ход, проигрывает. На рис.7 показан граф игры «ним»для 7 фишек. Каждая вершина этого графа соответствует одному из возможных разбиений 7 фишек на группы. Их можно назвать позициями в игре. Позиция á5-1-1ñ означает, что имеется три группы: в 1-ой группе – 5 фишек, а в двух других – по 1-ой фишке. Дуги соответствуют возможным ходам иг-рока в данной позиции. В позиции á5-1-1ñ есть две возможности: разделить группу из 5 фишек на группы из 3-ёх и 2-ух фишек или на группы из 4-ёх и 1-ой фишки. Это значит, что из пози-ции á5-1-1ñ можно перейти в позиции á3-2-1-1ñ и á4-1-1-1ñ. Позиции á2-2-2-1ñ, á2-2-1-1-1ñ и á2-1-1-1-1-1ñ называются финальными, поскольку из них никуда нельзя перейти. Позиция á7ñ назы-вается начальной.

Рис.7. Граф игры «ним»для 7 фишек ■

Пример 8. Игра«Две кучки». Имеется две кучки, в каждой из которых имеется 4 фишки. Игрок может сделать один из следующих трёх ходов:

1. Забрать одну фишку из 1-ой кучки.

2. Забрать одну фишку из 2-ой кучки.

3. Забрать по одной фишке из обеих кучек.

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

Рассматриваемую игру можно представить графом, показанным на рис.8. Как и в преды-дущем примере, вершины соответствуют всем возможным позициям в игре, а дуги – ходам, т.е. переходам между позициями. Пара чисел в скобках у вершины указывает на число предметов в 1-й и 2-й кучке в соответствующей позиции. Игра начинается в вершине (4,4) и заканчивается в вершине (0,0). Из каждой вершины есть три перехода – налево (взят предмет из 1-й кучки), вниз (взят предмет из 2-й кучки) и по диагонали (взяты по одному предмету из обеих кучек).

Рис.8. Граф игры «две кучки» ■

Дадим теперь достаточно общее описание игр рассматриваемого типа. Имеется ациклич-ный (т.е. не содержащий циклов) граф. Одна вершина объявляется начальной. Одна (отличная от начальной) вершина объявляется финальной. Предполагается, что финальная вершина явля-ется единственной вершиной в графе, из которой не выходит ни одной дуги. Игра состоит в том, что игроки по очереди переходят из вершины в вершину по дугам графа, причём 1-ая вер-шина обязательно должна быть начальной. При указанном предположении через конечное чис-ло ходов один из игроков обязательно попадает в финальную вершину, на чём игра и заканчи-вается. Игрок, попавший в финальную вершину, считается победителем. Обычно (см. примеры 7 и 8) вершины графа интерпретируются как позиции в игре, что и позволило дать таким играм естественное название «позиционные».

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

1. Имеется несколько финальных вершин. Добавим к графу одну вершину z и проведём дуги из каждой финальной вершины в вершину z. Вершина z будет единственной финальной вершиной в новом графе. Если в исходной игре попадание в любую финальную вершину было проигрышем, то в новой игре попадание в новую единственную финальную вершину стало вы-игрышем. Наоборот, если в исходной игре попадание в любую финальную вершину было выиг-рышем, то в новой игре попадание в новую единственную финальную вершину стало проигры-шем. Понятно, что суть игры совершенно не изменилась, поскольку в новую вершину попадает всегда не тот игрок, который попал в любую из исходных финальных вершин, а как раз другой. Таким образом, всегда можно рассматривать эквивалентную игру с одним финальным состоя-нием.

2. Игрок, попавший в единственную финальную вершину, считается проигравшим. В этом случае также добавляется одна новая финальная вершина z, в которую ведёт одна дуга из старой финальной вершины. Очевидно, что игрок, не попавший в старую финальную верши-ну, попадает в новую финальную вершину, т.е. является победителем в новой игре. Поэтому проигравшим в новой игре игроком является тот же игрок, который был проигравшим и в ста-рой игре, т.е. новая и старая игра эквивалентны.

Таким образом, мы приходим к описанной выше модели позиционной игры, победитель которой – это игрок, попавший в единственную финальную вершину.

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

Дата добавления: 2015-10-16