Dana Nau, Professor, Department of Computer Science and the Institute for Systems Research,
University of Maryland

Building and using game-theoretic agent models from observed behavior

Thursday, March 29, 4:00 PM

STEPS 101

Reception prior to talk at 3:30 PM in Packard Lobby

Abstract: One reason why AI programs have worked so well in games such as chess and checkers is that in these games, the game-theoretic notion of "rational choice" is an excellent model of the opponent. But the are other classes of games where the rational-choice model is less successful -- for example, if there are non-zero-sum outcomes, imperfect information, noisy observations, or more than two players. For two such classes of games, I will describe algorithms that construct other kinds of opponent models from observed behavior.

For the Iterated Prisoner's Dilemma with Noise (a non-zero-sum repeated game with noisy observations), our DBS algorithm builds and maintains a model of the other player's strategy, and uses this model to guide its decision-making. In a large international competition, our implementation of DBS scored higher than all but two other agents -- and the reason those agents scored higher was because several dozen "slave" agents deliberately conspired to raise the two agents' scores.

In multiplayer extensive-form games, where strategies tend to be much more complex, our SOS algorithm does not attempt to model the agents' strategies directly. Instead, using a concept borrowed from social psychology research, SOS builds models of the agents' social orientations, and uses these models to guide a game-tree search.  In experimental studies on the game of Quoridor, SOS performed significantly better than current state-of-the-art algorithms.

This work was done jointly with several talented students and postdoctoral researchers: Tsz-Chiu Au, Brandon Wilson, and Inon Zuckerman.


Bio: Dana Nau is a Professor in the Department of Computer Science and the Institute for Systems Research at the University of Maryland. He does research in Artificial Intelligence, especially the topics of game theory and AI planning, and he co-directs the Laboratory for Computational Cultural Dynamics. He is a Fellow of the Association for Advancement of Artificial Intelligence (AAAI), and has received dozens of other awards and honors.

Here are some of some of Dr. Nau's best-known accomplishments. (1) His discovery of game-tree pathology has led to subsequent research by dozens of other researchers over the past three decades. (2) A strategy-generation algorithm co-authored by him and one of his students enabled the Bridge Baron program to win the 1997 world championship of computer bridge, as reported in the Washington Post and other major media. (3) He led the development of the SHOP and SHOP2 automated-planning systems, which have been downloaded more than 13,000 times and have been used in many hundreds of projects in industry, government, and academia. (4) He co-authored a graduate-level textbook, Automated Planning: Theory and Practice, which has become the de facto standard textbook on its topic.

© 2012 Computer Science and Engineering, P.C. Rossin College of Engineering & Applied Science, Lehigh University, Bethlehem PA 18015.