Стратегия в игре
В задачах на стратегию нужно не угадать несколько удачных ходов, а доказать результат для любого ответа соперника. Для этого строят граф игры, классифицируют позиции как выигрышные и проигрышные и затем описывают стратегию перехода из одной позиции в другую.
Что такое стратегия в игре
Рассмотрим игру двух игроков, которые ходят по очереди. В каждый момент известна позиция в игре — например, текущее число камней в куче. Из позиции разрешены определённые ходы. Игра заканчивается, когда игрок не может сделать ход или выполняется условие победы, указанное в задаче.
Стратегия — правило выбора хода, которое по любой возникшей позиции указывает, что делать игроку. Выигрышная стратегия гарантирует победу независимо от ходов соперника.
Полное дерево игры содержит вершины-позиции и рёбра-переходы между ними. Корень — начальная позиция, дочерние вершины — позиции после одного допустимого хода. На практике всё дерево часто не рисуют: достаточно рассуждать о типах позиций и о переходах между ними.
Выигрышные и проигрышные позиции
Сначала нужно точно определить, кто делает ход и какое условие окончания считается победой. В школьных задачах часто встречается правило: игрок, после хода которого количество камней становится не меньше заданного \(T\), выигрывает.
Выигрышная позиция — позиция, из которой игрок, делающий ход, может гарантировать победу. Проигрышная позиция — позиция, из которой при правильной игре соперника победить нельзя.
Если из позиции есть хотя бы один ход в проигрышную для соперника позицию, текущая позиция выигрышная. Если все допустимые ходы ведут в выигрышные для соперника позиции, текущая позиция проигрышная.
Здесь \(W(P)\) означает, что позиция \(P\) выигрышная, а \(L(P)\) — проигрышная. Важна разница между словами «существует» и «для любого»: свой ход мы выбираем сами, а ход соперника заранее неизвестен.
В простейшем случае терминальные позиции, где ход сделать нельзя, являются проигрышными для игрока, которому нужно ходить. Затем классификация распространяется назад по дереву. Такой подход связан с выигрышной позицией и проигрышной позицией, которые полезно повторить перед решением задач.
Как построить выигрышную стратегию
- Запишите позицию одним или несколькими параметрами: например, \(s\) — число камней в куче.
- Перечислите все разрешённые ходы и условие немедленной победы.
- Найдите конечные проигрышные позиции или позиции, из которых уже нельзя продолжать игру.
- Определите позиции, из которых есть ход в проигрышную позицию.
- Если соперник может сделать несколько ответов, рассмотрите каждый ответ и найдите свой следующий гарантированный ход.
- Сформулируйте стратегию словами: «после любого хода соперника делаем ...».
Для одной кучи часто достаточно таблицы значений \(W(s)\) и \(L(s)\). Если ходы изменяют несколько параметров, применяют оптимизацию динамического программирования или двумерное динамическое программирование. Если величина после ходов всё время движется к границе, помогает моновариант.
Не пишите только первый ход. Сначала укажите позицию, которую нужно получить, затем докажите, что после каждого хода соперника можно снова попасть в нужный класс позиций. Это и есть гарантия результата.
Позиция P имеет три хода: в проигрышную позицию L1 и в две выигрышные позиции W1 и W2. Какова позиция P при ходе игрока?
Разобранный пример: два хода до победы
Игра: в куче \(s\) камней. За ход можно добавить \(1\) или \(2\) камня. Побеждает игрок, после хода которого в куче станет не менее \(20\) камней. Требуется определить, при каких начальных \(s\) первый игрок может выиграть своим первым ходом, а при каких он выигрывает вторым ходом.
Позиции \(18\) и \(19\) выигрышные для игрока, который ходит: из них можно сразу получить не менее \(20\). Значит, нужно искать позиции, из которых любой первый ход ведёт в одну из этих позиций, а самому игроку после ответа соперника остаётся сделать победный ход.
Для точного ответа полезно проверить все ближайшие значения. Проигрышная позиция здесь одна: \(s=17\). Из \(15\) первый игрок может добавить \(2\) и передать сопернику \(17\). Затем соперник добавит \(1\) или \(2\), а первый игрок добавит столько, чтобы получить не менее \(20\).
Показать полное решение Решение
Из начальной позиции \(15\) первый игрок добавляет \(2\), получает \(17\). Если соперник добавляет \(1\), становится \(18\), и первый добавляет \(2\). Если соперник добавляет \(2\), становится \(19\), и первый добавляет \(1\). В обоих случаях первый игрок выигрывает своим вторым ходом.
Следовательно, при \(s=15\) первый игрок выигрывает вторым ходом, причём стратегия учитывает оба возможных ответа соперника.
Как оформлять ответы на экзамене
В задачах типа ege-19, ege-20 и ege-21 обычно требуется назвать начальные значения, при которых выигрывает первый или второй игрок, и указать стратегию. Ответ должен содержать не только число, но и доказательство.
- Указано, кто делает первый ход.
- Перечислены все допустимые ходы.
- Отдельно разобраны все ответы соперника.
- Объяснено, почему следующий ход приводит к победе.
- Не перепутаны «победа первым ходом» и «победа вторым ходом».
Ошибка 1: рассмотреть один удачный ответ соперника вместо всех возможных. Ошибка 2: назвать позицию выигрышной только потому, что из неё можно приблизиться к цели. Ошибка 3: забыть, что достижение порога обычно означает немедленную победу и игра заканчивается. Ошибка 4: перепутать число камней до хода и после хода. Ошибка 5: доказать существование хода, но не доказать, что стратегия работает после следующего ответа соперника.
Если в задаче играют несколько куч или меняются разные параметры, рисуйте небольшое дерево игры для критических позиций. При повторяющейся структуре переходов удобно использовать полуинвариант — величину или свойство, сохраняющееся после серии ходов.
Быстрая проверка
Проверь себя
Главное
- Стратегия — правило выбора хода для любой возникшей позиции.
- Выигрышная позиция имеет хотя бы один переход в проигрышную позицию соперника.
- Проигрышная позиция имеет только переходы в выигрышные позиции соперника.
- Для доказательства нужно разобрать каждый возможный ответ соперника.
- В задачах с кучами полезно двигаться от конечных позиций назад и искать повторяющийся шаблон.
- В ответе важно явно указать первый ход и продолжение стратегии после каждого ответа соперника.