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, and value.
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 -∞ and initial_beta to ∞.
- Sets depth to 3.
- Prints optimal value.

Python

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.

Implementation of Alpha-Beta pruning in Adversarial Search Algorithms

Alpha-Beta pruning in Adversarial Search Algorithms

Similar Reads

Contact Us