Module 4: Game Searches

Topic 2: Pruning Game Search

How do we handle much larger games?

MiniMax will give the optimal strategy but it cannot handle large search spaces.  We will discuss multiple ways to handle larger (and more difficult/interesting) games.  In this topic, we start with alpha-beta pruning which is a strategy to prune a MiniMax tree while still guaranteeing optimality.  

Remember, if you get stuck, please chat in Slack and ask your fellow students plus the TA and Dr. McGovern for help!  Go to #general for help in general!

  • Read Section 5.2.3-5.3 of Chapter 5 (alpha-beta pruning through Heuristic alpha-beta tree search)

Alpha-beta pruning

Evaluation functions


  • Watch the video on other approaches to searching in larger spaces.  This includes a discussion of evaluation functions, which can replace utility functions if the search is terminated before the game ends.


Next topic

Even alpha-beta pruning is not enough to handle really large games!  Let’s jump to the next topic on Monte Carlo Tree Search for more.