Задание 20. Поиск выигрышной стратегии игры: ЕГЭ по информатике

Задание 20 ЕГЭ по информатике проверяет умение находить выигрышную стратегию в конечной детерминированной игре с полной информацией (обычно игра с камнями или фишками). Требуется проанализировать позиции, определить, кто выигрывает при оптимальной игре, и записать ответ в виде числа или…

Что нужно знать

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

Термины и понятия

• Выигрышная позиция: позиция, из которой существует ход, приводящий к победе (или к проигрышной позиции соперника).
• Проигрышная позиция: позиция, из которой все ходы ведут в выигрышные позиции для соперника.
• Выигрышная стратегия: алгоритм действий игрока, гарантирующий ему победу при любой игре соперника.
• Дерево игры: граф, вершины которого — позиции, а рёбра — возможные ходы.
• Обратная индукция: метод анализа игры с конца, при котором определяются выигрышные и проигрышные позиции, начиная с терминальных.
• Терминальная позиция: позиция, в которой игра заканчивается (например, камней больше 100).
• Ход: изменение позиции одним игроком.
• Игрок: участник игры (обычно Петя и Ваня).

Частые ошибки

• Неверное определение терминальной позиции: например, не учитывают, что игра заканчивается при превышении порога, а не при достижении.
• Путают выигрышную и проигрышную позиции: считают позицию выигрышной, если из неё есть ход в другую выигрышную, а не в проигрышную.
• Не учитывают, что игроки могут делать несколько ходов подряд, если это разрешено условием (например, в некоторых задачах ход можно делать до тех пор, пока есть возможность).
• Пропускают выигрышный ход, рассматривая не все возможные ходы из позиции.

Как пройти тему

В курсе «Информатика» тема «Задание 20. Поиск выигрышной стратегии игры» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Задание 1. Представление и считывание данных в информационных моделях
• Задание 2. Таблицы истинности и логические схемы
• Задание 5. Формальное исполнение алгоритма
• Задание 6. Результаты работы алгоритмов управления исполнителями
• Задание 7. Объём памяти для графической и звуковой информации
• Задание 9. Обработка числовой информации в электронных таблицах

← Предыдущая тема: Задание 19. Анализ алгоритма логической игры
Следующая тема: Задание 21. Дерево игры и выигрышная стратегия

Все темы: ЕГЭ по информатике