Unit 3: Games and Adversarial Search

Commentary

This unit covers a class of problems involving adversarial multiagent environments, especially game playing. Computer games are very attractive, not only to game players, but also AI researchers. In fact, games have long been a major research branch in AI, and recently there has been some ground-breaking work in computer game design, including IBM's Deep Blue (https://www.ibm.com/ibm/history/ibm100/us/en/icons/deepblue/) and University of Alberta's Chinook (https://webdocs.cs.ualberta.ca/~chinook/). This unit introduces the problem descriptions and optimal strategies in games, and presents several important algorithms and techniques for solving game problems. You are also exposed to state-of-the-art game programs, as well as techniques for exploring your research interests.

Unit Purpose

When you complete this unit, you will be able to

• Outline the methods of adversarial search used to solve AI game playing problems.
• Analyse and implement minimax and alpha-beta pruning algorithms.
• Exemplify heuristic evaluation functions for pruning in adversarial search.
• Explain how to handle imperfect information in games.
• Describe the state-of-the-art game programs.

Section 1: Optimal decisions in games
Section 2: Adversarial search algorithms: Minimax and alpha-beta pruning
Section 3: Heuristics and imperfect information in adversarial search
Section 4: Recent game programs

Readings

Supplemental Unit Readings

Books:

Hsu, F.-H. (2002). Behind Deep Blue: Building the computer that defeated the world chess champion. Princeton, NJ: Princeton University Press. ISBN 0-691-09065-3 Schaeffer, J. (1997). One jump ahead: Challenging human supremacy in checkers. Berlin: Springer-Verlag.

Activities

• Explore the most recent game programs through the AAAI.org and ACM websites.
• Discuss the possibility of applying game programming in AI to the current computer games industry or Internet games.