Стратегия победы вторым ходом
Обратный анализ игры: от немедленной победы к позиции, из которой первый ход обеспечивает успех после любого ответа.
Для победы вторым ходом важно не только приблизиться к окончанию игры. Первый ход должен поставить соперника в положение, где любой его ответ даст возможность закончить игру. Поэтому рассуждение удобно строить от конца: сначала найти немедленные победы, затем позиции перед ними и лишь после этого выбирать начальный ход.
Позиция оценивается перед ходом
Позиция задаёт состояние игры: например, количество камней в одной куче или пару количеств в двух кучах. Также должна быть известна очередь игрока. В играх с одинаковыми действиями для обоих участников свойства позиции удобно формулировать для того, кто сейчас ходит, без постоянного имени.
Позиция с уже выполненным условием окончания называется терминальной. Из неё игра не продолжается. В рассматриваемых играх победил тот, кто достиг её своим ходом. Стратегия задаёт выбор действия в каждой позиции, которая может возникнуть при ответах соперника; выигрышная стратегия обеспечивает победу при любом его выборе.
Позицию называют выигрышной для ходящего, если он может обеспечить победу. Проигрышная для ходящего позиция, напротив, позволяет сопернику обеспечить победу независимо от сделанного сейчас хода. Слова «выигрышная» и «проигрышная» не закреплены за Петей или Ваней: всё зависит от того, кому досталась очередь.
От завершающего действия к первому ходу
Если из ещё продолжающейся позиции есть завершающий победный ход, это победа за один ход. Такие позиции обозначаются W_1. Для принадлежности этому набору хватает одного удачного действия: остальные могут быть невыгодны.
Следующий слой состоит из позиций, где любой ход оставляет сопернику W_1. При этом ни один ход не завершает игру: каждый результат — продолжающаяся позиция. Ходящий вынужден отдать победу на ближайшем ответе. Этот слой обозначается L_1.
Теперь можно определить победу вторым собственным ходом при невозможности первого. Исходная позиция не должна принадлежать W_1, но из неё должен существовать ход в L_1. Такие позиции обозначаются W_2.
| Набор позиций | Основание |
|---|---|
| W_1 | Есть ход, сразу заканчивающий игру победой |
| L_1 | Каждый ход оставляет сопернику продолжающуюся позицию из W_1 |
| W_2 | Первого выигрыша нет, но есть ход в L_1 |
Все три набора относятся к игре, которая ещё не закончилась. Такая последовательность определения называется обратным анализом: ближайший к победе слой объясняет предыдущий.
Почему чередуются «есть» и «все»
На своём ходе игрок выбирает одно действие; для доказательства стратегии достаточно предъявить удачный выбор. Ход соперника выбрать за него нельзя, поэтому проверяются все его возможности. Эти два вида проверки называют кванторами: \exists — «существует хотя бы один», \forall — «для каждого».
Для Пети, начинающего игру, порядок таков: существует первый ход Пети, для каждого ответа Вани существует завершающий второй ход Пети. Слова идут именно в таком порядке. Последний выбор зависит от ответа Вани; одинаковая операция во всех ветвях не требуется.
При программной проверке «хотя бы один» обычно выражает any, а «все» — all. Поэтому первый выбор соответствует any, ответы противника — all, завершающее действие — снова any. Требование отсутствия первого выигрыша проверяется отдельно: «позиция не в W_1» означает, что ни одно разрешённое действие не заканчивает игру сейчас. Один плохой ход не доказывает этого отсутствия.
Малая иллюстрация: передача невыгодной позиции
В задаче о выборе первого хода ↗ используются правила уменьшения кучи ↗: начало S\ge11, разрешены вычитание трёх, вычитание пяти и деление на четыре с округлением вниз; победа — при десяти камнях или меньше.
Победа за ход возможна из 11–43: деление даёт не больше десяти. Из 44 получаются только 41, 39 и 11, то есть три позиции с немедленной победой следующего игрока. Поэтому 44 принадлежит L_1. Из 47 Петя может вычесть три и передать Ване именно эту позицию:
47\xrightarrow{\text{Петя}}44, затем Ваня получает выбор 41,39,11.
После 41 и 39 Петя делит на четыре и получает 10 или 9; после 11 вычитает три и получает 8. Все ветви заканчиваются его победой. Из самих 47 ни вычитания, ни деление ещё не дают десять или меньше, поэтому первый выигрыш исключён. Этот фрагмент показывает переход W_2\to L_1\to W_1, после которого выполняется завершающий ход.
Собственные ходы и глубина продолжения
Один ход одного игрока при подсчёте глубины дерева часто называют полуходом. Два собственных хода Пети здесь занимают три полухода всей партии: Петя — Ваня — Петя. Если после одного из них условие окончания уже выполнено, оставшиеся действия не выполняются. Поэтому проверка порога предшествует переходу к следующему игроку.
Почему наличие плохого первого хода не опровергает выигрышную стратегию Пети? Как доказать, что выбранное действие выдерживает все ответы Вани? Полный выбор начальных значений и проверка ветвей приведены в материале «Победа Пети вторым ходом».