Ученики на Учителя.com


Задача №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-м шаге.
Рис.1. Граф отображающий все множество стратегий в игре Примера 1.
(красные вершины – отражают выигрыш игрока)
Из анализа Графа стратегий видно, что только одна стратегия гарантирует 1-му игроку
выигрыш вне зависимости ходов 2-го игрока. Это стратегия S11= (3+2,6)= (5,6), которая
переводит игру из ситуации S0(3,6) в ситуацию S11= (5,6). (синий круг на рис.1).
Не зависимо от выбора 2-го игрока у 1-го имеется однозначная возможность достичь
выигрышной ситуации ( «сумма камней больше или равна 24») первым.
В других ситуациях при неправильном выборе на первом шаге, 1-й игрок не получает
выигрыша.
Таким образом 1-й игрок на первом ходу обязательно должен добавить 2 камня к первой
емкости (т.е. 3+2=5).
Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в
первую кучу.
3. Определение выигрышной стратегии для произвольной ситуации
Пример 2.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи кам-
ней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить
в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в
два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в
игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх пози-
ций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть
неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не
менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получив-
ший такую позицию, что в кучах всего будет 73 камня или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при
любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен
сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у
Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет
выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните,
почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов
может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков
имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объяс-
ните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество
ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стра-
тегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигры-
шу, и укажите, какое наибольшее количество ходов может потребоваться победителю для
выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной
Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Решение:
Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При
начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих
четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее
73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержа-
щую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32)
после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32),
(16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из
любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней,
удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети вы-
игрывает своим первым ходом.
Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети.
При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из на-
чальных позиций (7, 32) и (8, 31) Петя после первого хода должен получить позицию (8,
32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выиг-
рышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стра-
тегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигры-
вает своим вторым ходом.
Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого
хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В
позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней
во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих
позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стра-
тегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры
Пети Ваня выигрывает на первом или втором ходу.
Ответ:
Задание 1. Ваня выигрывает своим первым ходом.
Задание 2. Петя выигрывает своим вторым ходом.
Задание 3. Ваня выигрывает первым или вторым ходом.
Определение начальной позиции, обеспечивающей выигрыш того или иного игрока
Пример 3.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней.
Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в
кучу один камень или увеличить количество камней в куче в три раза. Например, имея
кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого иг-
рока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 48.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу,
в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤
47.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при
любых ходах противника. Описать стратегию игрока — значит описать, какой ход он дол-
жен сделать в любой ситуации, которая ему может встретиться при различной игре против-
ника.
1. Вопросы для самопроверки
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход.
Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждо-
го указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при
любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стра-
тегию Вани.
2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём
(а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом
независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите
выигрышную стратегию Пети.
3. Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым
ходом при любой игре Пети, и
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех
партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).
На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
Решение:
1. а) Петя может выиграть, если 16, ..., 47. Во всех этих случаях достаточно утроить коли-
чество камней. При меньших значениях S за один ход нельзя получить кучу, в которой
больше 47 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет
S = 15 камней. Тогда после первого хода Петя в куче будет 16 или 45 камней. В обоих слу-
чаях Ваня утраивает количество камней и выигрывает в один ход.
2. Возможные значения S: 5 и 14. В этих случаях Петя, очевидно, не может выиграть первым
ходом. Однако он может получить кучу из 15 камней: в первом случае утроением, во втором
добавлением одного камня. Эта позиция разобрана в п. 16. В ней игрок, который будет хо-
дить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим
ходом выиграет.
3. Возможное значение S: 13. После первого хода Пети в куче будет 14 или 39 камней. Если
в куче станет 39 камней. Ваня утроит количество камней н выиграет первым ходом. Ситу-
ация, когда в куче 14 камней, уже разобрана в п. 2. В этой ситуации игрок, который будет
ходить (теперь это Ваня), выигрывает своим вторым ходом.
На рисунке изображено дерево игры. Выигрышные позиции подчеркнуты.
Ответ:
1. а) S от16 до 47
б) S = 15
2. S = 5 и S = 14
3. S = 13
4. Вопросы для самопроверки
1. Определите формально правила игры (приведите пример игры по правилам)
2. Как с помощью графа можно отобразить изменения в состоянии игровой ситуации
(приведите пример графа простой игры двух игроков)
3. Что отображает путь на графе от исходной ситуации (S0) до конечной ситуации
(Sn) для игрока.
4. Как можно рассчитать количество выигрышных ситуаций для игрока (какой метод
вам удобнее графом или таблицей)
Литература и источники:
1. Станкевич А. Игры на графах - https://ejudge.lksh.ru/archive/2014/08/A/games.pdf
2. Построение графической схемы алгоритма - https://megapredmet.ru/1-3657.html
3. Основные комбинаторные ситуации - https://cyberpedia.su/16x3e61.html
4. https://ege-study.ru/ru/ege/materialy/informatika/zadanie-26/
Скачать материал

Информатика - еще материалы к урокам: