Задание 20: выигрыш первого игрока за два хода

Усложняем анализ: теперь смотрим на два хода вперёд и ищем позиции, где первый игрок гарантированно побеждает своим вторым ходом.

Задание 20 требует найти значения S, при которых у первого игрока есть стратегия выиграть не позднее своего второго хода, но не первым.

Что проверяет задание 20

Задание 20 — повышенный уровень, 1 балл. Формулировка: «Найдите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как походит Ваня». Глубина анализа — два хода первого игрока, между ними ход второго.

Теория: «выигрыш за не более чем k ходов»

Введём функцию win_le(s, k) — «игрок, который ходит из s, выигрывает не более чем за k своих ходов при оптимальной защите соперника». Рекурсия:

Если из s можно сразу попасть в терминал — выигрыш (за 1 ход), значит при k ≥ 1 True.
Иначе: ищем такой наш ход m, что при ЛЮБОМ ответе соперника om мы дальше выигрываем за ≤ k−1. То есть win_le(om, k-1) для всех ответов om.

Это естественное обобщение: глубина k = 1 — это «выигрыш первым ходом», k = 2 — «не позднее второго хода» и т. д. Между нашими ходами соперник ходит и сопротивляется, поэтому по его ходам берём all, а по нашим — any.

Метод решения

Реализуйте win_le(s, k).
Задание 20: оставьте S, где not win_in_1(S) (Петя не выигрывает сразу) и win_le(S, 2) (но выигрывает за ≤ 2 хода).
Среди подходящих возьмите столько значений, сколько просят (обычно два наименьших).

Решение на Python

from functools import lru_cache

LIMIT = 49

def moves(s):
    return [s + 1, s * 2]

def win_in_1(s):
    return any(m >= LIMIT for m in moves(s))

@lru_cache(maxsize=None)
def win_le(s, k):
    "Ходящий из s выигрывает не более чем за k своих ходов."
    if s >= LIMIT:
        return False           # игра кончилась, ходить нельзя
    if k == 0:
        return False           # ходов не осталось, а не выиграл
    for m in moves(s):
        if m >= LIMIT:
            return True        # выиграли этим ходом
        # при ЛЮБОМ ответе соперника мы дальше выигрываем за <= k-1
        if all(win_le(om, k - 1) for om in moves(m) if om < LIMIT) \
           and all(om < LIMIT for om in moves(m)):
            return True
    return False

answer = [s for s in range(1, LIMIT)
          if (not win_in_1(s)) and win_le(s, 2)]
print("Подходящие S (задание 20):", answer)
print("Ответ — два наименьших:", answer[:2])

Вывод:

Подходящие S (задание 20): [12, 23]
Ответ — два наименьших: [12, 23]

Получили S ∈ {12, 23}. Разберём S = 23: Петя сам не выигрывает (24 и 46 меньше 49). Петя ходит в 24 — а 24 мы знаем как проигрышную для того, кто ходит (теперь ходит Ваня!), значит дальше Петя добивает за свой второй ход при любой игре Вани. Стратегия Пети: пойти в 24 и поставить Ваню в ту самую ловушку из задания 19.

Почему важна защита соперника

Слово «независимо от того, как походит Ваня» — это all по ходам Вани. Нельзя рассчитывать, что Ваня ошибётся: стратегия обязана работать при оптимальной игре соперника. Поэтому в win_le по ходам соперника стоит all, а по своим ходам — any (нам достаточно одного выигрывающего хода).

Типичные ошибки

Берут позиции, где Петя выигрывает первым ходом. Задание 20 требует именно второй ход, поэтому not win_in_1(S) обязательно.
Меняют местами any/all. По своим ходам — any (хватит одного), по ходам соперника — all (должно работать против любого ответа).
Берут не два значения. Если просят два — приведите оба; одно — потеря балла.
Не учитывают терминальные ходы соперника. Если у соперника есть ход в терминал — он выигрывает, наш ход плох.

Итог

Задание 20 = «не выигрывает за 1 ход, но выигрывает за ≤ 2 хода»: not win_in_1(S) and win_le(S, 2).
В win_le по своим ходам — any, по ответам соперника — all.
Часто стратегия Пети — загнать Ваню в проигрышную позицию из задания 19.