Minimax algorithm

📘 Problem Solving by Searching: Minimax Algorithm

1. What is the Minimax Algorithm?

The Minimax algorithm is used in two-player, turn-based, zero-sum games (like Tic-Tac-Toe, Chess, or Checkers). It helps AI choose the best move assuming the opponent also plays optimally.

It aims to maximize the AI’s gain while minimizing the opponent’s gain — hence the name minimax.

2. Key Concepts

3. How Minimax Works

1. Generate the game tree from the current state.

2. Evaluate terminal states using a utility function.

3. Propagate values up the tree:

   • Max nodes choose the maximum value of their children.
   • Min nodes choose the minimum value of their children.

4. Choose the move that leads to the best value at the root (AI's turn).

4. Example: Simple Game Tree

          [AI]
          Max
         /    \
      Min     Min
     / \      / \
   +1  0    -1  +1

• At Min nodes: pick the minimum child value → First Min: min(+1, 0) = 0 → Second Min: min(–1, +1) = –1

• At Max (AI): pick the maximum of 0 and –1 → Best move = 0

5. Time Complexity

• Time: O(b^m)

  • b = branching factor (possible moves per turn)
  • m = maximum depth of the game tree

• Space: O(m) for depth-first implementation

6. Optimization: Alpha-Beta Pruning

Minimax can be optimized with Alpha-Beta pruning, which:

• Eliminates branches that don't need to be explored.
• Reduces time complexity from O(b^m) to O(b^(m/2)) in the best case.

✅ Summary