5 что такое выигрышная стратегия в игре
26. Выигрышные стратегии
26. Выигрышные стратегии.
· все позиции в простых играх делятся на выигрышные и проигрышные
· выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку; при этом говорят, что у него есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть
· если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник; в этом случае говорят, что у него нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника
· выигрышные и проигрышные позиции можно охарактеризовать так:
— позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная;
· в дереве игры указываются ВСЕ ходы проигрывающего игрока и ХОД Ы ПО СТРАТЕГИИ выигрывающего игрока
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или добавить в кучу два камня или увеличить количество камней в куче в 3 раза. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 12 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче превышает 54. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 55 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 54.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Укажите 3 значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети.
Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.
а) Петя может выиграть, если S = 19, …, 54. При меньших значениях S за один ход нельзя получить кучу, в которой будет 55 или более камней. Пете достаточно увеличить количество камней в 3 раза.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 18 камней. Тогда после первого хода Пети в куче будет 19 камней, 20 камней или 54 камня. Во всех случаях Ваня увеличивает количество камней в 3 раза и выигрывает в один ход.
Возможные значения S: 6, 16, 17. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако Петя может получить кучу из 18 камней: при S = 6 он утраивает количество камней, при S = 16 добавляет 2 камня, при S = 17 добавляет 1 камень. Позиция с кучей из 18 камней разобрана в п. 1б. В ней игрок, который будет ходить (в данном случае это Ваня), выиграть не может, а его противник (т. е. Петя) следующим ходом выиграет.
Возможное значение S: 15. После первого хода Пети в куче будет 16 камней, 17 камней или 45 камней. Если в куче станет 45 камней, то Ваня увеличит количество камней в 3 раза и выиграет своим первым ходом. Ситуация, когда в куче 16 или 17 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом. На рисунке изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчёркнуты.
Р-04. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Для каждой из начальных позиций (10, 43), (12, 42) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Для каждой из начальных позиций (10, 42), (11, 42), (12, 41) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Для начальной позиции (11, 41) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Задание 1. В начальных позициях (10, 43), (12, 42) выигрышная стратегия есть у Вани.
При начальной позиции (10, 43) после первого хода Пети может получиться одна из следующих четырёх позиций: (11, 43), (20, 43), (10, 44), (10, 86). Каждая из этих позиций содержит менее 97 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 97 камней, удвоив количество камней во второй куче.
Для позиции (12, 42) после первого хода Пети может получиться одна из следующих четырёх позиций: (13, 42), (24, 42), (12, 43), (12, 84). Каждая из этих позиций содержит менее 97 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 97 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.
Задание 2. В начальных позициях (10, 42), (11, 42) и (12, 41) выигрышная стратегия есть у Пети. При начальной позиции (10, 42) он должен первым ходом получить позицию (10, 43), из начальных позиций (11, 42) и (12, 41) Петя после первого хода должен получить позицию (12, 42). Позиции (10, 43) и (12, 42) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.
Задание 3. В начальной позиции (11, 41) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (12, 41), (11, 42), (22, 41) и (11, 82). В позициях (22, 41) и (11, 82) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (12, 41) и (11, 42) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.
В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом.
Игры и выигрышные стратегии
Определение игры
Человек с самого детства и всю жизнь играет в игры. И если некоторое представление о детских, логических и компьютерных играх имеют все, то далеко не все знают, что, например, выбор банка, в котором следует открыть счет, — это тоже игра (в математическом смысле слова). В математике существует специальный раздел — теория игр, в котором изучаются свойства игр в широком смысле.
Определимся сразу, что мы будем рассматривать не все игры, а только их определенный класс. Нас будут интересовать игры с противоречивыми интересами сторон (антагонистические игры) и полной информацией об игре, и в первую очередь такая разновидность подобных игр, как игра двух лиц с нулевой суммой.
Игра двух лиц (в дальнейшем будем называть их первый игрок и второй игрок, подразумевая игроков, которые ходят первым и вторым соответственно) с нулевой суммой означает, что выигрыш одного игрока является проигрышем другого (в ряде игр возможна ничья).
В рассматриваемых нами играх участвуют два игрока, которые ходят по очереди, причем оба они обладают полной информацией о текущей игровой ситуации (это определение исключает большинство карточных игр) и о возможных ходах очередного игрока. Игра считается оконченной, если достигнута позиция, являющаяся согласно правилам игры “терминальной” (конечной, заключительной), например, матовая позиция в шахматах. Правилами игры также устанавливается, каков исход игры в этой терминальной позиции.
· указать конечное множество, элементы которого называются позициями игры;
· указать начальную позицию игры;
· указать множество заключительных позиций и задать результат игры в каждой из них;
· для каждой из остальных позиций указать возможные ходы, т.е. позиции, которые могут случиться после хода первого или второго игрока соответственно (в некоторых играх возможные ходы не зависят от того, какой именно игрок ходит).
При этом в игре не должно быть бесконечных партий (бесконечных последовательностей позиций, в которых игроки ходят по правилам, но так и не попадают в заключительную позицию).
Если к тому же ни в каких аспектах игры (правилах, возможности или очередности ходов, определении момента завершения игры или результата) не участвует элемент случайности, такая игра будет еще и детерминированной.
Классификация позиций и стратегии игроков
Пусть в нашей игре не бывает “ничьих” и игроки ходят по очереди. Нетерминальная позиция называется выигрышной, если в ней существует какой-нибудь разрешенный ход, приводящий к выигрышу. С другой стороны, некоторая нетерминальная позиция является проигранной для игрока, если все разрешенные ходы из этой позиции ведут к позициям, в которых возможен выигрыш противника. Запишем это более формально.
Нетерминальная позиция x называется выигрышной для игрока, которому предоставлен ход, если существует хотя бы один ход, переводящий игру в проигрышную позицию. Нетерминальная позиция x называется проигрышной, если все ходы из позиции x ведут в выигрышные позиции.
Стратегией в конечной игре с полной информацией называется правило, указывающее, как следует игроку ходить в каждой из позиций, где ход за ним. Понятие стратегии не надо отождествлять с понятием хода. Стратегия определяет полный план действий игрока при всевозможных ситуациях, могущих возникнуть в игре.
Стратегия называется выигрышной для игрока, если все партии, в которых он придерживается этой стратегии, заканчиваются выигрышем этого игрока. Покажем, что в рассматриваемом нами классе игр обязательно существует выигрышная стратегия для одного из игроков, а все позиции игры можно разделить на выигрышные и проигрышные.
Конечную игру с полной информацией можно представить в виде ориентированного графа (см. “Структуры данных”), вершинами которого являются все допустимые позиции игры, а ребра указывают возможные ходы. Данный граф обязательно будет ациклическим (не будет содержать циклов), в противном случае окончание игры не гарантировано. Будем назначать значение для каждой вершины этого графа (выигрышная или проигрышная) по таким правилам:
· значение вершин, соответствующих терминальным позициям, однозначно определено правилами игры;
· все вершины, из которых хотя бы одно ребро графа ведет в вершину, помеченную как проигрышную, помечаем как выигрышные;
· все вершины, из которых все ребра графа ведут в выигрышные позиции, помечаем как проигрышные.
Эти правила применяем в любом порядке, пока это возможно. Утверждается, что рано или поздно всем позициям игры будут присвоены определенные значения. В самом деле, если какая-то вершина графа оказалась непомеченной, то она не может быть заключительной. Более того, какая-то из следующих за ней позиций тоже осталась непомеченной (иначе мы смогли бы пометить и эту), значит, и у нее какая-то из следующих не имеет пометки и т.д.
В результате мы получаем бесконечную партию, которая по условию невозможна.
Так как все позиции оказались помеченными, то помечена и начальная позиция. Если она оказалась выигрышной, то при правильной игре первый игрок гарантированно выигрывает и его выигрышная стратегия состоит в том, чтобы на каждом ходу ставить противника в проигрышную позицию (наличие такого хода обеспечено правилом, по которому помечалась соответствующая вершина графа). Если же она помечена как проигрышная, то гарантированно выигрывает второй игрок при любом ходе первого игрока.
Программирование игр
Говоря даже об определенном классе игр, нельзя не упомянуть компьютерные программы, играющие в различные игры из данного класса. Как, например, компьютеры играют (и, как мы знаем, весьма успешно) в шахматы? Ведь полный анализ данной игры пока невозможен. Как и люди, компьютеры просчитывают варианты для текущей позиции — они смотрят, какие возможны ходы, какие ответы возможны на каждый из ходов и т.д. Просмотр приходится на каком-то уровне прерывать и грубо оценивать позицию как выигрышную или проигрышную в зависимости от материального перевеса и расположения фигур. К этому еще добавляется библиотека начал (дебютов), накопленная многовековым опытом шахматистов, а также сведения об окончаниях (эндшпилях), часть из которых, в свою очередь, удалось за последние годы просчитать на компьютере.
Если же игра такова, что число позиций в ней, по меркам современных компьютеров, не велико (скажем, не превосходит 10 6 ), то игру можно полностью просчитать, начиная с терминальных позиций. Соответствующая программа будет существенно более эффективной, если значения уже просчитанных позиций будут запоминаться в памяти компьютера и не пересчитываться повторно. Для этого, помимо прочего, надо научиться все позиции нумеровать (в ряде игр это может быть весьма нетривиальной задачей). При этом часть позиций можно будет и не просчитывать вообще: если для какого-то хода игрока выясняется, что он ведет в проигрышную позицию, то другие варианты хода можно уже не рассматривать (текущая позиция выигрышная).
На столе лежат N камней. Играющие по очереди могут взять от одного до четырех камней. Кто не может сделать ход (камней не осталось) — проигрывает. Если N делится на 5 без остатка, то второй игрок может гарантировать себе выигрыш, дополняя ход противника до 5 (если первый взял одну, то второй берет четыре и т.д.). Если N на 5 не делится, то выигрывает первый игрок: он должен сначала взять число камней, равное остатку от деления N на 5, а потом дополнять ход противника до 5. Здесь все позиции с числом камней кратным 5 являются проигрышными, остальные — выигрышными. Программирование выигрышной стратегии для такой игры не составит труда.
Часто в играх используется и так называемая “симметричная стратегия”. Например, двое игроков кладут одинаковые круглые монеты на прямоугольный стол. Монеты могут свешиваться за край, но не должны падать и перекрываться. Кто не может положить монету — проигрывает. В этой игре первый игрок может выиграть, положив первым ходом свою монету в центр стола, а затем повторяя ходы второго игрока симметрично относительно центра. Очевидно, что если второй игрок нашел место для монеты, то есть и пустое симметричное ему место. В этой игре число позиций бесконечно (хотя сама игра конечна), но идея симметрии применяется и в ситуациях с конечным числом позиций.
Методические рекомендации
Тема выигрышные стратегии в играх появилась в профильном уровне стандарта среднего (полного) общего образования по информатике. Изучение темы “Игры и выигрышные стратегии” позволяет показать ученику научный подход к решению ряда бытовых задач, расширяет их кругозор с точки зрения практической применимости знаний математики и алгоритмов. Ранее подобные задачи встречались лишь на олимпиадах по информатике и программированию и опирались на знания, полученные учащимися математических классов в углубленном курсе математики. Начиная с 2005 г. задачи на поиск выигрышной стратегии встречаются и в материалах ЕГЭ по информатике. Приведем пример задачи из демоверсии ЕГЭ 2007 г.
Задача. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет один камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение. Выигрывает второй игрок.
Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа соответствуют количеству камней на каждом этапе игры, в первой и второй кучах соответственно. Приведенная на с. 36 таблица содержит все возможные варианты ходов первого игрока. Из нее видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.
В бескомпьютерном варианте предлагаемые задачи по информатике на данную тему таковы, что общее число позиций в игре позволяет провести практически полный ее анализ так, как было рассказано в материалах статьи.
Программирование стратегий одного из игроков в различных логических играх может стать хорошей темой для кружковой и внеклассной работы учащихся (подготовка к конференциям, турнирам игровых программ, в которых программы играют между собой, и т.п.).
4 См. книгу А.Шеня “Игры и стратегии с точки зрения математики”. М.: изд-во МЦНМО, 2007.
5 Игра приведена, в частности, в книге А.Шеня “Игры и стратегии с точки зрения математики”.
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Игровые стратегии.
Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)
§18. Игровые стратегии.
Выигрышные и проигрышные позиции
Ключевые слова:
Как вы уже знаете из § 16, игровые модели — это модели, которые описывают соперничество двух (или более) сторон, каждая из которых стремится к выигрышу, т. е. преследует свою цель. Часто цели участников противоречивы — выигрыш одного означает проигрыш других.
Построением и изучением игровых моделей занимается теория игр — раздел прикладной математики. Задача состоит в том, чтобы найти стратегию (алгоритм игры), который позволит тому или другому участнику получить наибольший выигрыш (или, по крайней мере, наименьший проигрыш) в предположении, что соперники играют безошибочно.
Стратегия — это алгоритм игры, который позволяет добиться цели в игре в предположении, что соперники играют безошибочно.
Мы будем изучать игры с полной информацией, в которых результат не зависит от случая (говорят, что в таких играх нет неопределённое™). Игроки делают ходы по очереди, в любой момент им известна позиция и все возможные дальнейшие ходы.
Можно ли считать играми с полной информацией «крестики-нолики», карточные игры, шахматы, шашки, «морской бой»?
Теоретически в играх с полной информацией можно построить последовательность ходов из заданной начальной позиции, которая приведёт одного из игроков к выигрышу или, по крайней мере, к ничьей. Нас будут интересовать простые игры, где не так много вариантов развития событий и перебор ходов возможен за приемлемое время. В большинстве игр, например в шахматах, количество вариантов настолько велико, что их полный перебор требует огромного времени и поэтому нереален.
Подсчитайте, сколько различных ходов могут сделать крестики в начале игры «крестики-нолики» на поле 3×3. Сколько различных позиций может возникнуть после ответного хода ноликов? После второго хода крестиков? После второго хода ноликов? Как можно сократить количество рассматриваемых вариантов в этой игре?
Подсчитайте, сколько различных ходов могут сделать белые в начале шахматной игры.
Все позиции (игровые ситуации) делятся на выигрышные и проигрышные.
Выигрышная позиция — это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку.
При этом говорят, что у него есть выигрышная стратегия — алгоритм выбора очередного хода, позволяющий ему выиграть.
Проигрышная позиция — это такая позиция, в которой игрок, делающий первый ход, обязательно проиграет, если его соперник не сделает ошибку.
В этом случае говорят, что у него нет выигрышной стратегии. Таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника.
Найдите среди позиций игры в «крестики-нолики», показанных на рис. 3.37, выигрышные и проигрышные. Во всех случаях ходят нолики.
Рис. 3.37
Найдите все возможные ходы белых и чёрных фигур в позиции, показанной на рис. 3.38.
Рис. 3.38
Найдите выигрышный ход белых (они начинают).
Выигрышные и проигрышные позиции можно охарактеризовать так:
• позиция, из которой все возможные ходы ведут в выигрышные позиции, — проигрышная;
• позиция, из которой хотя бы один из возможных ходов ведёт в проигрышную позицию, — выигрышная, при этом выигрышная стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.
В позициях, показанных на рис. 3.39, найдите выигрышный ход ноликов, который создаёт проигрышную (для крестиков) позицию.
Рис. 3.39
Докажите, что все позиции, показанные на рис. 3.40, проигрышные для ноликов. Рассмотрите все возможные ходы и для каждого из них укажите выигрывающий ход крестиков.
Рис. 3.40
Дерево перебора вариантов
Одна из простых игр, где можно перебрать все варианты, — это игра с камнями. Перед двумя игроками лежит куча из некоторого количества камней (обозначим его S) или других одинаковых предметов (монет, бусин, пуговиц и т. п.) За один ход игрок может взять один или два камня. Тот, кто возьмёт последний камень, проигрывает.
Сыграйте в эту игру с соседом несколько раз для S = 6. Начинайте игру по очереди.
Для небольших значений S легко построить дерево перебора вариантов. Для S = 4 такое дерево показано на рис. 3.41.
Рис. 3.41
Буквой П обозначены ходы первого игрока (пусть его зовут Петя), а буквой В — ходы второго игрока (будем называть его Ваней). Числа в узлах дерева показывают количество камней в куче после очередного хода, а «-1» и «-2» — взятие из кучи соответственно одного или двух камней.
Очевидно, что позиция S = 1 — проигрышная: тот, кто ходит в этой позиции, проигрывает, потому что берёт последний (единственный) камень. Тогда выигрышными будут все позиции, из которых можно получить S = 1 каким-либо ходом — это позиции S = 2 и S = 3.
Из позиции S = 4 все возможные ходы ведут в выигрышные позиции S = 2 и S = 3, поэтому эта позиция проигрышная. Если Ваня не сделает ошибку, то Петя в любом случае проиграет.
Используя дерево перебора вариантов, выясните, какой ход должен сделать Ваня, чтобы выиграть в позиции S = 2? В позиции S = 3?
Выигрышную стратегию можно показать с помощью неполного дерева игры. Дело в том, что для выигрывающего игрока нам достаточно указать на каждом ходу один-единственный вариант, переводящий игру в проигрышную (для его соперника) позицию. А вот для проигрывающего игрока на каждом ходу нужно рассматривать все варианты, чтобы доказать, что он никак не может избежать поражения. Построим неполное дерево для начальной позиции S = 4, в которой, как мы показали, выигрышная стратегия есть у второго игрока (рис. 3.42).
Рис. 3.42
По этому дереву видно, что при любом своём первом ходе Петя обязательно проигрывает на втором ходу, взяв последний камень (если, конечно, Ваня не ошибётся).
Постройте дерево перебора вариантов для игры с камнями при S = 6. Выясните, какова начальная позиция — выигрышная или проигрышная. Почему? Постройте неполное дерево игры с доказательством стратегии выигрывающего игрока.
По результатам исследований определите, при каких значениях S начальные позиции будут выигрышными, а при каких — проигрышными. Если позиция выигрышная, какой стратегии должен следовать Петя?
Решение без дерева
Для того чтобы при заданном значении S определить, какова начальная позиция — выигрышная или проигрышная, не обязательно строить дерево. Составим таблицу, в которой для каждой позиции (для каждого значения S) будем указывать, какая это позиция и на каком ходу завершится игра. Как мы знаем, S = 1 — это проигрышная позиция, Петя проигрывает за один ход. Отмечаем её в таблице как П, где буква «П» означает проигрыш, а индекс «1» — количество ходов (рис. 3.43).
Рис. 3.43
Выигрышными будут все позиции, из которых можно каким-либо ходом получить проигрышную позицию S = 1, т. е. позиции S = 2 и S = 3. Отмечаем их как В, (выигрыш за 1 ход) — рис. 3.44.
Рис. 3.44
Из позиции S = 4 все возможные ходы ведут в выигрышные позиции, поэтому эта позиция — проигрышная (проигрыш за 2 хода) — рис. 3.45.
Рис. 3.45
Рассуждая таким же образом, заполните таблицу до конца.
Исследование игры
Исследуйте самостоятельно следующую игру.
В игре участвуют два игрока, назовём их Петя (он ходит первый) и Ваня (второй). Вначале перед игроками лежит куча из некоторого количества камней (обозначим его S). За один ход игрок может добавить в кучу один камень (ход «+1») или увеличить количество камней в куче в два раза (ход «*2»). Например, имея кучу из 5 камней, за один ход можно получить кучу из 6 или 10 камней. У каждого игрока есть неограниченное количество камней. Победителем считается игрок, первым получивший кучу, в которой 14 камней или больше.
а) Определите, при каких значениях S Петя может выиграть первым ходом.
б) Определите, при каких значениях S Петя не может выиграть первым ходом, а Ваня выигрывает своим первым ходом. Заполните таблицу выигрышных и проигрышных позиций для всех значений S от 1 до 13.
в) Определите, при каких значениях S Ваня не всегда может выиграть своим первым ходом, но у него есть стратегия, следуя которой он выигрывает своим первым или вторым ходом.
г) Постройте неполное дерево игры с доказательством стратегии выигрывающего игрока при S = 4.
Выводы
• Стратегия — это алгоритм, который позволяет добиться цели в игре в предположении, что соперники играют безошибочно.
• Выигрышная позиция — это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку.
• Проигрышная позиция — это такая позиция, в которой игрок, делающий первый ход, обязательно проиграет, если его соперник не сделает ошибку.
• Позиция, из которой все возможные ходы ведут в выигрышные позиции, — проигрышная.
• Позиция, из которой хотя бы один из возможных ходов ведёт в проигрышную позицию, — выигрышная, при этом выигрышная стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.
Нарисуйте в тетради интеллект-карту этого параграфа.
Вопросы и задания
1. Что такое выигрышная стратегия в игре?
2. Как доказать, что заданная позиция в игре является выигрышной (или проигрышной)? Как вы думаете, в каких случаях это сделать не удаётся?
3. Почему для того, чтобы доказать выигрыш какого-то игрока в заданной начальной позиции, не нужно строить полное дерево игры?
4. Выполните по указанию учителя задания в рабочей тетради.