CMPS140, Winter 2012, Section 01: Lecture 10

 

Def.   Commitment  =    cutting off possible (optimal solutions) during problem solving
                        (see aggressive)
Def.   Game Theoretic Value = "Worst Case Guarantee" for a perfect player.

Game tree search:
    See Minimax and Minimax Alpha-Beta in Chapter 5.
Minimax returns the game theoretic value and optimal move for the first (root) player
. Minimax Alpha-Beta does the same (but usually can prune about 1/2 the tree).

Note that what minimax returns may not be what is practically best!


Simultaneous games like RPS can be analyzed as payoff matrices:
  This matrix   
                 12
                 34  
      has a game theoretic value of 3 and both players strategies are fixed.

   This matrix   14
                 32     requires both players to play stochastically to  reach equilibrium.



Next time:  logic!