Теория игр ЕГЭ по информатике: как решать коротко
Задачи про кучу камней решаются от конца игры. Сначала находишь позиции, из которых игрок выигрывает одним ходом. Потом — позиции, из которых любой ход ведёт в такую выигрышную, это проигрыш для того, кто ходит. Дальше по цепочке: выигрыш в два хода, проигрыш после двух ходов. Рисовать всё дерево в голове не нужно. Раскладываешь позиции по классам на числовой прямой, а ответ проверяешь короткой рекурсивной программой.
Почему Петя и Ваня с камнями валят сразу три задания
Знакомая картина: открываешь блок про Петю и Ваню, читаешь условие, вроде всё понятно — добавить камень или удвоить кучу. Начинаешь прикидывать: «если Петя сделает так, то Ваня ответит так, а потом…» — и через пять минут в черновике каша из стрелок. Ответ в первом задании получается каким-то, во втором ты уже не уверен, третье бросаешь. Обидно, потому что все три держатся на одной идее.
Главная причина провала — попытка перебрать партию вперёд, от стартовой позиции. Дерево ходов растёт очень быстро: два варианта хода у каждого игрока, несколько раундов, и веток уже десятки. Удержать их в голове невозможно, а на бумаге это занимает время, которого на КЕГЭ и так мало. Ошибка в одной ветке тянет за собой ошибку во всех трёх ответах, потому что они строятся друг на друге.
Вторая причина — путаница в формулировках. «Выиграть своим первым ходом», «выиграть при любой игре соперника», «не может выиграть за один ход, но может за два» — эти фразы звучат похоже, но означают разные классы позиций. Если не понимать, какой класс от тебя хотят, даже верно посчитанные позиции дадут неверный ответ. Хорошая новость: и то, и другое лечится одним методом.
Выигрышные и проигрышные позиции: что это простыми словами
Позиция — это просто количество камней в куче перед ходом. Выигрышная позиция — та, из которой игрок, который сейчас ходит, может победить, как бы ни играл соперник. Проигрышная — та, из которой ходящий проиграет при правильной игре соперника, что бы он ни делал. Всё. Кто такой Петя и кто такой Ваня, важно только для того, чтобы понять, чей сейчас ход.
Правило связи между позициями одно, и его стоит выучить наизусть. Позиция выигрышная, если из неё есть хотя бы один ход в проигрышную позицию для соперника. Позиция проигрышная, если все ходы из неё ведут в выигрышные позиции для соперника. Слова «хотя бы один» и «все» — это и есть вся теория игр, которая нужна на экзамене. Остальное — аккуратный счёт.
Дальше позиции делят по числу ходов. Выигрыш в один ход: есть ход, который сразу заканчивает игру. Проигрыш в один ход: любой твой ход отдаёт сопернику выигрыш в один ход. Выигрыш в два хода: есть ход в позицию «проигрыш в один ход». И так далее. Эти классы и спрашивают в трёх связанных заданиях, просто разными словами.
Как решать задачи про кучу камней от конца игры
Возьмём условный пример, не из конкретного варианта. В куче S камней, за ход можно добавить один камень или удвоить кучу. Игра заканчивается, когда в куче стало 30 камней или больше, выигрывает тот, кто сделал последний ход. Начинаем не с S, а с финиша: из каких позиций можно закончить игру одним ходом? Удвоение даёт 30 и больше при S от 15 до 29 — это выигрыш в один ход.
Теперь ищем проигрыш в один ход: позиции, где оба хода ведут в отрезок от 15 до 29. Из 14 получается 15 или 28 — обе выигрышные для соперника, значит, 14 проигрышная. Из 13 можно пойти в 14, а это уже не выигрыш соперника в один ход, поэтому 13 сюда не подходит. Видишь: никакого дерева, просто проверка двух чисел для каждой позиции.
Следующий слой — выигрыш в два хода: позиции, из которых есть ход в 14. Это 13, потому что плюс один, и 7, потому что удвоение. Затем проигрыш после двух ходов: все ходы ведут в выигрышные позиции, и хотя бы один — в выигрыш в два хода. Проверяем 12: ходы в 13 и 24, обе выигрышные, одна из них двухходовая. Значит, 12 подходит. Так слой за слоем и решается весь блок.
Как оформить решение в черновике, чтобы не запутаться
Самый удобный способ — числовая прямая или строка таблицы. Выписываешь числа от небольшого значения до финиша и под каждым ставишь метку класса: «В1» для выигрыша в один ход, «П1» для проигрыша после одного хода, «В2», «П2» и так далее. Двигаешься справа налево, от конца игры к началу. Каждую новую метку ставишь, только проверив оба хода из этой позиции.
В электронной таблице это делается ещё быстрее. В первом столбце — количество камней, во втором и третьем — результаты двух возможных ходов, в четвёртом — метка класса. Глазами сверяешь, в какие классы попадают ходы, и сразу видишь ответ. Такой способ хорош тем, что ошибку легко найти: она сидит в одной конкретной строке, а не размазана по всему дереву.
Важная привычка — записывать, что именно спрашивают, до начала счёта. Перепиши формулировку своими словами: «нужна позиция, где Ваня выигрывает первым ходом при любой игре Пети» — это проигрыш для Пети в один ход. Когда класс назван заранее, ты не перепутаешь его с соседним в конце. Половина потерь в этом блоке происходит не в счёте, а в переводе условия на язык позиций.
Как проверить ответ по теории игр программой на Python
Ручной счёт полезен, чтобы понимать задачу, но на экзамене надёжнее подтвердить ответ кодом. Стандартный приём — рекурсивная функция с двумя параметрами: текущее число камней и сколько ходов осталось. Если камней уже достаточно для финиша, функция проверяет, чей ход был последним и кто выиграл. Если ходов не осталось, а игра не закончена — это не победа.
Внутри функции сравниваешь, чей сейчас ход. Для игрока, который должен выиграть, достаточно, чтобы хотя бы один ход приводил к победе — в Python это функция any. Для соперника нужно, чтобы победа сохранялась при всех его ходах — это функция all. Ровно то же правило «хотя бы один» и «все», что и в ручном решении, только записанное кодом. Потом перебираешь S в цикле и печатаешь подходящие значения.
Тонкий момент — формулировки «не может выиграть за один ход, но может за два». Тут проверяешь два условия сразу: функция с меньшим числом ходов возвращает ложь, с большим — истину. Если пропустить первое условие, в ответ попадут лишние позиции. Разобрать такой шаблон кода и потренировать его на разных условиях можно бесплатно в разделе подготовки к ЕГЭ на Prepodoff: там есть теория по темам ФИПИ и тренажёры с разборами.
Что делать, если в задаче две кучи или другие ходы
Иногда куч две, а ходы — добавить камень в одну из куч или увеличить одну из них в несколько раз. Пугаться не нужно: метод тот же, только позиция теперь описывается парой чисел, а не одним. Вместо числовой прямой рисуешь таблицу, где строки — камни в первой куче, столбцы — во второй. Метки классов ставишь в клетки, двигаясь от финиша.
В программе с двумя кучами функция просто получает три параметра: две кучи и число оставшихся ходов. Список возможных ходов становится длиннее, но логика any и all не меняется. Поэтому стоит один раз написать аккуратный шаблон и на тренировках менять в нём только условие финиша и список ходов. Тогда на экзамене ты правишь пару строк, а не пишешь решение с нуля.
Бывают и другие варианты: ходы, которые уменьшают кучу, финиш при условии «меньше или равно», запрет на повтор хода. Каждый раз задавай себе три вопроса: какие ходы разрешены, когда игра кончается, кто побеждает. Ответы подставляешь в шаблон. Если условие непривычное, сначала посчитай пару позиций руками и сверь с программой — так ловится большинство ошибок в коде.
Можно ли решать теорию игр только программой и не разбираться
Формально да: многие сдают этот блок готовым шаблоном кода. Но если не понимать, что считает функция, легко ошибиться в мелочи — поставить any вместо all, перепутать, чей ход первый, неверно задать финиш. Программа честно выдаст ответ, только неправильный, и проверить его будет нечем. Понимание классов позиций — это и есть способ заметить, что код врёт.
Оптимальная схема такая: разбираешься в методе руками на двух-трёх простых задачах, потом пишешь шаблон и прогоняешь его на тех же задачах. Ответы совпали — шаблону можно доверять. Дальше на тренировках решаешь программой, а руками делаешь быструю прикидку для самопроверки. Так уходит страх перед блоком, а время на него сокращается.
Если застреваешь на объяснении, почему any, а не all, или не понимаешь разбор, его можно попросить объяснить ещё раз другими словами. В «Моём плане» — бесплатном планировщике в Telegram — есть ИИ-тренер: он объясняет теорию, разбирает решения и составляет план подготовки к экзамену, чтобы теория игр не оставалась на последнюю неделю.
Как натренировать теорию игр к КЕГЭ и не терять три задания
Теория игр пугает только до тех пор, пока ты пытаешься перебрать партию вперёд. Как только переходишь к движению от конца игры и классам позиций, три связанных задания превращаются в одну задачу с тремя вопросами. Выучи правило «хотя бы один ход в проигрыш — выигрыш, все ходы в выигрыш — проигрыш», и большая часть страха уйдёт.
Тренируй блок регулярно, а не за неделю до экзамена: по несколько задач с разными ходами и условиями финиша, каждый раз сначала руками, потом кодом. Записывай, какие формулировки сбивают тебя чаще, и переписывай их своими словами перед счётом. Через несколько таких подходов задачи начнут решаться почти механически.
Теорию по теме, тренажёры и разборы задач про камни можно найти в бесплатной подготовке к ЕГЭ на Prepodoff в разделе /ege. Аккаунт нужен только для того, чтобы сохранять прогресс и видеть, какие темы уже закрыты. Так Петя и Ваня перестанут быть самым нервным местом варианта.
