Задача №26. Построение дерева игры. Поиск выигрышной стратегии

Задача №26. Построение дерева игры. Поиск выигрышной
стратегии
Автор материалов – Герасимов Н.А.
1. Формализация игровой ситуации
2. Определение выигрышной стратегии для игры двух игроков.
3. Определение выигрышной стратегии для произвольной ситуации
4. Вопросы для самопроверки
Литература и источники:
1. Формализация игровой ситуации
Под «игрой» будем понимать многоходовый процесс, в котором участвуют 2 и более
игроков, каждый из которых на каждом шаге игры может сделать выбор (ход),
изменяющий игровую ситуацию. Игроками выбор делается из конечной альтернативы
вариантов действий. Такие игры называют играми «с полной информацией»
Примерами игр «с полной информацией» являются игры «крестики-нолики», шашки,
шахматы и другие. Начинается игра с определенной позиции (или начальной ситуации
S0), которая как правило, создает равные условия для каждого игрока.
Игра развивается по шагам. На каждом шаге игры каждый игрок имеет возможность
выбрать альтернативу из конечного набора действий ( множество альтернатив D={a,b, …}
на каждом шаге игры постоянно).
После сделанных ходов всеми игроками в игре возникает новая ситуация (Si), которая
оценивается игроками. Каждый игрок оценивает свою позицию, относительно цели игры
и принимает решение о качестве ситуации и какое действие выбрать на следующем шаге
игры..
Конечной ситуацией (Sn) в игре является та, в которой один из игроков достигает
конечной цели игры первым.
Последовательность ходов (выборов) игроком, приводящих его из начальной ситуации
(S0) в конечную (Sn) называется – траекторией игрока (или его стратегией).
Очевидно, что у каждого игрока возможны различные варианты стратегий. Одни
стратегии приводят игрока к выигрышу (выигрышная стратегия), другие - нет.
В простых играх, у которых исходная ситуация описывается малым количеством
вариаций, количество игроков невелико (2 или 3 игрока), и количество альтернатив
действий так же невелик - все множество стратегий игроков можно отобразить графом
(обычно графом типа «дерево»).
Пример простой игры можно представить так. Имеется исходная ситуация: ящик, в
котором 2 яблока. Имеются два игрока, которые могут добавить в этот ящик яблоки двумя
способами: способ а) +2 яблока, или способ б) удвоить количество яблок в ящике.
Выигрывает тот, кто первым получит заданное количество яблок в ящике (например 7
яблок).
Граф, отображающий возможные варианты количества яблок в корзине на каждом шаге
игры показан ниже.
Рис.1. Вариант графа, отражающий все ситуации в простой игре двух игроков
Анализ графа. Из графа на Рис.1. видно, что какое бы действие не принял первый игрок
(+2 или х2), второй игрок всегда может закончить игру на 2-м шаге. В этом случае можно
говорить, что второй игрок имеет очевидную выигрышную стратегию.
Но если 2-й игрок упустит такую возможность, то игра закончится на 3-м шаге победой 1-
го игрока.
Таким образом, стратегия на графе отображается последовательностью дуг графа
(маршрутом на графе), которая приводит игрока из начальной ситуации в конечную.
Если у игрока имеется четкая стратегия, которая однозначно приводит его из некоторой
позиции (Si) в к выигрышу, то говорят, что игрок «имеет выигрышную позицию» в
позиции (Si).
2. Определение выигрышной стратегии для игры двух игроков.
Существует класс простых игр, в которых выигрышную позицию имеет игрок, который
начинает игру первый. И если он выберет правильное решение на первом ходу, то он
может получить гарантированный выигрыш не зависимо от выборов других игроков.
Проигрышная позиция – это такая позиция, при которой игрок, делающий первый ход,
проигрывает независимо от выбора очередного хода.
Для определения наличия выигрышной позиции у первого игрока необходимо
проанализировать все множество стратегий и выбрать те, которые гарантирую выигрыш.
Рассмотрим варианты задач, в которых имеется выигрышная стратегия для первого игрока
Пример 1.
Описание игры. Перед игроками стоят две емкости, в которых лежат камни. В первой
емкости находятся 3 камня, а во второй 6 . У каждого игрока неограниченно много камней.
Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-
то емкости, или добавляет 2 камня в какую-то емкость. Выигрывает игрок, после хода
которого общее число камней в двухемкостях становится не менее 24 камней.
Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или
игрок, делающий второй ход? Докажите, что у первого игрока имеется или отсутствует
выигрышная стратегия? Ответ обоснуйте.
Решение:
Для доказательства построим граф, охватывающий все стратегии как 1-го игрока, так и 2-
го.
Начальная ситуация игры: в емкостях лежит (3 и 6) камней или всего 9. Ситуация S0.
1-й Шаг игры. Ход 1-го игрока. Он может перевести ситуацию S0 в 4-ре новых
ситуации:
S11= (3+2,6)= (5,6); S12= (3х2,6)= (6,6); S13= (3,6+2)= (3,8); S14= (3,6х2)= (5,12);
2-й Шаг игры. Ход 2-го игрока. Он может перевести любую из 4-х ситуаций S11,
S12, S13 и S14, в 4-ре новых ситуации.
Например, рассмотрим изменение ситуации S11:
S111=(5+2,6)=(7,6); S112=(5х2,6)=(10,6); S113=(5,6+2)=(5,8); S114=(5,6х2)=(5,12);
Анализ: на один из вариантов не дает окончания игры, т.к. во всех ситуациях сумма камней
меньше 24.
И так далее, можно рассмотреть все возможные исходы из других ситуаций и принять
правильную стратегию для следующего хода.
3-й Шаг игры. Снова ход 1-го игрока. Он уже исходит из сложившейся конкретной
ситуации.
Нарисуем граф отображающий все множество стратегий этой игры и проанализируем
различные стратегии. Выберем выигрышную для 1-го игрока и определим правильный ход
на 1-м шаге.