Minimax & Alpha-Beta Pruning

Definition

Minimax picks the best move assuming the opponent plays optimally; alpha-beta skips branches that can't matter.

Classic game AI for tic-tac-toe and chess.

Diagram

Flowchart

Example: Minimax on a tree

def mm(n, is_max):
    if isinstance(n, int): return n
    vals = [mm(c, not is_max) for c in n]
    return max(vals) if is_max else min(vals)
print(mm([[3, 5], [2, 9]], True))

Output: 3

Complexity

O(b^d) · alpha-beta best case O(b^(d/2))

Key points

• Good move ordering improves pruning
• Depth limits + evaluation function in practice

Interview questions

More AI topics