Alpha-beta Pruning Quiz
Highest value seen so far | Max nodes update alpha
Lowest value seen so far | Min nodes update beta
Definition The highest and lowest values seen along the path to that node
Alpha and beta values are only passed down; Terminal values go up
If β ≤ α: Prune
function minimax(node, depth, alpha, beta, maximizingPlayer):
if depth = 0 or node is a terminal node:
return the value of the node
if isMaximizingPlayer:
bestValue = -infinity
for each child of node:
val = minimax(child, depth - 1, alpha, beta, False)
bestValue = max(bestValue, val)
alpha = max(alpha, val)
if beta ≤ alpha:
break
return bestValue
else:
bestValue = +infinity
for each child of node:
val = minimax(child, depth - 1, alpha, beta, True)
bestValue = min(bestValue, val)
beta = min(beta, val)
if beta ≤ alpha:
break
return bestValue
result = minimax(root, depth, -infinity, +infinity, True)
