Как описать стратегию в шахматах, шашках, «крестиках-ноликах 5 в ряд» — через дерево решений.
Дерево игры — это дерево, в котором вершины — позиции, а рёбра — ходы игроков. На листьях выставлены оценки (выигрыш/проигрыш/ничья). По нему ищут оптимальную стратегию.
На каждом уровне дерева игроки выбирают ход по-разному:
Оценки поднимаются от листьев к корню: на каждом уровне MAX берёт максимум, MIN — минимум из значений потомков.
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 листов (в лучшем случае)
Ускорение перебора без потери результата
Идея: если мы уже нашли хороший ход и видим, что соперник может добиться результата не хуже, чем мы нашли раньше, — дальше можно не считать.
В лучшем случае альфа-бета ускоряет перебор в √N раз (вместо O(N) → O(√N)).
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.