ЕГЭ‑инфо без паники: алгоритм minimax

Что за тема и для чего она нужна

** изображение создано или обработано с помощью ИИ.

Название «minimax» звучит как пароль от сейфа. На деле это обычная логика. Мне 27, я сам сдавал экзамены и готовлю к ним других. Говорю честно: пугает не тема, а туман вокруг неё.

Где нужен minimax в ЕГЭ по информатике? В заданиях 19-21, где два игрока ходят по очереди. Один хочет выиграть. Второй — тоже. Каждый выбирает лучший ход для себя. Поэтому мы не ищем красивый путь в одиночку. Мы учитываем: соперник будет мешать.

В ЕГЭ по информатике это чаще всего игра с кучами камней. Игроки добавляют камни, умножают количество или уменьшают. Побеждает тот, кто первым достигает нужного значения. Формулировки меняются, но основа одна.

То есть как шахматы? Почти. Только доска меньше, ферзь не драматизирует, а вместо фигур — числа. Мы строим дерево ходов и размечаем позиции. Где можно победить за один ход — позиция выигрышная. Где любой ход ведёт в проигрыш — позиция проигрышная.

Minimax учит думать за двоих. Не как оптимист перед контрольной, который надеется, что соперник ошибётся. А как человек, который знает: Петя и Ваня хотят победить одинаково сильно. Оба будут выбирать лучшие ходы без жалости.

Вам не нужно программировать полноценный игровой движок. Достаточно: чётко записать правила хода (сколько и как можно изменить кучу); обозначить выигрышное значение (цель); аккуратно просчитать позиции с конца к началу.

Ошибка, которую я часто вижу: ученик считает только свои лучшие ходы, а ходы соперника пропускает или делает их «слабыми» нарочно. Такой расчёт не принимает на экзамене. Судья проверяет именно minimax — с учётом ответов второго игрока.

Как работает minimax: логика без сложных формул

** изображение создано или обработано с помощью ИИ.

Представьте позицию в игре. У вас есть несколько возможных ходов. После каждого хода отвечает соперник. Он не обязан вам помогать. Он выберет самый неприятный для вас вариант из доступных.

Отсюда и название: Max (тот, кто ходит) пытается получить лучший результат. Min (соперник) старается этот результат испортить. В школьных задачах я объясняю проще: текущий игрок ищет выигрышный ход, зная, что противник будет сопротивляться.

1. Если позиция уже конечная (достигнуто условие победы или поражения), исход известен. Дальше думать не нужно.

1. Если текущий игрок может одним ходом переместить игру в позицию, которая является проигрышной для соперника, значит, текущая позиция выигрышная.

1. Если все возможные ходы текущего игрока ведут только в позиции, которые будут выигрышными для соперника, значит, текущая позиция проигрышная.

Сухо. Но работает железно. Я рисую ученикам маленькую схему: внизу финальные позиции, выше — позиции за один ход до конца, ещё выше — за два хода. Дерево получает метки постепенно.

А если ходов много? Тогда рисовать дерево руками становится неудобно — быстро превращается в макароны. Спасает рекурсия или таблица (массив с состояниями). Но сама идея не меняется: я сначала определяю, чем заканчивается игра внизу (базовые позиции), потом поднимаю вывод наверх.

В экзамене часто спрашивают не просто «кто выигрывает». Например:

1. «Кто выигрывает при безошибочной игре обоих?»

1. «Найдите выигрышный ход первым ходом.»

1. «Кто может победить вторым ходом, независимо от ответа соперника?»

Эти формулировки меняют, что именно проверять. Слова «первым ходом», «вторым ходом», «независимо от ответа» — не украшения. Они указывают, на какую глубину анализа заглядывать и какой диапазон ходов рассматривать. Я всегда выписываю их отдельно перед тем, как начать размечать позиции.

Где это встречается в ЕГЭ по информатике

** изображение создано или обработано с помощью ИИ.

В материалах для подготовки игровые стратегии обычно проходят под номерами 19-21. Нумерацию лучше сверить с демоверсией ФИПИ — она меняется.

Есть стартовое число или две кучи. Есть правила ходов. Есть порог победы. Петя ходит первым, Ваня — вторым. Если спрашивают про Ваню, недостаточно, чтобы он хотел выиграть. Нужно, чтобы его победа наступала при любых ответах Пети.

Ученик видит слово «может» и ищет один удачный сценарий. В задачах на стратегию этого мало. Я называю это правилом «злого соседа»: соперник не пропустит выгодный ход. Ваш план должен выдержать его вредность.

