Introduction to Artificial Inteligence - Spring 2001

Adversarial Games

1. Game playing as search
2. Perfect decision in 2-agent adversarial games
   • Problem definition: initial state, operators, terminal states, payoff (utility) function.
   • Minimax algorithm
3. Imperfect decisions
   • (Static) evaluation functions
   • Search cutoff
4. Alpha-beta pruning
   • Basic algorithm
   • Effectiveness of alpha-beta pruning
5. Multi-player games
6. Games with random elements
   • Adding chance nodes and expecti-minimax
   • Evaluation functions for chance games
   • Complexity of expecti-minimax
7. State of the art in game playing
   • Chess - Deep Blue world champion (1997)
   • Checkers - Chinook world champion (1994)
   • Othello (reversi)
   • Backgammon - championship level
   • Go - still not so good
   • Hex - interesting recent developments
   • Bridge - challenging domain, much to be done