Ответная стратегия и дерево игры
Дерево ответов, победы на разной глубине и логическое различие между отсутствием гарантии и запретом раннего выигрыша.
Игрок, который ходит вторым, сначала наблюдает выбор соперника и только затем выбирает свой ответ. Выигрышная стратегия должна работать после каждого разрешённого начала. При этом в одной ветви победа может наступить раньше, чем в другой: гарантия победы за два собственных хода задаёт предельный срок, а не одинаковую длину всех партий.
Позиция, партия и дерево
Позиция — состояние игры вместе с известной очередью игрока. Для одной кучи состояние задаётся числом, для двух — парой чисел. Позиция с выполненным условием окончания называется терминальной; продолжений у неё нет. Победитель определяется правилами игры.
Партия показывает одну последовательность действий. Дерево игры показывает возможные продолжения: из каждой ещё не завершённой позиции идут ветви ко всем результатам разрешённого хода. Поэтому одна победная партия не доказывает победу при любой игре соперника: другие ветви могут закончиться иначе.
Стратегия указывает, какое действие выбрать при каждом возможном ответе соперника. Чтобы показать выигрышную стратегию Вани, в дереве сохраняются все ветви Пети, а на каждом ходе Вани достаточно оставить одно выбранное действие, обеспечивающее победу. Остальные ходы Вани могут быть плохими; стратегия не обязана их использовать.
Срок считается по собственным ходам
Петя начинает. Первая пара действий — первый ход Пети и первый ход Вани. Следующая пара — вторые ходы каждого из них. Отдельное действие одного игрока при подсчёте глубины дерева называют полуходом. Поэтому Ваня выигрывает первым собственным ходом после двух полуходов всей партии, а вторым — после четырёх.
Однако четыре действия существуют только в незавершённой ветви. Если Ваня уже победил первым ходом, следующих ходов Пети и Вани нет. Если своим ходом раньше победил Петя, эта ветвь опровергает требуемую гарантию Вани.
Позиции с короткой гарантией
Позицию удобно оценивать для того, кто сейчас ходит. Сначала выделяются продолжающиеся позиции, в которых есть завершающий победный ход. Они обозначаются W_1: победа за один собственный ход.
Далее выделяются позиции, все выходы из которых ещё не терминальны и принадлежат W_1 уже для соперника. Они обозначаются L_1: ходящий вынужден передать сопернику немедленную победу. Наконец, позиции без первого выигрыша, но с возможностью передать L_1, обозначаются W_2: ходящий обеспечивает победу своим вторым ходом.
Теперь можно описать требование к начальной позиции, где ходит Петя. Каждый его первый ход должен оставить Ване либо W_1, либо W_2. В первом случае Ваня заканчивает игру сразу, во втором — выбирает продолжение с победой следующим собственным ходом.
Объединение двух наборов записывается W_1\cup W_2: символ \cup означает «принадлежит хотя бы одному из наборов». Все выходы Пети должны быть продолжающимися позициями из этого объединения. Терминальный результат его хода сюда не входит: Петя уже выиграл.
«Не гарантирует первым» и «никогда не выигрывает первым»
Чтобы Ваня гарантировал победу первым ходом, каждый первый ход Пети должен передавать ему W_1. Чтобы такой гарантии не было, достаточно хотя бы одного выхода Пети вне W_1. Не требуется, чтобы вне этого набора находились все выходы.
| Требование | Условие на выходы Пети |
|---|---|
| Ваня побеждает не позднее второго | Все выходы — в W_1\cup W_2, ни один не заканчивает игру победой Пети |
| Ваня не гарантирует первый выигрыш | Хотя бы один выход — вне W_1 |
Вместе условия означают, что хотя бы один выход относится именно к W_2, а остальные могут быть как в W_1, так и в W_2. Начальную позицию с этими свойствами обозначают L_2: ходящий не может избежать победы соперника за два собственных хода, но способен избежать его немедленной победы.
Выражения «для каждого» и «существует» называют кванторами. Для стратегии здесь порядок следующий: для каждого первого хода Пети есть ответ Вани; если он ещё не закончил игру, для каждого второго хода Пети есть завершающий второй ход Вани. При программной проверке всем вариантам соответствует all, существованию подходящего — any. Завершённая ветвь не передаётся на следующий уровень проверки.
Малая иллюстрация: короткая и длинные ветви
В задаче с разными сроками победы ↗ действуют правила уменьшения кучи ↗: начало S\ge11; вычитание трёх, вычитание пяти или деление на четыре с округлением вниз; победа при десяти камнях или меньше.
При начале 52 Петя может оставить 49, 47 или 13. Из 13 Ваня сразу вычитает три и побеждает. Из 49 он оставляет 46, из 47 — 44. Любой ответ Пети из 46 или 44 даёт от 11 до 43 камней, а из этого диапазона Ваня завершает игру делением на четыре. Поэтому первые две ветви требуют его второго хода, третья — только первого.
Гарантию первого хода опровергает ветвь через 49: разрешённые результаты Вани — 46, 44 и 12, ни один не достигает порога. Это проверка всех его возможностей в одной неудобной позиции. Намеренный плохой ход Вани из 13 ничего подобного не доказал бы: возможность немедленно победить там сохраняется.
Почему раннюю победную ветвь не нужно продлевать до второго хода? Какой контрпример действительно исключает гарантию первого выигрыша? Полное дерево ответов и доказательство минимума приведены в материале «Ответная стратегия Вани».