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

DeterministicChance
Perfect informationchess, checkers, go, Othellobackgammon, Monopoly
Imperfect informationbridge, 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

ComponentMeaning
Initial statestarting board and who moves first
Operatorsthe legal moves
Terminal testdecides when the game is over (terminal states)
Utility (payoff) functionnumeric 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.