Дерево игры; стратегии

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 18 · страница 18.2
Дерево игры; стратегии
Минимакс + альфа-бета. Визуализатор для малых S.
Каждый ход игрока — узел дерева. Каждый лист — терминальная позиция (победа/поражение). Минимакс снизу вверх вычисляет оптимальный ход. Альфа-бета отсекает ветви, не влияющие на результат.
ФГОС
ФОП
ЕГЭ №21,23
01
Дерево игры
Дерево игры
— корневое дерево, где:
Корень — стартовая позиция.
Узел на чётной глубине (0, 2, 4, ...) — ход Первого.
Узел на нечётной глубине (1, 3, 5, ...) — ход Второго.
Листья — терминальные позиции (победа/поражение), оценка +1/−1.
02
Алгоритм минимакс
Поднимаемся снизу вверх:
На уровне
max
(Первый выбирает) берём
максимум
среди детей.
На уровне
min
(Второй выбирает) берём
минимум
среди детей.
Альфа-бета
Если α (лучшее для max) ≥ β (лучшее для min), поддерево можно отсечь — оно не повлияет на результат. Это ускоряет минимакс в 2-10 раз на практике.
03
Визуализатор минимакса
Задай терминальные значения листьев — увидишь разметку max/min
🌳
Минимакс: дерево для N=3 (глубина 3)
Значения листьев (8 шт, через запятую)