Дерево игры и минимакс

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

← Вернуться к оглавлению
Alterna · глава 19 · страница 19.2
Дерево игры и минимакс
Алгоритм минимакс с альфа-бета отсечением. Анимированная визуализация дерева.
Дерево игры
— каждый узел это позиция, каждый ребёнок — возможный ход.
Минимакс
вычисляет оптимальный результат: MAX берёт максимум, MIN — минимум.
Альфа-бета
отсекает ветви, не влияющие на результат.
ФГОС
ФОП
ЕГЭ №21
01
Дерево игры
Дерево игры
— корневое дерево, где:
Корень
— стартовая позиция S.
Чётная глубина
(0, 2, 4, ...) — ход
MAX (Петя, Первый)
.
Нечётная глубина
(1, 3, 5, ...) — ход
MIN (Вася, Второй)
.
Листья
— терминальные позиции (цель достигнута).
02
Алгоритм минимакс
Правило
На уровне
MAX
— берём
максимум
среди детей.
На уровне
MIN
— берём
минимум
среди детей.
Альфа-бета отсечение
α
— лучший результат для MAX на данном пути.
β
— лучший результат для MIN на данном пути.
Если
α ≥ β
— поддерево можно отсечь.
03
Визуализатор минимакса
Введи 8 значений листьев — увидишь анимацию вычисления снизу вверх
🌳
Минимакс: дерево глубины 3
Листья (8 значений, через запятую)
04
Генератор деревьев игры
Выбери тип игры — система построит дерево и покажет L/W-разметку
🎮
Конструктор деревьев игры
Тип игры
Стартовое S
Цель (≤0 или ≥N)
Макс. глубина
Нажми «Построить дерево»
Легенда
■ MAX (Петя)
·
■ MIN (Вася)
·
■ W — выигрышная
·
■ L — проигрышная
🤖
Игра: Крестики-нолики против ИИ (минимакс)
ИИ использует алгоритм минимакс — просчитывает все возможные ходы на глубину и выбирает оптимальный. Попробуй победить!
Ваш ход (X)
05
Альфа-бета: сравнение
Узнай, сколько узлов отсекает альфа-бета vs полный минимакс
✂️
Альфа-бета vs Минимакс: узлы и отсечения
Глубина дерева
Ветвей у каждого узла
Минимакс (без отсечения)
Нажми «Запустить»
Альфа-бета (с отсечением)
Нажми «Запустить»
06
Мини-тест: минимакс и деревья
5 вопросов по минимаксу и деревьям игр
XP: 0
🎯
Тест: Минимакс
5 вопросов по минимаксу и деревьям игр