My home page
My group
Professional activities

Daphne Koller Publications

Generating and solving imperfect information games (1995)

by D. Koller and A. Pfeffer

Abstract: Work on game playing in AI has typically ignored games of imperfect information such as poker. In this paper, we present a framework for dealing with such games. We point out several important issues that arise only in the context of imperfect information games, particularly the insufficiency of a simple game tree model to represent the players' information state and the need for randomization in the players' optimal strategies. We describe Gala, an implemented system that provides the user with a very natural and expressive language for describing games. From a game description, Gala creates an augmented game tree with information sets which can be used by various algorithms in order to find optimal strategies for that game. In particular, Gala implements the first practical algorithm for finding optimal randomized strategies in two-player imperfect information competitive games [KMvS94]. The running time of this algorithm is polynomial in the size of the game tree, whereas previous algorithms were exponential. We present experimental results showing that this algorithm is also efficient in practice and can therefore form the basis for a game playing system.

Download Information

D. Koller and A. Pfeffer (1995). "Generating and solving imperfect information games." Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 1185-1192). pdf ps.gz

Bibtex citation

  title = {Generating and solving imperfect information games},
  author = {D. Koller and A. Pfeffer},
  booktitle = {Proceedings of the 14th International Joint Conference on
      Artificial Intelligence (IJCAI)}, 
  address = {Montreal, Canada}, 
  month  = {August},
  year = 1995, 
  pages = {1185--1192},

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal