Статья Автор: Лебедев Дмитрий

Игровая стратегия - решение для экзамена (простое, без рекурсии)_КЕГЭ задания типа 19-21

Этот разбор адресован (в первую очередь) тем, кто умеет решать задания на игровые стратегии без компьютера, имеет представление о методе "раскраски" и хочет понять, как решать задания КЕГЭ на  две (и более) кучи простым и понятным способом.  

В качестве примера рассмотрим задание 2024 года на две кучи. 
Условие задачи
Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежат две кучи камней.
Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
  • добавить в одну из куч (по своему выбору) один камень
  • или увеличить количество камней в куче в три раза.
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 65.

Вопросы к заданию имеют "глубину" в 4 такта (1 ход Пети, 1 ход Вани, 2 ход Пети, 2 ход Вани). 
Имеется описание возможных стартовых позиций -"В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 58"
Такая "простая" постановка задания дает возможность получения "несложного" решения 

 

Пусть St - множество стартовых позицей (точек) - это множество пар вида (i,j), для который i+j  < 65
"Окружением"/"образом" позиции назовем множество точек, в которые можно совершить ход. "Образ" будем обозначать как O(v)
Определим W1 - подмножество ST, состоящее из позиций из которых можно совершить "победный ход", то есть перейти в позицию (i',j'), где i'+j' >= 65.
Нетрудно понять, что:
  • если  \(v \in W_1, \ то\ O(v) \nsubseteq St\) - "окружения" точек из W1 "выходят" из St;
  •  W1 - множество позиций, для которых у Пети есть выигрышная стратегия в один ход.
Несложно написать программу, которая создаст множество St определит множество  W1 и построит St1 = St / W1 (разница множеств).


St1 - множество позиций, остающихся в игре (для разбора) после 1-го такта.
Очевидно, что из позиций множества ST1 нельзя выиграть за 1 ход, то есть выйти за пределы St.
В множестве ST1 могут оказаться точки, "окружение"  которых полность лежит в W1.
Выделим L1 - подмножество таких позиций. \(L_1 = \{ v\ |\ O(v) \subset W_1 \}\)
Нетрудно понять, что для позиций из L1 (и только для них) выигрышная стратегия в один ход есть у Вани  (из L1 принудительно в W1, а из W1 есть "победный" ход).
Дополним программу подпрограммой, определяющей L1 на основании ST1 и W1 и определим множество позиций оставшихся в игре ST2  =  ST1 /  L1 (разница множеств)
 


ST2  - это позиции, остающиеся в игре. Для некоторый позиций из ST2 можно будет перейти в L1.
Выделим такие позиции в множество \(W_2\ = \{v \in St2\ |\ O(v\ ) \bigcap \neq\ \varnothing\}\)
Нетрудно понять, что для позиций из W2 будет существовать
выигрышная стратегия в два хода для Пети:
  • Петя ходит в L1
  • из L1 Ваня вынужден ходить в W1
  • Из W1 Петя завершает игру 
Дополним код подпрограммой, определяющей  W2 на основании ST2 и L1 
Также определим ST3  = ST2 / W2 - множество позиций, остающихся в игре



ST3  - это позиции, остающиеся в игре после трех тактов. Теперь можем определить \(L_2 =\{ v \in St_3\ |\ O(v) \subset W_1\bigcap W_2 \}\) - множество позиций из ST3, для которых "окружение" полностью лежит в объединении W1 и W2. По аналогии с L1, нетрудно понять, что в L2 будут позиции, для которых выигрышная стратегия в два хода будет у Вани.
(Выигрышная стратегия в два хода означает, что Игрок может выиграть первым или вторым ходом, но у Игрока
НЕТ выигрышной стратегии, позволяющей выиграть первым ходом)
Множество L2 определим на основании ST3 и объединения W1, W2  с помощью подпрограммы step2 
 


Поиск ответов на задания.
По условию задания, игра начинает из позиций вида (6,s). Обозначим множество позиций такого вида через Start.

Задание 20.
Найдите два наименьших значения S,  при которых у Пети есть выигрышная стратегия,
причём одновременно выполняются два условия: 

– Петя не может выиграть за один ход; 
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. 

Для получения ответов на задание 20 надо найти пересечения множест W2 и Start

Задание 21. 
Найдите минимальное значение S, при котором одновременно выполняются два условия: 

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. , надо 

Для получения ответов на задание 21 надо найти пересечения множест L2 и Start

Задание 19
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.
Укажите минимальное значение S, при котором такая ситуация возможна.
Для получения ответов на задание 19  надо понять, что своим ходом Петя попал в  W1,  причем изменив количество
камней во второй куче, а значив  оставшись в множестве Start
Это нетрудно сделать, посмотрев на множество на пересечение W1 и Start
Дополним программу соответствующими выводами информации




Ответом на задание 19 будет S=7. Тогда Петя мог пойти в позицию (6,21) из которой Ваня мог победить 

Ответом на задание 19 будет S=7. Тогда Петя мог пойти в позицию (6,21) из которой Ваня мог победить 

Подведем итоги
  • Представленную программу сложно назвать эффективной и универсальной, зато она хорошо иллюстрирует основные шаги метода "раскраски", с помощью которого решаются многие задачи игровых стратегий.
  • С помощью предложенной программы можно решать задания как с одной, так и с насколькими кучами.
  • При решении активно использовались операции с множествами, что упрощает понимание алгоритма (хотя и понижает эффективность
  • Далее разберем вопросы "оптимизации" и решение заданий с другими правилами игры
Пропустить Навигационные Ссылки. Чтобы оставить комментарий нужна авторизация
Печать