Теория игр: выигрышная стратегия
Ты научишься классифицировать игровые позиции и находить выигрышную стратегию на нужное число ходов.
Зачем на экзамене
В заданиях 19, 20 и 21 рассматривается игра двух участников с полной информацией. Игроки по очереди изменяют одну или несколько куч, а победа определяется достижением заданного результата. Нужно не угадывать удачный ход, а доказать стратегию для всех допустимых ответов соперника.
Что нужно уметь
- описывать позицию игры набором чисел;
- строить все допустимые ходы из позиции;
- отмечать позиции, в которых игра уже закончена;
- различать выигрыш за один ход и выигрыш не позднее заданного хода;
- проверять ходы первого игрока по условию "существует", а ответы соперника по условию "для всех";
- находить минимальное или максимальное начальное значение с требуемым свойством;
- формулировать стратегию, а не только называть ответ.
База
Позиция, ход и терминальное состояние
Позиция полностью описывает текущее состояние игры. Для одной кучи это число камней S, для двух куч: пара (a, b). Ход переводит позицию в одну из следующих позиций по правилам задачи.
Терминальная позиция уже удовлетворяет условию окончания игры. Например, если выигрывает тот, кто первым получает не менее T камней, то для двух куч терминальны позиции с a + b >= T. Игрок, сделавший ход в такую позицию, победил.
Игровые задания предполагают разумную игру обоих участников. Поэтому недостаточно найти один удобный ответ соперника. Стратегия должна работать при любом его допустимом ходе.
Выигрышные и проигрышные позиции
Нетерминальная позиция является выигрышной, если существует ход в проигрышную для соперника позицию. Позиция является проигрышной, если каждый допустимый ход ведет в выигрышную для соперника позицию.
| Что доказываем | Как проверяем следующие позиции |
|---|---|
| текущий игрок может выиграть | достаточно хотя бы одного подходящего хода |
| текущий игрок неизбежно проигрывает | нужно проверить все его ходы |
| стратегия работает после ответа соперника | для каждого ответа должен существовать выигрышный продолженный ход |
Слои позиций по числу ходов
Удобно размечать позиции от конца игры. Обозначим через W1 позиции, из которых игрок может победить одним ходом. Через L1 обозначим позиции, из которых любой ход переводит соперника в W1. Тогда W2 содержит позиции, из которых есть ход в L1.
| Слой | Смысл | Условие |
|---|---|---|
W1 | победа текущего игрока за один ход | есть ход в терминальную позицию |
L1 | поражение после любого своего хода | все ходы ведут в W1 |
W2 | победа своим вторым ходом | есть ход в L1 |
L2 | соперник победит не позднее второго хода | все ходы ведут в W1 или W2 |
Если требуется победа именно вторым ходом, исключи позиции, где уже возможна победа первым ходом. Формулировки "не позднее второго хода" и "вторым ходом, но не первым" задают разные множества начальных значений.
Рекурсивная проверка
Для большого диапазона позиции удобно проверять программой. Функция получает позицию и номер хода, завершает вычисление в терминальном состоянии и затем соединяет результаты дочерних позиций через any или all.
Выбор операции зависит не только от имени игрока, но и от утверждения, которое доказывается. На ходе игрока, чью победу ищем, обычно нужен хотя бы один успешный вариант. На ходе соперника должны быть успешны все его ответы.
Как решать
- Запиши позицию и условие окончания игры.
- Перечисли все функции перехода. Для двух куч не забудь применить каждую разрешенную команду к каждой куче.
- Найди позиции
W1: из них можно сразу попасть в терминальное состояние. - Найди позиции
L1: проверь, что каждый ход отдает сопернику позициюW1. - Продолжай разметку слоями до требуемого числа ходов.
- Отдельно обработай слова "именно", "не позднее", "после любого хода" и "при неудачной игре".
- Выбери из подходящих начальных значений минимум, максимум или все значения по условию.
- Проверь ответ: назови первый ход стратегии и объясни реакцию на каждый тип ответа соперника.
Частые ошибки
- Ошибка: считать выигрышным любой путь, на котором соперник ошибся. Как избежать: на ходе соперника проверяй все допустимые ответы.
- Ошибка: продолжать игру после достижения цели. Как избежать: проверяй терминальное условие до построения новых ходов.
- Ошибка: путать ход игрока с одним изменением кучи. Как избежать: один выбор команды и есть один ход, даже если значение умножается сразу.
- Ошибка: включать
W1в ответ на вопрос о победе именно вторым ходом. Как избежать: вычитай более ранние выигрышные слои. - Ошибка: забывать ходы со второй кучей. Как избежать: выпиши переходы формулами до начала перебора.
- Ошибка: менять строгое неравенство на нестрогое. Как избежать: перепиши условие окончания без сокращений и проверь граничную позицию.
Проверь себя
- Как называется позиция, в которой условие победы уже выполнено?
- Что должно быть верно для позиции
W1? - Какой логический квантор нужен при проверке всех ответов соперника?
- Можно ли включить позицию с победой за один ход в ответ "победа именно вторым ходом"?
Ответы: 1) терминальная; 2) существует ход в терминальную позицию; 3) "для всех"; 4) нет.
Связь с заданиями
Задания 19, 20 и 21 используют одну игровую модель, но спрашивают о разных слоях позиций и разных участниках. Обычно сначала находят немедленный выигрыш, затем гарантированную победу за несколько ходов и позиции, где один игрок выигрывает только при определенном развитии игры. Точная трактовка числа ходов всегда берется из условия.