Game Playing (COMP3411)

Origins

The important points in the history of game-playing agents include the following:

  • 1769 Wolfgang von Kempelen (Mechanical Turk)
  • 1846 Charles Babbage & Ada Lovelace (tic-tac-toe)
  • 1944 VOn Neumann (Perfect Play Algorithm)
  • 1952 Alan Turing (Chess algorithm) - First Chess Program
  • 1959 Arthur Samuel (Checkers) - Using ML (parameter tuning) to improve evaluation accuracy (as well as hash tables and data compression)
  • 1967 Donald Michie (Menace machine learner)

General Game Playing

General game players (as opposed to specific game players) are systems that don't know the rules of a game until it starts. They're designed to understand formal descriptions of any arbitrary game, and to learn to play those games effectively.

General game players are examples of systems that can adapt to radically different environments without human intervention.

Types of Games

There are two big differences in the types of games we can learn to play:

Discrete Games

  • Fully observable, deterministic
    • e.g. Chess, Checkers, Tic Tac Toe
  • Fully observable, stochastic
    • e.g. Monopoly
  • Partially observable
    • e.g. Poker

Continuous Embodied Games

E.g. Robocup Soccer

Partially Observable Games

Games like card games do not have all the information available to the player. In theory we can calculate a probability for each possible deal.

The current best Bridge program (GIB) computes the minimax value of each action in each deal (consistent with the knowledge we have) then chooses the action with the best average return.

Motivation to Create Game AI's

Why try to do this?

  • Unpredictable opponents mean the solution must have some kind of strategy (takes skill)
    • It has to respond to every possible opponent reply
  • Time limits mean there must be approximation
    • We have to learn tradeoffs between speed and accuracy
  • It's such a human thing to do, to play a game.
    • Many social, biological, political and economic processes can be formalised as multi-agent games.
  • They're fun!

Games have been a key driver of new techniques for searching and AI, because of this desire.

Representation

Instead of representing an entire state, if we represent features individually and describe how actions change these we can reduce the size of the storage.

Minimax Search

Minimax is an algorithm designed to maximise gain and minimise loss in the situation where both players make the optimal moves of a game.