Дерево игры и алгоритм минимакс (задание 20)

Зачем это в ЕГЭ. Задание 20 в ЕГЭ по информатике проверяет умение анализировать дерево игры и применять алгоритм минимакс для поиска оптимального хода. Оно оценивается в 1 первичный балл и встречается в каждом варианте ФИПИ.

Главная идея. Алгоритм минимакс используется для поиска наилучшего хода в игре с двумя игроками, где один стремится максимизировать выигрыш, а другой — минимизировать. Суть в том, чтобы просчитать все возможные ходы и выбрать тот, который гарантирует максимальный выигрыш при худшем противодействии.

Алгоритм (чеклист).
1. Построй дерево игры, где каждый уровень соответствует ходу одного из игроков.
2. На листьях дерева запиши значения выигрыша для текущего игрока.
3. Для каждого узла на предпоследнем уровне выбери минимальное значение из его потомков (если это ход противника).
4. Для каждого узла на предыдущем уровне выбери максимальное значение из его потомков (если это ход текущего игрока).
5. Повторяй шаги 3 и 4, пока не дойдёшь до корня дерева.
6. Проверь, что выбранный ход действительно максимизирует выигрыш при любом противодействии.

Опоры (кратко).
- Минимакс: $\text{minimax}(n) = \begin{cases} \text{оценка}(n), & \text{если } n \text{ — лист} \\ \max(\text{minimax}(c)), & \text{если } n \text{ — ход текущего игрока} \\ \min(\text{minimax}(c)), & \text{если } n \text{ — ход противника} \end{cases}$
- Дерево игры: структура, где узлы — состояния игры, а рёбра — возможные ходы.

Пример 1 (базовый подтип).
Дано дерево игры с тремя уровнями. Листья имеют значения: [3, 5, 2, 8, 1, 4].
Шаг 1. Построй дерево: корень — первый ход, два узла на втором уровне — ходы противника, шесть листьев — конечные состояния.
Шаг 2. На втором уровне выбери минимальные значения для каждого узла: min(3, 5) = 3, min(2, 8) = 2, min(1, 4) = 1.
Шаг 3. На корневом уровне выбери максимальное значение из [3, 2, 1]: max(3, 2, 1) = 3.
Шаг 4. Оптимальный ход — первый, гарантирующий выигрыш не менее 3.

Пример 2 (усложнённый подтип).
Дано дерево игры с четырьмя уровнями. Листья имеют значения: [7, 3, 9, 2, 5, 6, 1, 4].
Шаг 1. Построй дерево: корень — первый ход, два узла на втором уровне — ходы противника, четыре узла на третьем уровне — ходы текущего игрока, восемь листьев — конечные состояния.
Шаг 2. На третьем уровне выбери максимальные значения для каждого узла: max(7, 3) = 7, max(9, 2) = 9, max(5, 6) = 6, max(1, 4) = 4.
Шаг 3. На втором уровне выбери минимальные значения для каждого узла: min(7, 9) = 7, min(6, 4) = 4.
Шаг 4. На корневом уровне выбери максимальное значение из [7, 4]: max(7, 4) = 7.
Шаг 5. Оптимальный ход — первый, гарантирующий выигрыш не менее 7.

Типичные ошибки.
1. Неправильное построение дерева. Упускают уровни или неправильно распределяют ходы между игроками.
2. Ошибка в выборе min/max. Путают, когда нужно выбирать минимальное, а когда максимальное значение.
3. Неверный подсчёт значений на листьях. Используют неправильные значения выигрыша.
4. Пропуск шага проверки. Не убеждаются, что выбранный ход действительно оптимален.
5. Путаница в уровнях дерева. Не учитывают, что уровни чередуются между игроками.

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