Game Tree

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

Back to the table of contents
Alterna · Chapter 25 · page 25.3
Game Tree
How to describe the strategy in chess, checkers, "nolic-crests 5 in rows" through a tree of solutions.
Game Tree
It is a tree where the vertices are positions and the ribs are player moves. The leaves are rated (win/win/nothing) and are looking for an optimal strategy.
GEF
PIF
EEG No. 23, 26.27
01
Minimax algorithm
At each level of the tree, players choose to move in different ways:
MAX game
(who wants to win) picks a move with
maximum
evaluation.
MIN-game
(opportunist) picks a move with
Minimum
evaluation.
The estimates rise from leaves to roots: at each level, MAX takes the maximum, MIN takes the minimum of the progeny.
02
Example: 2 moves forward
Tree: MAX 3 option ♪ MIN ♪ leaves (assessments)
MAX
A
=3
B
=4
A1
3
A2
5
B1
2
B2
8
MAX selects MAX(3.4) = 4 * stroke B
MIN=3
MIN=4
MAX
(Chief) - Looking for
maximum
MIN
(opposer) - looking
minimum
Leaves:
A1=3, A2=5 → A = min(3,5) =
3
B1=2, B2=8 → B = min(2,8) =
4
Decision:
MAX selects max(3, 4) =
4
Optimal move -
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 листов (в лучшем случае)
🎮
Minimax: Animation of tree + alpha-beta
03
Alpha-beta cut-off
Expediting over-the-end without losing results
The idea is that if we've already found a good move, and we see that a rival can do as much as we did before, we can count on it.
α
(alpha) is the best MAX estimate found on the way to the root.
β
(Beta) is the best rating for MIN.
If α ≥ β is no longer relevant, we cut it off.
At best, alpha-beta accelerates overtaking to GN times (instead of O(N) o(GN)).
🎯
Mini-test: 5 questions
XP: 0
🧩
Quick test on the subject
Five questions, 20 XP for every correct answer.