MINIMAX ALGORITHM

Overview

Minimax is a decision-making algorithm for turn-based, zero-sum games. It explores the game tree to find the optimal move by assuming both players play optimally. The algorithm minimizes the maximum possible loss.

Key Features

  • ›Optimal play assumption
  • ›Game tree exploration
  • ›Alpha-beta pruning optimization
  • ›Deterministic outcomes

Algorithm Pseudocode

function minimax(node, depth, maximizing):
  if depth == 0 or game_over:
    return evaluate(node)
  
  if maximizing:
    value = -∞
    for child in node.children:
      value = max(value, 
        minimax(child, depth-1, false))
    return value
  else:
    value = +∞
    for child in node.children:
      value = min(value,
        minimax(child, depth-1, true))
    return value

Applications

Tic-Tac-Toe
Chess
Checkers
Connect Four