Adversarial Agents

• turn taking, full information
  • Minimax
  • Alpha-Beta Pruning (P167 Russell & Norvig)
    • Alpha = best choice for Max so far on path to this node
    • Beta = best choice for Min so far on path to this node
    • if max > Beta then cutoff (because other player would choose beta move)
    • if min < Alpha then cutoff (because other player would choose alpha move)
• Partial information
  • Mixed strategies
  • Optimal mixed strategies
    • Linear programming solution
• Opponent Modelling
  • Just use (stochastic) RL
    • Fictitious play
    • Best response learning
    • WoLF
    • Does oscilation matter?