Meeting 05: Games and Min-Max

Reading: AIAMA 5.1-5.2

This section of the text introduces our first look at multi-agent environments, ones in which two agents compete. This is explored through the use of simple two-player games. Section 5.1 specifies what kind of games we are considering and how they fit into state-space search. Section 5.2 introduces the overall idea behind two-player game search and a simple algorithm called minimax (or min-max).

Questions you should be able to answer after reading are:

  1. What kind of games does this chapter cover?
  2. How do games fit into the concept of state-space search?
  3. What is the game tree and the ply depth?
  4. How does the minimax algorithm determine a move in the game?
  5. When is the move optimal?
  6. What is the central assumption of optimality in minimax?