Задание 19-21 ЕГЭ по информатике. Теория игр

Пример простой игры (спички)

Сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Первый ход за первым игроком. Рассматриваются два варианта первого хода: взять 1 спичку (останется 4) или взять 2 спички (останется 3); варианты изображаются на двоичном «дереве игры» (если из позиции три хода — дерево троичное).

Если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; если после первого хода осталось 3, второй выигрывает сразу, взяв 2 и оставив 1.

Если осталось 3 или 2, то в обоих случаях первый игрок выигрывает своим следующим ходом.

Анализ дерева игры и выводы

• Дерево игры показывает все возможные варианты от начальной позиции. В каждой позиции — набор допустимых ходов (ветви).
• Отвечаем на вопросы: (1) может ли первый выигрывать независимо от второго? (2) может ли второй выигрывать независимо от первого? В этом примере ответ: первый имеет выигрышную стратегию (взять 1 спичку первым ходом), второй — нет, если первый не ошибается.
• Полный перебор работает лишь для очень простых игр; у сложных (например, шахматы) дерево разветвляется слишком сильно.

Термины и правило классификации позиций

• Выигрышная позиция — игрок, делающий ход, может гарантированно выиграть при любой игре соперника (есть выигрышная стратегия). Проигрышная позиция — при правильной игре соперника текущий игрок проиграет.
• Стратегия — алгоритм выбора хода, переводящий игру в проигрышную для соперника позицию.
• Критерий по ходам: позиция, из которой хотя бы один ход ведёт в проигрышную — выигрышная; позиция, из которой все ходы ведут в выигрышные — проигрышная.

Оценки ходов и «матрица стратегий» (одна куча)

Для задач с одной кучей удобно строить таблицу-оценку позиции S: положительное число N — выигрыш за N ходов; отрицательное −N — проигрыш за N ходов (при правильной игре оппонента).

При S ≥ 15 первый игрок выигрывает одним ходом, удвоив количество камней: это позиции с оценкой +1.

Из S=14 все ходы (в 15 и 28) ведут в позиции с оценкой +1, значит S=14 имеет оценку −1 (проигрыш за 1 ход).

Далее: если из S есть ход в позицию с оценкой −1, то S получает +2 (гарантированный выигрыш за 2 хода) — это S=13 и S=7.

Затем смотрим позиции, из которых все ходы ведут в +1 или +2 — единственная такая S=12, у неё оценка −2.

«Матрица стратегий» для двух куч

При двух кучах (K;S) строится двумерная «матрица». Выделяются ячейки, где за 1 ход можно достичь целевого порога (выигрышные за один). Анализ дальнейших слоёв (±2 и т.д.) проводится по тому же правилу: из ячейки, откуда есть ход в «−» слой, — «+»; где все ходы ведут в «+» — «−».

Программная реализация и таблицы

Далее приведён рекурсивный расчёт оценки с мемоизацией для одной кучи, а также подход через LibreOffice/Excel для двух куч: сначала помечают клетки выигрыша за 1 ход формулой максимума после лучшего удвоения, затем по условному форматированию раскрашивают, и пошагово отмечают слои (−1, +2, −2, …). Формула для «один ход» при двух кучах: в ячейке B2 =МАКС(2*$A2+B$1; $A2+2*B$1) и заполнение по таблице, затем проверка «≥ 77».

Примеры решений заданий

Задача 1 (одна куча). Ходы: «+1» или «×2». Финиш — S ≥ 29, старт 1 ≤ S ≤ 28

Формулировка: Петя и Ваня по очереди добавляют в одну кучу либо 1 камень, либо удваивают количество камней. Побеждает тот, кто первым получит кучу с ≥29 камней. Стартовое S в диапазоне 1…28. Требуется ответить на подзадачи заданий 19–21.

Матрица и ключевые оценки

• Все S ≥ 15 — немедленный выигрыш (оценка +1) удвоением.
• S=14 — все ходы ведут в +1 ⇒ оценка −1.
• S=13 и S=7 — есть ход в −1 ⇒ оценка +2.
• S=12 — все ходы ведут в +1 или +2 ⇒ оценка −2.

Решения

• Задание 19. А) S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня выиграет первым ходом: 14 (оценка −1). Б) Минимальное S, когда Ваня выиграл своим первым ходом после неудачного хода Пети: 8 (Петя ошибся, удвоив до 16 — позиция «+1» для Вани).
• Задание 20. Два значения S, где у Пети есть стратегия выигрыша вторым ходом при любой игре Вани, и при этом не выигрывает за один: 7 и 13 (оценка +2).
• Задание 21. S, при котором у Вани есть стратегия выигрыша первым или вторым ходом при любой игре Пети, но нет гарантии выиграть первым ходом: 12 (оценка −2).

