Информатика. Учебник для 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. Выполните по указанию учителя задания в рабочей тетради.
§18. Игровые стратегии.