Algorithm of the day -

The Minimax Algorithm with Alpha-Beta Pruning

Summary

The Minimax algorithm is a recursive algorithm used for decision making in games like chess, tic-tac-toe, etc. Alpha-Beta pruning is an optimization technique used to reduce the number of nodes to be evaluated in the Minimax algorithm.

Use Case

The Minimax algorithm with Alpha-Beta pruning can be used in a game of chess to decide the best move for a player. It evaluates all possible moves, their outcomes, and the opponent's possible responses to choose the move that maximizes the chances of winning.

Steps

  1. Initialize the best score as negative infinity for the maximizing player and positive infinity for the minimizing player.
  2. Evaluate the current state of the game and assign a score to it.
  3. Explore all possible moves from the current state and recursively call the Minimax function for each move.
  4. Apply Alpha-Beta pruning by maintaining two values, alpha and beta, which represent the best possible score for the maximizing and minimizing player respectively.
  5. Update the best score and the best move based on the scores obtained from the recursive calls.

Complexity

The time complexity of the Minimax algorithm with Alpha-Beta pruning is O(b^d) where b is the branching factor and d is the depth of the search tree. The space complexity is O(d) due to the recursive call stack.

Code Example

import random

def minimax(state, depth, alpha, beta, maximizing_player):
    if depth == 0 or game_over(state):
        return evaluate_state(state)
    if maximizing_player:
        value = -float('inf')
        for move in possible_moves(state):
            value = max(value, minimax(apply_move(state, move), depth - 1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value
    else:
        value = float('inf')
        for move in possible_moves(state):
            value = min(value, minimax(apply_move(state, move), depth - 1, alpha, beta, True))
            beta = min(beta, value)
            if beta <= alpha:
                break
        return value