Generating and Solving Imperfect Information Games
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 [Koller et al 1994]. The running time of this algorithm is palinomial 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.