from functools import lru_cache

max_stones = 28  # предел, до которого игра продолжается (финиш при > max_stones)

@lru_cache(None)
def game_res(stones, maxstones):
    if stones > maxstones:
        return 0  # игра уже завершена
    else:
        next_scores = [
            game_res(stones + 1, maxstones),
            game_res(stones * 2, maxstones),
        ]
        negative = [c for c in next_scores if c <= 0]
        if negative:
            return -max(negative) + 1  # выигрышный слой
        else:
            return -max(next_scores)   # проигрышный слой

results = [game_res(S, max_stones) for S in range(1, max_stones + 1)]
print(results)                         # «матрица» по S=1..28
print('19A =', results.index(-1) + 1)  # 14
# 19B вычисляется отдельной проверкой «ошибочного» хода Пети (пример: 8 → 16)
# 20:
i1 = results.index(2)
i2 = results.index(2, i1 + 1)
print('20 =', i1 + 1, i2 + 1)          # 7 13
print('21 =', results.index(-2) + 1)   # 12

Задача 2 (две кучи). Ходы: «+1 в одну из куч» или «×2 одну из куч». Финиш — сумма ≥ 77. Старт (7; S), 1 ≤ S ≤ 69

Формулировка: Две кучи, игрок за ход либо прибавляет 1 камень в любую одну из куч, либо удваивает любую одну из куч. Игра заканчивается, когда сумма камней становится ≥ 77. Начальная позиция (7; S). Требуется решить подзадачи 19–21.

Подход через таблицу (из презентации)

1. Строим таблицу: по вертикали — первая куча (начиная с 7), по горизонтали — вторая куча (с 1). Для каждой пары считаем максимум камней, достижимый за один ход: =МАКС(2*$A2+B$1; $A2+2*B$1). Помечаем условным форматированием ячейки, где максимум ≥ 77 (выигрыш за 1 ход). :contentReference[oaicite:21]{index=21}
2. Далее отмечаем слои «−1», «+2», «−2» и т.д. по правилу: из ячейки, откуда есть ход в «−», — «+»; где все ходы ведут в «+» — «−». Нас интересует строка для первой кучи = 7 (то есть позиции (7; S)). :contentReference[oaicite:22]{index=22}

Решения

• Задание 19. Минимальное S, при котором «Ваня выиграл своим первым ходом после неудачного первого хода Пети»: 18. Обоснование: если Петя удваивает вторую кучу, получается (7; 2S). Ваня выигрывает за один, когда 2S ≥ 35 ⇒ S ≥ 18. Альтернатива — Петя удваивает первую: (14; S), Ваня выиграет за один при S ≥ 32; минимально подходит 18. :contentReference[oaicite:23]{index=23}
• Задание 20. Два значения S, где у Пети есть выигрышная стратегия вторым ходом, при том что за один ход он не выигрывает: 31 и 34. Они соответствуют зелёным ячейкам на строке (7; S) — «+2»-позициям. :contentReference[oaicite:24]{index=24}
• Задание 21. Минимальное S, при котором у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети, но нет гарантии выиграть первым ходом: 30 (на строке первой кучи = 7 это «−2»-позиция; жёлтые ячейки). :contentReference[oaicite:25]{index=25}

Программные наброски (из презентации)

Для двух куч рекурсивная функция получает два аргумента (камни в первой и второй куче), а «матрица» кэшируется в словаре; переходы — четыре: (K+1; S), (K; S+1), (2K; S), (K; 2S). Игра завершается, когда K+S ≥ 77.

Короткий чек-лист по задачам 19–21

• Сначала отмечаем «выигрыш за один ход» (слой +1), затем распространяем слои −1, +2, −2, … по правилу переходов. :contentReference[oaicite:31]{index=31}
• Вопросы формулируются по слоям: «не может выиграть за один, но…» ⇒ ищем −1; «выигрыш вторым ходом при любой игре» ⇒ +2; «у второго есть выигрыш 1–2 ходом, но не 1-м гарантированно» ⇒ −2. :contentReference[oaicite:32]{index=32}
• Для двух куч обязательно учитывать любую из четырёх операций на ход и суммарный порог окончания. :contentReference[oaicite:33]{index=33}