Дерево игры

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

← Вернуться к оглавлению
Alterna · глава 22 · страница 22.3
Дерево игры
Игры с полной информацией, минимакс, альфа-бета.
Дерево игры — частный случай ДАГ. Содержит все возможные продолжения игры. Алгоритм минимакс находит оптимальный ход. Альфа-бета ускоряет в 2-10 раз. Связь с главой 18.
ФГОС
ФОП
ЕГЭ №23
01
Игры с полной информацией
В играх с полной информацией (шахматы, крестики-нолики) оба игрока видят всё состояние. Это позволяет использовать дерево игры для анализа.
В отличие от случайных игр (нарды с костями), в играх с полной информацией оптимальный ход можно вычислить (теоретически).
02
Минимакс
Минимакс: на уровне max (Первый) берём максимум, на уровне min (Второй) — минимум. Рекурсивно снизу вверх.
Для малых деревьев (глубина ≤ 6) работает идеально. Для больших — альфа-бета или эвристики.
03
Крестики-нолики: минимакс на canvas
❌
Крестики-нолики против ИИ (минимакс)
Ты играешь за
❌
, ИИ — за
⭕
Твой ход!