Introduction to Artificial Inteligence - Spring 2001
BGU Computer Science Department
Adversarial Games
- Game playing as search
- Perfect decision in 2-agent adversarial games
- Problem definition: initial state, operators, terminal states,
payoff (utility) function.
- Minimax algorithm
- Imperfect decisions
- (Static) evaluation functions
- Search cutoff
- Alpha-beta pruning
- Basic algorithm
- Effectiveness of alpha-beta pruning
- Multi-player games
- Games with random elements
- Adding chance nodes and expecti-minimax
- Evaluation functions for chance games
- Complexity of expecti-minimax
- 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