Alpha-Beta Pruning

Game Playing and Adversarial Search

AI, Artificial and Computational Intelligence
AI, ACI, Game Playing, Minimax, Alpha-Beta Pruning, Monte Carlo Tree Search, Stochastic Games

Game Playing and Adversarial Search #

Game-playing agents search in environments where other agents influence the outcome. In competitive games, a good move must account not only for what the agent wants to achieve, but also for the strongest response an opponent can make.

  • Searching to play games

  • Minimax Algorithm

  • Alpha-Beta Pruning

  • Monte Carlo Tree Search

  • Stochastic Games

Learning Objectives #

  • formulate a game as an adversarial search problem
  • construct a game tree with alternating MAX and MIN turns
  • design and interpret a static evaluation function
  • back up values using Minimax
  • apply Alpha-Beta Pruning and identify cut-offs
  • explain the four phases of Monte Carlo Tree Search
  • calculate an MCTS selection score using UCB1
  • evaluate chance outcomes in a stochastic game

Big Picture #

flowchart TD
    A["Game state"] --> B["Generate legal moves"]
    B --> C["Build game tree"]
    C --> D["Evaluate leaves"]
    D --> E["Choose robust action"]
    E --> A

    style A fill:#E1F5FE
    style B fill:#FFF9C4
    style C fill:#EDE7F6
    style D fill:#FFF9C4
    style E fill:#C8E6C9

In normal search, the agent controls its own actions and the transition model determines what happens next. In adversarial search, another agent chooses actions that may reduce the first agent’s utility.