Games - AI

Games are a form of multi-agent environment

  • Cooperative or competitive
  • Competitive muti-agent environments give rise to adversarial search (or games)

Search — no adversary

  • Solution is (heuristic) method for finding goal
  • Heuristics and CSP techniques can find optima/ solution
  • Evaluation function: estimate of cost from start to goal through given node
  • Ex. path planning, scheduling activities

Games — adversary

  • Solution is strategy (strategy specifies move for every possible opponent reply).
  • Time limits force an approximate solution
  • Evaluation function: evaluate "goodness" of game position
  • Ex. chess, checkers, Othello, backgammon

Types of Games

Types of gamesDeterministicChance
Perfect Informationchess, checkers, go, othellobackgammon, monopoly
Imperfect Informationbattleships, blind tictactoebridge, poker, scrabble, nuclear war