Дерево игры

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

← Вернуться к оглавлению
Alterna · глава 25 · страница 25.3
Дерево игры
Как описать стратегию в шахматах, шашках, «крестиках-ноликах 5 в ряд» — через дерево решений.
Дерево игры
— это дерево, в котором вершины — позиции, а рёбра — ходы игроков. На листьях выставлены оценки (выигрыш/проигрыш/ничья). По нему ищут оптимальную стратегию.
ФГОС
ФОП
ЕГЭ №23,26,27
01
Алгоритм минимакс
На каждом уровне дерева игроки выбирают ход по-разному:
MAX-игрок
(тот, кто хочет выиграть) выбирает ход с
максимальной
оценкой.
MIN-игрок
(соперник) выбирает ход с
минимальной
оценкой.
Оценки поднимаются от листьев к корню: на каждом уровне MAX берёт максимум, MIN — минимум из значений потомков.
02
Пример: 2 хода вперёд
Дерево: MAX → 3 варианта → MIN → листья (оценки)
MAX
A
=3
B
=4
A1
3
A2
5
B1
2
B2
8
MAX выбирает MAX(3,4) = 4 → ход B
MIN=3
MIN=4
MAX
(начальник) — ищет
максимум
MIN
(соперник) — ищет
минимум
Листья:
A1=3, A2=5 → A = min(3,5) =
3
B1=2, B2=8 → B = min(2,8) =
4
Решение:
MAX выбирает max(3, 4) =
4
Оптимальный ход —
B
.
def minimax(node, depth, is_max):
if node.is_leaf():
return node.value # оценка позиции
if is_max:
best = float('-inf')
for child in node.children:
best = max(best, minimax(child, depth+1, False))
return best
else:
best = float('inf')
for child in node.children:
best = min(best, minimax(child, depth+1, True))
return best
def alpha_beta(node, depth, is_max, alpha, beta):
if node.is_leaf():
return node.value
if is_max:
for child in node.children:
alpha = max(alpha, alpha_beta(child, depth+1, False, alpha, beta))
if beta <= alpha:
break # отсечение — beta не улучшится
return alpha
else:
for child in node.children:
beta = min(beta, alpha_beta(child, depth+1, True, alpha, beta))
if beta <= alpha:
break # отсечение
return beta
# Пример: глубина 2, ветвление 2 → без отсечения 4 листа,
# с альфа-бета: до 3 листов (в лучшем случае)
🎮
Минимакс: анимация дерева + alpha-beta
03
Альфа-бета отсечение
Ускорение перебора без потери результата
Идея: если мы уже нашли хороший ход и видим, что соперник может добиться результата не хуже, чем мы нашли раньше, — дальше можно не считать.
α
(альфа) — лучшая оценка для MAX, найденная на пути к корню.
β
(бета) — лучшая оценка для MIN.
Если α ≥ β, дальше считать бессмысленно — отсекаем.
В лучшем случае альфа-бета ускоряет перебор в √N раз (вместо O(N) → O(√N)).
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Быстрый тест по теме
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.