Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Why Games
Games are a useful and hard test for AI:
- abstraction: board games are a clean model of real conflicts (chess as an abstract war game), with an exact state space representation
- uncertainty: a hostile opponent acts to reduce our agent's well-being, so it is a contingency problem (the uncertainty comes from the opponent, not from random effects)
- complexity: chess has average branching factor about 35 and games of over 50 moves per player, so roughly positions
- time limits: a complete search for the optimal move is impossible, so search efficiency is crucial
Types of Games
| Deterministic | Chance | |
|---|---|---|
| Perfect information | chess, checkers, go, Othello | backgammon, Monopoly |
| Imperfect information | bridge, poker, Scrabble |
Definitions:
- perfect information: each player sees the opponent's position and all available choices
- deterministic: each step is fully set by the moves chosen, with no dice or card draws
Deterministic games with perfect information are the easiest to search.
Game as a Search Problem
| Component | Meaning |
|---|---|
| Initial state | starting board and who moves first |
| Operators | the legal moves |
| Terminal test | decides when the game is over (terminal states) |
| Utility (payoff) function | numeric score of a terminal state, e.g. win , draw , loss |
Game Tree
Players alternate between MAX (us) and MIN (opponent) levels. In tic-tac-toe MAX plays X and MIN plays O, and leaves carry utility , or . Utilities are always from MAX's point of view: MAX wants high values and MIN wants low values.
MAX picks its move with Minimax Search.