Module 4: Game Searches


Executive Summary

  • Topics:
    • Search with adversaries (e.g. games)
    • Minimax search
    • Alpha-beta pruning
    • Handling large and more challenging games
    • Ethics of game search 
  • Length: This module will take two weeks to complete
  • Assigned chapters: Chapter 5
  • Project: Project 3 (will stay open one week beyond this module)

Adversarial search

Many games can be fully solved through search techniques but the problem formulation and the search approaches that we have studied so far cannot handle searching in a strategic situation with multiple agents.  In this module, we will discuss adversarial search techniques, starting from simple games that can be fully searched and moving to more advanced games where we must use approximations to the full search.

Hybrid machine learning and search approaches have been in the news lately especially with the AlphaZero series of games (see link and photo to the right).  Although we will discuss the foundational search approaches for these methods, we will not cover the machine learning methods until a later module.

Real World search

Chess with alpha zero

Photo from this DeepMind blog post about AlphaZero

Next topic

Jump into our first topic of optimal game searches