Выигрышные и проигрышные позиции
Игры с полной информацией и ключевая идея теории игр: разметка позиций на выигрышные и проигрышные.
Выигрышная позиция — та, из которой есть ход в проигрышную (для соперника); проигрышная — та, из которой все ходы ведут в выигрышные.
Зачем это в олимпиадах
Игровые задачи — отдельный любимый жанр олимпиад: «двое по очереди берут камни, кто не может ходить — проиграл, кто выигрывает при правильной игре». За кажущейся простотой стоит стройная теория. Базовый навык — научиться размечать все позиции на выигрышные (W) и проигрышные (L) и понимать, почему такая разметка определяет исход. Это фундамент для функции Шпрага–Гранди и нима в следующих уроках. Освоив разметку, вы будете решать целый класс задач, не угадывая, а доказывая.
Какие игры мы рассматриваем
Мы изучаем беспристрастные игры с полной информацией: оба игрока видят всю позицию (нет скрытых карт), нет случайности (нет кубиков), доступные ходы зависят только от позиции, а не от того, чей ход (беспристрастность), игра конечна и кто не может сделать ход — проигрывает (нормальное соглашение). Примеры: «отнимание камней», ним, многие задачи про передвижение фишек. Шахматы и крестики-нолики сюда не входят (там ходы зависят от цвета — игры пристрастные).
Идея разметки W/L «на пальцах»
Рассуждаем с конца. Терминальная позиция, где ходить некуда, — проигрышная для того, чей ход (он уже проиграл). Дальше по индукции: позиция выигрышная, если из неё есть хотя бы один ход в проигрышную (отдаём сопернику плохую позицию); позиция проигрышная, если все ходы ведут только в выигрышные (что ни сделай — отдашь сопернику победу). Эти два правила однозначно размечают все позиции снизу вверх.
# Игра: есть n камней, за ход берут 1, 2 или 3. Кто не может ходить — проиграл.
def compute_states(n, moves):
win = [False] * (n + 1) # win[k] = выигрышна ли позиция с k камнями
for k in range(1, n + 1):
# позиция выигрышна, если есть ход в проигрышную
win[k] = any(k - m >= 0 and not win[k - m] for m in moves)
return win
win = compute_states(12, (1, 2, 3))
for k in range(13):
print(k, "W" if win[k] else "L")Вывод:
0 L 1 W 2 W 3 W 4 L 5 W 6 W 7 W 8 L 9 W 10 W 11 W 12 L
Проигрышные позиции — кратные 4 (0, 4, 8, 12). Это не случайность: при ходах 1–3 первый игрок всегда может «дополнить» ход соперника до 4 и удерживать остаток кратным 4. Из любого 4k что ни возьми (1, 2 или 3), соперник возьмёт дополнение до 4. Так разметка вскрыла закономерность.
Почему разметка определяет исход
Утверждение: если позиция помечена W, то у текущего игрока есть стратегия победы; если L — проигрывает при любой игре (при оптимальной игре соперника). Доказательство — индукция по «глубине» игры. В W-позиции игрок ходит в L-позицию (она существует по определению W), и теперь уже соперник в проигрышной позиции — по предположению индукции он проиграет. В L-позиции любой ход ведёт в W-позицию, отдавая сопернику выигрышную стратегию. База — терминальная L-позиция, где текущий игрок уже проиграл. Индукция замыкается.
Разбор: игра с произвольным набором ходов
Разметка не требует угадывать формулу — она механически работает для любого множества разрешённых ходов. Возьмём ходы {2, 3} (брать ровно 2 или 3 камня) и посмотрим, где проигрышные позиции.
def compute_states(n, moves):
win = [False] * (n + 1)
for k in range(1, n + 1):
win[k] = any(k - m >= 0 and not win[k - m] for m in moves)
return win
win = compute_states(15, (2, 3))
losing = [k for k in range(16) if not win[k]]
print("Проигрышные позиции:", losing)Вывод:
Проигрышные позиции: [0, 1, 5, 6, 10, 11, 15]
Закономерность сложнее (период 5: {0,1} по модулю 5), и угадать её сходу непросто — но разметка нашла её автоматически за O(n·|moves|). Это и ценно: когда формула неочевидна, всегда можно построить таблицу W/L перебором и либо использовать её напрямую, либо разглядеть период.
Разбор олимпиадной задачи: игра на двух кучах
Усложним: две кучи, за ход берут любое число камней из одной кучи или поровну из обеих. Кто не может ходить — проиграл. Это игра Витхоффа. Размечать вручную тяжело, но перебор справляется. Построим таблицу W/L для всех позиций (a, b) и поищем закономерность в проигрышных.
def wythoff(N):
win = [[False] * (N + 1) for _ in range(N + 1)]
for a in range(N + 1):
for b in range(N + 1):
# перебираем все ходы из (a, b)
moves = []
for k in range(1, a + 1):
moves.append((a - k, b)) # из первой кучи
for k in range(1, b + 1):
moves.append((a, b - k)) # из второй кучи
for k in range(1, min(a, b) + 1):
moves.append((a - k, b - k)) # поровну из обеих
win[a][b] = any(not win[na][nb] for na, nb in moves)
return win
win = wythoff(12)
losing = [(a, b) for a in range(13) for b in range(a, 13) if not win[a][b]]
print(losing)Вывод:
[(0, 0), (1, 2), (3, 5), (4, 7), (6, 10)]
Проигрышные позиции — (0,0), (1,2), (3,5), (4,7), (6,10), …. Это знаменитые пары Витхоффа, связанные с золотым сечением: aᴪ = ⌊k·φ⌋, bᴪ = ⌊k·φ2⌋. Сходу такую формулу не угадать — но разметка перебором нашла позиции автоматически, и уже по таблице можно либо вывести закономерность, либо использовать её напрямую при малых ограничениях. В этом и сила метода: он не требует озарения, лишь аккуратной индукции по позициям.
Подводные камни
- Соглашение об окончании. Мы используем «нормальное»: кто не может ходить — проиграл. В «мизерном» варианте (кто не может — выиграл) разметка другая. Читайте условие.
- Беспристрастность. Теория W/L и Гранди — для игр, где ходы не зависят от игрока. Для шахмат и т.п. она неприменима.
- Размер таблицы. Разметка занимает O(n) памяти; для огромных
nищите период или формулу. - Граница ходов. Не забывайте проверку
k - m >= 0, иначе уйдёте в отрицательные индексы.
Итог
- Изучаем беспристрастные игры с полной информацией без случайности.
- Терминальная позиция (нет ходов) — проигрышная.
- W: есть ход в L; L: все ходы ведут в W — это размечает все позиции по индукции.
- Разметка перебором находит исход и часто вскрывает период проигрышных позиций.
