Can we really solve a game optimally?  What does optimal mean?

Before we can dive into search methods for games, we need to look at how we formulate search for an adversarial situation as it is different than what we have been doing so far. We also need to discuss what an optimal solution means as many people assumes optimal solutions are always winning solutions (hint:  no, sometimes you can’t win a game!  Optimal is the best you can do given the information you have and assumptions about your opponent!)

The reading for this section is

• Sections 5.1-5.2.2 of Chapter 5 (Game Theory through Optimal Decisions in Games but don’t read about alpha-beta pruning)

Setting up a gaming problem

• How do we set up a game in the same way we setup search problems?  Watch the video on problem formulation for games.
  • Copy of the slides

Minimax Search

The optimal game search is called Minimax search.  This only works in small games which are fully observable but, as with DFS/BFS, it provides a foundation for our later searches on more complicated games!

• Watch the video on Minimax for 2 players
  • Copy of the slides
  • If minimax is confusing still, wikipedia has some additional examples that may be helpful!

It is often not feasible to fully solve a game tree.  Move to the next topic on pruning game searches!