Задание 26 — «Теория игр, поиск выигрышной стратегии» — характеризуется высоким уровнем сложности, время выполнения – примерно 30 минут, максимальный балл — 3. Процент выполнения весьма неплохой - 48%.
Все позиции в простых играх делятся на выигрышные и проигрышные.
Выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, обязательно выиграет при любых действиях соперника, если не допустит ошибки; при этом говорят, что у данного игрока есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть.
Если игрок, делающий первый ход, находится в проигрышной позиции, то он обязательно проиграет, если ошибку не сделает его оппонент; в этом случае говорят, что у данного игрока нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для оппонента.
Для того чтобы найти выигрышную стратегию в несложных играх, достаточно использовать метод перебора всех возможных вариантов ходов игроков или применить метод построения деревьев.
Рассмотрим пример:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 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)?
Игроки могут делать два хода — прибавить к любой из куч один камень, или умножить количество камней в любой из куч на два. Игрок выигрывает, когда количество камней в куче становится >= 73. Рассмотрим первый ход на графе (каким может быть первый ход):
Петя делает ход первым и не может получить выигрышное количество >=73, а вот Ваня может, удвоив количество камней во второй куче после хода Пети:
7 + 2*33 = 73 9 + 2*32 = 73
6 + 2*66 = 138 8 + 2*64 = 136
То есть при позициях (6, 33) и (8, 32) второй игрок (Ваня) выигрывает первым ходом.
Задание 2. Ответим на вопрос: кто из игроков имеет выигрышную стратегию при позициях (6, 32), (7, 32), (8, 31)?
Петя ходит первым и он хочет выиграть (но выиграть первым ходом из данных трех позиций невозможно) и постараться сделать так, чтобы Ване досталась проигрышная позиция. Из задания 1 нам известны две проигрышные позиции — (6, 33) и (8, 32). Эти проигрышные позиции Петя может сделать своим первым ходом для Вани из предложенных позиций:
(6, 32) -> (6, 33)
(7, 32) -> (8, 32)
(8, 31) -> (8, 32)
Петя хочет - Петя сделает. В результате Ваня своим первым ходом проиграет , а Петя выиграет своим вторым ходом. Получается данные позиции выигрышные для Пети.
Задание 3. Кто из игроков имеет выигрышную стратегию при позиции (7, 31)?
Петя ходит первым. Рассмотрим все возможные ходы Пети из позиции (7, 31):
Тогда Ване могут достаться позиции
Далее,
Важно помнить, что каждый игрок не только хочет выиграть за меньшее количество ходов, но и не позволить сопернику выиграть за меньшее количество шагов.
Выходит, что все позиции, которые достались Ване — выигрышные.
Указания по оцениванию:
В задаче требуется выполнить три задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий.
Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу – например, арифметическая ошибка при вычислении количества камней в заключительной позиции – при оценке решения не учитывается.
Если верно выполнены все три задания - получаете 3 балла.
Если верно выполнили 1 и 2 или одно только 3 задание - 2 балла.
Если выполнили 1 или 2 задание - 1 балл.
Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.
Читайте также: Задание 1, Задание 2, Задание 3, Задание 4, Задание 5, Задание 6, Задание 7, Задание 8, Задание 9, Задание 10, Задание 11, Задание 12, Задание 13, Задание 14, Задание 15, Задание 22, Задание 16, Задание 17, Задание 18, Задание 19, Задание 20, Задание 21, Задание 23, Задание 24, Задание 25, Задание 27.
Еще больше интересного материала в группе в ВК и на сайте. Кроме этого, можете воспользоваться услугами репетитора.
