Module 4: Game Searches

Topic 4: Rollouts

Stochastic Games and Partial Observability

In our final topic for this module, we discuss a method called rollouts that is related to MCTS (it is based on Monte Carlo sampling).  It is not discussed much in the book but it is simple to implement and is very useful for large-scale games.  We end with a discussion of a theoretical method that works well in tiny games with chance but is of limited practical use.

  • Read Section 5.5 through end of of Chapter 5 (stochastic games through end of chapter)


Rollouts are uses as part of Monte Carlo Tree Search but they are quite general and can be used for lots of situations with partially observable games (and they were invented before MCTS!).  

  • Watch the video on rollouts
  • Copy of the slides


Another way to handle stochastic games is to look at probabilities and expected values.  Unfortunately this causes the game tree to blow up in size very quickly!

  • Watch the video on Expectiminimax

Assignment and next topic

No assignment for this topic (but you may implement rollouts in your projects!).  Jump to the next topic on game search and ethics!