Implementation of Alpha-Beta pruning in Adversarial Search Algorithms
The provided code implements the alpha-beta pruning algorithm, a variant of the minimax algorithm used in decision-making and game theory to minimize the number of nodes evaluated in the game tree. Here is a brief explanation of each part of the code:
- Node Class: Defines a node in the game tree with
name
,children
, andvalue
. - Helper Functions:
evaluate(node)
: Returns node’s value.is_terminal(node)
: Checks if node is a terminal node.get_children(node)
: Returns node’s children.
- Alpha-Beta Pruning Function:
alpha_beta_pruning(node, depth, alpha, beta, maximizing_player)
:- Returns node value if depth is 0 or node is terminal.
- Maximizing player: Tries to maximize score, updates
alpha
, checks for beta cut-off. - Minimizing player: Tries to minimize score, updates
beta
, checks for alpha cut-off.
- Game Tree Creation:
- Creates terminal nodes (D, E, F, G, H, I) with values.
- Creates internal nodes (B, C) with children.
- Creates root node (A) with children B and C.
- Run Algorithm:
- Runs alpha-beta pruning on root node A.
- Sets
initial_alpha
to -∞ andinitial_beta
to ∞. - Sets
depth
to 3. - Prints optimal value.
class Node:
def __init__(self, name, children=None, value=None):
self.name = name
self.children = children if children is not None else []
self.value = value
def evaluate(node):
return node.value
def is_terminal(node):
return node.value is not None
def get_children(node):
return node.children
def alpha_beta_pruning(node, depth, alpha, beta, maximizing_player):
if depth == 0 or is_terminal(node):
return evaluate(node)
if maximizing_player:
max_eval = float('-inf')
for child in get_children(node):
eval = alpha_beta_pruning(child, depth-1, alpha, beta, False)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Beta cut-off
return max_eval
else:
min_eval = float('inf')
for child in get_children(node):
eval = alpha_beta_pruning(child, depth-1, alpha, beta, True)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Alpha cut-off
return min_eval
# Create the game tree
D = Node('D', value=3)
E = Node('E', value=5)
F = Node('F', value=6)
G = Node('G', value=9)
H = Node('H', value=1)
I = Node('I', value=2)
B = Node('B', children=[D, E, F])
C = Node('C', children=[G, H, I])
A = Node('A', children=[B, C])
# Run the alpha-beta pruning algorithm
maximizing_player = True
initial_alpha = float('-inf')
initial_beta = float('inf')
depth = 3 # Maximum depth of the tree
optimal_value = alpha_beta_pruning(A, depth, initial_alpha, initial_beta, maximizing_player)
print(f"The optimal value is: {optimal_value}")
Output:
The optimal value is: 3
Alpha-Beta pruning in Adversarial Search Algorithms
In artificial intelligence, particularly in game playing and decision-making, adversarial search algorithms are used to model and solve problems where two or more players compete against each other. One of the most well-known techniques in this domain is alpha-beta pruning.
This article explores the concept of alpha-beta pruning, its implementation, and its advantages and limitations.