Minimax Algorithm Explained

Python Implementation

Below is a standard Python implementation of the Minimax algorithm featuring Alpha-Beta Pruning. This optimization keeps track of two variables:

• Alpha (α): The best score the Maximizer can guarantee. Initialized to negative infinity.
• Beta (β): The best score the Minimizer can guarantee. Initialized to positive infinity.

def minimax(board, depth, is_maximizing, alpha, beta):
    # Base cases: game ends
    if check_win(board, "X"):
        return 10 - depth
    if check_win(board, "O"):
        return -10 + depth
    if not empty_cells(board):
        return 0

    if is_maximizing:
        best_score = -float('inf')
        for move in legal_moves(board):
            board[move] = "X"
            score = minimax(board, depth + 1, False, alpha, beta)
            board[move] = None
            best_score = max(best_score, score)
            alpha = max(alpha, score)
            if beta <= alpha:
                break # Pruning happens here
        return best_score
    else:
        best_score = float('inf')
        for move in legal_moves(board):
            board[move] = "O"
            score = minimax(board, depth + 1, True, alpha, beta)
            board[move] = None
            best_score = min(best_score, score)
            beta = min(beta, score)
            if beta <= alpha:
                break # Pruning happens here
        return best_score