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
- Watch the video on Alpha-Beta pruning
- Copy of the slides
- If you are confused or need extra examples, here is an additional example of alpha-beta pruning step-by-step
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.
- Copy of the slides
Assignment
- Complete the exercise on alpha-beta pruning
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.