Generating and Solving Imperfect Information Games

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 su ch 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 imperfe ct information competitive games [Koller et al., 1994]. 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.