Minimax

Types of Game

• Perfect, imperfect
  • know all possible moves of himself and opponent
• Zero-sum, non-zero-sum
  • one player’s loss equal another player’s
• Deterministic vs Non-deterministic
  • Random choices

Minimax only works if perfect, zero-sum, deterministic

Tic Tac Toe

• AI, maximizer, uses “X”, initial -infty
• Human, minimizer, uses “O”, initial +infty

Minimax

1. Construct whole game tree
2. Apply utility function to each terminal state (win=1, loss=-1, draw=0)

Alpha-Beta Pruning

• alpha: maximum value (initial -infty)

• beta: minimum value (initial infty)

• prune a branch if alpha > beta

• advantage

• disadvantage

  • still need to reach terminal states
    • set depth limit
    • heuristic evaluation function