Задание 21: кто выигрывает и дерево всех партий

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

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

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

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

Метод: сначала кодом находим S, потом рисуем дерево

Используем те же функции win_in_1 и win_le. Ваня (второй) выигрывает за ≤ 2 хода, если при ЛЮБОМ ходе Пети получившаяся позиция выигрышна для Вани за ≤ 2 хода. А «у Пети нет стратегии за два хода» — это not win_le(S, 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):
    if s >= LIMIT or k == 0:
        return False
    for m in moves(s):
        if m >= LIMIT:
            return True
        if all(win_le(om, k - 1) for om in moves(m)):
            return True
    return False

def vanya_win_le(s, k):
    # Ваня (второй) выигрывает за <= k: Петя не выигрывает сразу,
    # и при любом ходе Пети Ваня дальше выигрывает за <= k
    if win_in_1(s):
        return False
    return all(win_le(m, k) for m in moves(s))

answer = [s for s in range(1, LIMIT)
          if (not win_le(s, 2)) and vanya_win_le(s, 2)]
print("Подходящие S (задание 21):", answer)

Вывод:

Подходящие S (задание 21): [22, 24]

Подходят S = 22 и S = 24: при них у Пети нет стратегии выиграть за два хода, а Ваня выигрывает не позднее второго хода.

Построение дерева партий (для S = 22)

Дерево рисуют так: в узлах — число камней, на рёбрах — кто ходит. Раскрываем ВСЕ ходы Пети (он играет как угодно) и ходы Вани по его выигрышной стратегии. Покажем код, который печатает дерево с отступами для S = 22.

LIMIT = 49

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

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

def best_vanya_move(s):
    # Ваня выбирает ход: сначала выигрыш сразу, иначе — в проигрышную для Пети
    for m in moves(s):
        if m >= LIMIT:
            return m
    for m in moves(s):
        if all(win_in_1(x) for x in moves(m)):  # Петя в ловушке
            return m
    return moves(s)[0]

def show(s, player, depth):
    pad = "  " * depth
    if s >= LIMIT:
        print(f"{pad}{s}  (партия окончена)")
        return
    print(f"{pad}{s}  -> ходит {player}")
    if player == "Петя":
        for m in moves(s):           # Петя ходит как угодно — все ветки
            show(m, "Ваня", depth + 1)
    else:
        m = best_vanya_move(s)       # Ваня — по своей стратегии (одна ветка)
        show(m, "Петя", depth + 1)

show(22, "Петя", 0)

Вывод:

22  -> ходит Петя
  23  -> ходит Ваня
    24  -> ходит Петя
      25  -> ходит Ваня
        50  (партия окончена)
      48  -> ходит Ваня
        49  (партия окончена)
  44  -> ходит Ваня
    88  (партия окончена)

Читаем дерево: Петя из 22 может пойти в 23 или 44. Если в 44 — Ваня сразу удваивает до 88 ≥ 49 и выигрывает. Если в 23 — Ваня идёт в 24 (ловушка из задания 19!), и какой бы ход Петя ни сделал (25 или 48), Ваня добивает (50 или 49). Во всех ветках побеждает Ваня — это и есть его выигрышная стратегия.

Как оформлять на экзамене

• В узлах пишите число камней, на рёбрах — кто ходит и какой ход (+1 или ×2).
• Ветви Пети раскрывайте ПОЛНОСТЬЮ (все его ходы), ветви Вани — только по его стратегии (один ход).
• Каждый лист должен заканчиваться победой Вани (камней ≥ порога после хода Вани).

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

• Раскрывают не все ходы проигрывающего. Для игрока без стратегии (Пети) надо показать ВСЕ его ходы — иначе дерево неполное.
• Раскрывают лишние ходы выигрывающего. Для Вани показывают только выигрывающий ход, не все.
• Лист не заканчивается победой нужного игрока. Проверяйте, что последний ход делает именно Ваня.
• Путают S = 22 и S = 24. Оба подходят, но деревья разные; стройте для того, что указали в ответе.

Итог

• Задание 21 = найти S и построить дерево всех партий при выигрышной стратегии.
• Ходы проигрывающего раскрывают полностью, ходы выигрывающего — только по стратегии.
• Код находит S и печатает дерево с отступами — переносите его на бумагу узлами и рёбрами.