Что такое выигрышная стратегия в игре
Игры и выигрышные стратегии
Определение игры
Человек с самого детства и всю жизнь играет в игры. И если некоторое представление о детских, логических и компьютерных играх имеют все, то далеко не все знают, что, например, выбор банка, в котором следует открыть счет, — это тоже игра (в математическом смысле слова). В математике существует специальный раздел — теория игр, в котором изучаются свойства игр в широком смысле.
Определимся сразу, что мы будем рассматривать не все игры, а только их определенный класс. Нас будут интересовать игры с противоречивыми интересами сторон (антагонистические игры) и полной информацией об игре, и в первую очередь такая разновидность подобных игр, как игра двух лиц с нулевой суммой.
Игра двух лиц (в дальнейшем будем называть их первый игрок и второй игрок, подразумевая игроков, которые ходят первым и вторым соответственно) с нулевой суммой означает, что выигрыш одного игрока является проигрышем другого (в ряде игр возможна ничья).
В рассматриваемых нами играх участвуют два игрока, которые ходят по очереди, причем оба они обладают полной информацией о текущей игровой ситуации (это определение исключает большинство карточных игр) и о возможных ходах очередного игрока. Игра считается оконченной, если достигнута позиция, являющаяся согласно правилам игры “терминальной” (конечной, заключительной), например, матовая позиция в шахматах. Правилами игры также устанавливается, каков исход игры в этой терминальной позиции.
· указать конечное множество, элементы которого называются позициями игры;
· указать начальную позицию игры;
· указать множество заключительных позиций и задать результат игры в каждой из них;
· для каждой из остальных позиций указать возможные ходы, т.е. позиции, которые могут случиться после хода первого или второго игрока соответственно (в некоторых играх возможные ходы не зависят от того, какой именно игрок ходит).
При этом в игре не должно быть бесконечных партий (бесконечных последовательностей позиций, в которых игроки ходят по правилам, но так и не попадают в заключительную позицию).
Если к тому же ни в каких аспектах игры (правилах, возможности или очередности ходов, определении момента завершения игры или результата) не участвует элемент случайности, такая игра будет еще и детерминированной.
Классификация позиций и стратегии игроков
Пусть в нашей игре не бывает “ничьих” и игроки ходят по очереди. Нетерминальная позиция называется выигрышной, если в ней существует какой-нибудь разрешенный ход, приводящий к выигрышу. С другой стороны, некоторая нетерминальная позиция является проигранной для игрока, если все разрешенные ходы из этой позиции ведут к позициям, в которых возможен выигрыш противника. Запишем это более формально.
Нетерминальная позиция 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 Игра приведена, в частности, в книге А.Шеня “Игры и стратегии с точки зрения математики”.
Стратегические игры и решение задач. Игра Ним и ей подобные
(Тут будет о истории Ним и подобных играх, так что если лень, листайте сразу до «Об определении стратегии» (Это под 2 картинкой))
Сосредоточим внимание на так называемых стратегических играх. Их можно разделить на два типа. Те, что описываются простыми правилами, длятся короткое время и количество информации в которых ограничено или относительно невелико, будем называть малыми стратегическими играми.
В других, подобных шахматам или го, полный контроль невозможен ввиду длительности партии, сложности правил и в особенности из-за огромного числа возможных ходов в каждой позиции. На примере малых стратегических игр мы увидим, как математика используется в анализе игр для определения преимущества одного из игроков и для нахождения выигрышной стратегии.
Взаимосвязь между математикой и играми может касаться различных аспектов игр. Применительно к стратегическим играм математика особенно полезна для определения выигрышной стратегии. Стратегическая игра очень похожа на процесс решения математической задачи: речь идет не о том, чтобы выиграть одну партию, совершая более удачные ходы, но о том, чтобы найти способ, как выигрывать всегда. По этой причине при определении выигрышных стратегий используются эвристические методы: способ «от обратного»; предположение, что игра «решена»; применение симметрии; проведение аналогии с другой, уже решенной игрой и прочие. Они аналогичны тем, что используются при решении математических задач. Поэтому когда для некоторой игры известна выигрышная стратегия, игра из развлечения превращается в решенную задачу. Понятно, что это верно только для определенных игр, которые выходят за рамки простых развлечений и описываются в математических теориях. О подобных теориях, порой достаточно сложных, мы, возможно, поговорим позже.
Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр
подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.
Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она будет рассматриваться в следующих постах под названием «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.
Определение общей выигрышной стратегии, применимой к любой игре такого типа, — одно из ярчайших проявлений того, как математика используется для анализа игр, и в особенности того, насколько эффективно представление чисел в двоичной системе.
Об определении стратегии
Сначала мы проанализируем игры с одной группой фишек, в которых на каждом ходу можно брать со стола минимум одну и максимум n фишек. Мы рассмотрим два частных случая, затем приведем обобщение. Самый простой вариант подобной игры таков.
Игра 1: выигрывает первый
На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если вы незнакомы с этой игрой, перед прочтением попробуйте сыграть в нее самому и постараться ответить на заданные выше вопросы.
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну
фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2017), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру
можно обобщить и дальше, изменив число фишек, которые можно брать на каждом
Игра 2: выигрывает второй
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Игровые стратегии.
Информатика. Учебник для 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. Выполните по указанию учителя задания в рабочей тетради.