Algorithm Deep Dive

Algorithm Deep Dive

Minimax with α–β pruning evaluates game trees to optimal depth while discarding branches that cannot influence the final decision.

1. Vanilla Minimax

flowchart TD
    A[Root] --> B1[Child 1]
    A --> B2[Child 2]
    B1 --> C1[Leaf]
    B2 --> C2[Leaf]

Loading

Time Complexity

• O(bᵈ) for branching factor b and depth d.

2. α–β Pruning

Keeps track of two bounds

• α – best max already found.
• β – best min already found.

When β ≤ α, further exploration is cut.

Best‑case reduction: evaluates O(b^{d/2}) nodes.

3. Move Ordering

Good move ordering increases early cut‑offs.

Strategies:

• Hash history
• Killer moves
• Board symmetries

Minimax does not implement ordering internally—leave it to your generateMoves() heuristic.

4. Iterative Deepening (Roadmap)

Future versions will call the search incrementally to fit within a time budget.