Игровые позиции и победа за ход
Позиция, ход и стратегия: почему возможность одной победной партии отличается от гарантии против любого ответа.
В игре результат зависит не только от выбранного действия, но и от ответа соперника. Поэтому утверждение «можно получить победную последовательность» слабее утверждения «можно обеспечить победу при любой игре противника». Это различие удобно описывать через позиции и допустимые переходы между ними.
Позиция и разрешённый ход
Позиция — состояние, по которому можно определить доступные действия и проверить окончание игры. Для одной кучи это число камней, для двух — пара чисел. Очередь хода тоже должна быть известна: одно и то же состояние может быть выгодно Пете, когда ходит он, и Ване, когда ходит Ваня.
В задачах с одинаковыми правилами для обоих игроков удобно оценивать позицию относительно того, кто сейчас ходит. После перехода очередь передаётся сопернику, поэтому вместе с числом меняется и точка зрения.
Разрешённый, или легальный, ход — одно действие, допускаемое правилами. Например, при прибавлении четырёх или утроении одной из двух куч из (a,b) возможны четыре результата: (a+4,b), (3a,b), (a,b+4), (a,3b). Одновременное утроение обеих куч в этот список не входит.
Сумма не всегда заменяет пару. Например, у (11,16) и (12,15) одна сумма 27, но утроение большей кучи даёт разные суммы: 59 и 57. Если разрешённые действия зависят от распределения камней, это распределение сохраняется в позиции.
Окончание игры и немедленная победа
Позиция, в которой выполнено условие окончания, называется терминальной. Продолжений у неё нет. Кто победил, определяется правилами: в рассматриваемых пороговых играх это игрок, который своим ходом достиг порога.
До терминальной позиции остаётся один ход, если существует разрешённое действие, сразу заканчивающее игру победой ходящего. Такую ещё продолжающуюся позицию будем называть позицией с победой за один ход и обозначать W_1. Буква служит меткой, индекс указывает число собственных ходов.
В игре с делением кучи на четыре ↗ начальное число не меньше 11; разрешены вычитание трёх, вычитание пяти и деление на четыре с округлением вниз. Победа — при десяти камнях или меньше. Деление заканчивает игру при \lfloor s/4\rfloor\le10, то есть для целого s\le43. Вычитания не расширяют эту границу. Поэтому позиции W_1 здесь — целые числа от 11 до 43.
Число 10 в этот список не входит: игра уже окончена. Число 43 входит: ход ещё нужен, но 43\to10 приносит победу. Разделение этих случаев предотвращает лишний ход после завершения партии.
Одна партия и стратегия
Партия — одна последовательность реально сделанных ходов от начала до окончания. Стратегия задаёт, какой ход выбрать в каждой позиции, которая может возникнуть при игре соперника. Выигрышная стратегия обеспечивает победу при всех его разрешённых выборах. Это не обязательно одна заранее записанная цепочка действий.
В игре с неудачным ходом в двух кучах ↗ начало имеет вид (11,S), где 1\le S\le142. Ход добавляет четыре в одну кучу или утраивает её; победа наступает при сумме не меньше 154. При S=16 возможна партия (11,16)\to(11,48)\to(11,144). После первого хода сумма 59, после второго — 155. Она доказывает возможность победы Вани после неудачного действия Пети. О других первых ходах Пети эта цепочка ничего не утверждает.
«Существует» и «для каждого»
Выражение «существует ход» требует найти хотя бы один подходящий вариант. Выражение «для каждого хода» требует проверить все разрешённые варианты. В логике такие указания на охват вариантов называют кванторами. Их обозначают соответственно \exists и \forall.
| Формулировка | Что доказывается |
|---|---|
| Ваня победил после неудачного хода Пети | Есть незавершающий ход Пети, после которого есть победный ответ Вани |
| Ваня выигрывает после любого хода Пети | Каждый ход Пети оставляет продолжающуюся игру и допускает победный ответ Вани |
Во втором случае ответ выбирается после наблюдения хода Пети. Например, в игре с вычитанием трёх, пяти и делением на четыре из 44 получаются 41, 39 или 11. Ваня может разделить 41 и 39, а из 11 вычесть три. Все ответы дают не более десяти камней. Одна и та же операция для всех ветвей не требуется; требуется существование завершающего действия в каждой ветви.
Те же различия применимы к другим играм, но набор ходов, момент остановки и победитель каждый раз берутся из условия. Если победа зависит от точного попадания в интервал или от перелёта через границу, одного сравнения с порогом уже недостаточно.
Почему для победы после ошибки хватает одной партии, а для гарантии нужны все первые ходы соперника? Как по позициям с немедленной победой найти минимальное начальное число? Эти вопросы разобраны в материале «Первый ход: возможность и гарантированная победа».