Задание 21. Дерево игры и выигрышная стратегия: ЕГЭ по информатике

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

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

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

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

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

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

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

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

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

Начать бесплатно Открыть курс

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

← Предыдущая тема: Задание 20. Поиск выигрышной стратегии игры
Следующая тема: Задание 22. Математические модели и архитектура компьютеров

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