Perfect Recall and Pruning in Games with Imperfect Information
Jean R. S. Blair, David Mutchler, Michael van Lent · 1996
Games with imperfect information are an interesting and important class of games. They include most card games (e.g., bridge and poker), as well as many economic and political models. Here, we investigate algorithms for solving imperfect information games expressed in their extensive (game-tree) form. In particular, we consider algorithms for the simplest form of solution --- a pure-strategy equilibrium point. We introduce to the artificial intelligence (AI) community a classic algorithm due to Wilson, that finds a pure-strategy equilibrium point in one-player games with perfect recall. Wilson's algorithm, which we call IMP-minimax, runs in time linear in the size of the game-tree searched. In contrast to Wilson's result, Koller & 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 show that in games with perfect recall, finding a pure-strategy equilibrium p...