Pruning

Alpha-Beta Pruning

http://www.cs.toronto.edu/~hojjat/384f06/Lectures/Lecture06-4up.pdf

A way to optimize Minimax, Alpha-Beta Pruning skips some of the recursive computations that are decidedly unfavourable.

The benefit of alpha–beta pruning lies in the fact that branches of the search tree can be eliminated. This way, the search time can be limited to the ‘more promising’ subtree, and a deeper search can be performed in the same time.

One big problem: Assumes the opponent is rational

Pseudocode

Minimax with Alpha-Beta Pruning. Recursive calls.

def minimax(state, max_depth, is_player_minimizer, alpha, beta):
    if max_depth == 0 or state.is_end_state():
        return evaluation_function(state)
 
    if is_player_minimizer:
        value = -math.inf
        for move in state.possible_moves():
            evaluation = minimax(move, max_depth - 1, False, alpha , beta)
            min = min(value, evaluation)
            # Keeping track of our current best score
            beta = min(beta, evaluation)
            if beta <= alpha:
                break
        return value
 
    value = math.inf
    for move in state.possible_moves():
        evaluation = minimax(move, max_depth - 1, True, alpha, beta)
        max = max(value, evaluation)
        # Keeping track of our current best score
        alpha = max(alpha, evaluation)
        if beta <= alpha:
            break
    return value