Тема minimax требует не заучивания, а десятка прочитанных задач, пока мозг не начнёт сам спрашивать: «А что сделает соперник?»

Если хотите системной поддержки, выберите проверенный онлайн-подготовку к ЕГЭ. Хороший разбор от преподавателя, который видит типичные ошибки, экономит время. Не магия — просто чужой опыт, упакованный в структуру. Системная практика под присмотром помогает быстрее перейти от «кажется, понял» к «решу на экзамене без ошибок».

Мини-инструкция: как решать задачу без паники

** изображение создано или обработано с помощью ИИ.

Я использую один маршрут. Скучный, как гречка. Зато после него ошибки резко редеют.

Нахожу конечное условие (например, сумма стала не меньше заданного числа). Записываю все возможные ходы — не держу их в голове. Определяю, кто ходит первым, обычно это Петя. Разбираю позиции с конца, не прыгаю сразу к старту. Отмечаю выигрышные и проигрышные состояния. Проверяю.

Для кода схема простая. Пишу функцию, которая принимает позицию и номер хода. Если игра закончилась — возвращаю результат. Иначе перебираю ходы. Для своей победы нужно хотя бы один хороший вариант. Чтобы проверить, проиграет ли соперник, нужны все его ходы.

Здесь легко запутаться в словах. Поэтому я советую писать рядом с задачей маленький перевод. «Петя выигрывает первым ходом» — существует ход Пети, который сразу заканчивает игру. «Ваня выигрывает своим первым ходом» — после любого хода Пети у Вани есть победный ответ.

Ещё делаю таблицу, особенно когда стартовых чисел много. В строках — значения S. В столбце — статус позиции. Отмечаю: P1, V1, P2, V2 или просто словами. Обозначения у преподавателей разные — это нормально. Важнее понимать смысл метки. Красивые буквы не спасают дырявую логику.

Типичные ошибки и как их избежать

** изображение создано или обработано с помощью ИИ.

Я сам смотрел на дерево ходов и думал: «Победа». Потом приходил воображаемый Ваня и ломал мой план.

Вот что я чаще всего замечаю у себя и у учеников:

1. Путают «существует ход» и «любой ход» — это главное.

1. Забывают, что соперник не поддаётся.

1. Смотрят только одну ветку вместо всех.

1. Неверно определяют момент, когда игра заканчивается.

1. Пропускают один из разрешённых ходов.

1. Сворачивают размышление фразой «и так понятно» слишком рано.

Особенно коварна формулировка «может выиграть». В быту она мягкая. На ЕГЭ — строгая. Игрок действительно имеет стратегию, только если справляется с любым ответом противника.

Ещё одна боль — числовая граница. Если в условии «не менее 77», то 77 — это уже конец. Не 78. Не «больше 77». Мелочь, а баллы крадёт без сирены.

Можно просто написать программу? Можно. Но программа усиливает вашу мысль, а не заменяет её. Если условие понято неверно, код честно посчитает неверный результат. Компьютер не спорит. В этом его красота и коварство.

Для самопроверки я проговариваю каждый статус вслух. Звучит странно. Но мозг так лучше ловит подмены. Например: «Эта позиция выигрышная, потому что есть ход в проигрышную для соперника». Вот так.

Тренировка перед экзаменом: маленький план

** изображение создано или обработано с помощью ИИ.

Начните с крошечной игры. Возьмите число S. За ход можно + 1 или * на 2. Победа при S ≥ 20. Разметьте позиции от 19 вниз до 1. Каждая позиция: выигрышная (есть ход в проигрышную для соперника) или проигрышная (все ходы ведут в выигрышные для соперника).

Потом усложните. Добавьте вторую кучу. Ходы: прибавить 1 к любой куче или удвоить одну из куч. Победа по сумме. Здесь таблица удобнее рисунка — строки для одной кучи, столбцы для другой, внутри статус позиции.

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

Чек-лист перед ответом:

1. Конечное условие понято точно?

1. Учтены все ходы обоих игроков?

1. Вывод работает при любом ответе соперника?

1. Не перепутаны первый и второй ход?

1. Крайние значения проверены?

Придумайте игру с одним числом. Разрешите два хода (например, +2 и ×3). Задайте порог победы (например, 30). Найдите все стартовые значения, где первый игрок выигрывает сразу. Затем — где он выигрывает своим вторым ходом.

Если получилось, вы уже не просто «слышали про minimax». Вы начали думать как стратег. А на ЕГЭ по информатике нужно именно это: спокойно, точно и без героического страдания.