PERFECT RECALL AND PRUNING IN GAMES WITH IMPERFECT INFORMATION

Games with imperfect information are an interesting and important clas s of games. They include most card games (e.g., bridge and poker) as w ell as many economic and political models. Here we investigate algorit hms for finding the simplest form of a solution (a pure-strategy equil ibrium point) to imperfect information games expressed in their extens ive (game tree) form. We introduce to the artificial intelligence comm unity a classic algorithm, due to Wilson, that solves one-player games with perfect recall. Wilson's algorithm, which we call IMP-minimax, r uns in time linear in the size of the game-tree searched. In contrast to Wilson's result, Koller and Meggido have shown that finding a pure- strategy equilibrium point in one-player games without perfect recall is NP-hard. Here, we provide another contrast to Wilson's result-we sh ow that in games with perfect recall but more than one player, finding a pure-strategy equilibrium point, given that such an equilibrium poi nt exists, is NP-hard. Our second contribution is to present a pruning technique for Wilson's IMP-minimax algorithm to make the latter more tractable. We call this new algorithm IMP-alpha-beta. We provide a the oretical framework (model) and analyze IMP-alpha-beta in that model. I MP-alpha-beta is of direct value for one-player, perfect-recall games. It also has strong potential for other imperfect information games, a s it is a natural (but as yet untested) heuristic in those cases.