Игровые стратегии (КЕГЭ 19-21). Обзор заданий

Два игрока( А и Б) играют в "камни" (или что-то похожее) по "типовым" правилам

  .  Ходы по очереди.
Правила можно разбить на блоки

1. Ходы в игре строго по очереди, первым всегда ходит игрок А. 
2. Игра гарантированно заканчивается (или исследуется фиксированное число ходов)
3. Для любого стартового хода гарантировано, что один из игроков  имеет выигрышную стратегию (ВС) 
   (Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.)
4. Объекты игры:
   a) - одна куча
   b) -  две кучи (точки на плоскости)
   c) -  набор чисел, карточек и т.п.
5. Правила ходов:
   a) набор команд для изменение состояния куч одинаковых для всех "тактов игры"
   b) "правило горячего камня" - команды разбиты на несколько групп, запрещено использовать группу,
        задействованную на последнем ходе противника (может быть и своем)
   c) выбор коман зависит от состояния "позиции"
6. Условия окончания:
   a) - количество камней "вышло за пределы нормы"
   b) - последнее значение обладает "нужным свойством"
   c) - нет возможности сделать очередной ход
7. Определение победителя:
   a) - кто сделал последний ход, тот и победил
   b) - кто сделал последний ход, тот проиграл ("поддавки")
   c)-  анализ состояния "позиции" последнего хода: сделавший последний ход может быть
      признан как победителем, так и проигравшим

Приведем стандартные примеры (с условной классификацией)
Пример 1 (ЕГКР апрелеь 2026 вариант 2 )

Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
- добавить в кучу 2 камень;
- добавить в кучу 5 камней;
- увеличить количество камней в куче в 2 раза.
 Игра завершается, когда количество камней в куче становится не менее 121.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 121 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 120.

Это стандартный вариант, который можно классифировать как 4a.5a.6a.7a

Пример 2 ((Демо-2025)

Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней.
Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
- убрать из кучи два камня
- убрать из кучи пять камней
- уменьшить количество камней в куче в три раза
(количество камней, полученное при делении, округляется до меньшего).
Игра завершается, когда количество камней в куче становится не более 19.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней.
В начальный момент в куче было S камней, S ≥ 20.

Отличается от примера 1 только тем, что количество камней уменьшается.
Сложность в том, что количество стартовых позиций нужно ограничить.
Это можно следать, если учесть вопросы задачи (в КЕГЭ все задания ограничены)
Поэтому последнее условие можно/нужно модифицировать 
В начальный момент в куче было S камней, 1000 > S  ≥  20.
  Это вариант классифировать как 4a.5a_.6a.7a (5a_ обозначает уменьшение кол-ва камней)

Пример 3 (авторская, посложнее чем в КЕГЭ)

Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
   - добавить в кучу один
   - или три камня,
   - либо увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда количество камней в куче становится простым числом.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, количество камней в которой является простым числом.
В начальный момент в куче было S камней; 1 ≤ S ≤ 100, S не является простым числом.
Задание нестандартное, поскольку 
- стартовое множество "дырявое" (1, 4, 6, 9, 10,12, ...96,98,99,100)
- финальные позиции явно не указаны (2, 3, 5, 7, 11,... 97, 101, 103, ...
вообще-то игра может быть бесконечной (оба умножают), но если требовать, что 
каждый игрок стремиться к победе, то игра гарантировано завершиться  - это можно легко проверить)
Классифицировать игру можно как 4a.5a.6b.7a

Пример 4 (авторская, две кучи, условие окончания)

Два игрока, Паша и Витя, играют в следующую игру.
Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша.
За один ход игрок может
 - добавить в одну из куч (по своему выбору) один камень
-  или увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 60.
           Если при этом в куче оказалось не более 79 камней, то победителем считается игрок, сделавший последний ход.
          В противном случае победителем становится его противник, при этом считается, что противник сделал ход.
В начальный момент в первой куче было восемь камней, во второй куче – S камней; 1 ≤ S ≤ 51.

Особенность - анализ последнего хода.
Классифицируем как 4b.5a.6b.7a

Пример 5 (горячий камень)

Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
- добавить в кучу один камень,
- добавить два камня
- или увеличить количество камней в куче в три раза.
При этом нельзя повторять ход, который только что сделал второй игрок.
Игра завершается, когда количество камней в куче становится не менее 62.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 62 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 61.

Особенность - есть правило "горячего камня"
Классифицируем как 4a.5b.6a.7a

Пока остановимся на этих примерах.
Попробуйте придумать своим правила игры (сложные или "гробовые")
для которых Вы будете решать задачу.
Определимся, что означает решить задачу в "общем виде"?
Решение Игры, в наших условиях, это определение (для заданной стартовой позиции)
- игрока, имеющего  ВС (выигрышную стратегию)
- некоторых характеристик ВС (максимальной и минимальной длины, возможных точек финиша и т.п.)
Задача решается построением двудольного графа. 
Для построения такого графа можно использовать принципы bfs или dfs (или нечто среднее)
Рассмотрим основные идеи методов и способов их реализации

Метод "раскраски"  или bfs
Основая идея заключается в том,  что будем строить "обратный двудольный граф".
То есть "финальные позиции" будем считать истоком, а "стартовые позиции" стоком.
Это возможно, если нет "условий на исследование траекторий в глубину" для определения следующего хода
(ограничений на количество выполнени команд, запрет цикла  и т.п.)
В качестве "финальных позиций" можно добавить использование  позиций "W" и "L"
Этапы работы 
-"нечетные такты"-  ищем "выигрышные позиции/кружки": просматриваем множество "стартовых позиций" и отбираем/раскрашиваем "кружком" те,
   из которых можно выиграть или перейти в "проигрышные позиции"
- "четные такты" - выявляем "проигрышные позиции/прямоугольники": просматриваем множество "стартовых позиций" и находим те,
из которых все допустимые ходы ведут в "выигрышные позиции/кружки"
Принцип можно сформулировать "метод кластеризации"

• изначально есть множество "прямоугольников"  (точно не пустое) и множество "кружков" (может быть пустым"
• позиция есть "кружок", если существует ход в "прямоугольник"
• позиция есть "прямоугольник" если все ходы ведут в" кружок"

Данный способ подойдет для всех примеров выше.

Метод dfs
Основая идея заключается в том,  что будем перебирать все допустимые траектории и
их анализом (по длине) опредялять "раскраску" стартовых позиций
В некоторых условияъ возможно только применения подхода dfs
Данный способ также подойдет для всех примеров выше,
но может быть зависим от параметров (глубина рекурсии).

Далее рассмотрим реализацию каждого метода и применения его для получения "общего решения"
Возможно, для решения конкретных заданий КЕГЭ, предложенные подходы будут несколько избыточны