PERFECT RECALL AND PRUNING IN GAMES WITH IMPERFECT INFORMATION1
Jean R. S. Blair, David Mutchler, Michael van Lent · Computational Intelligence · 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 findi ng the simplest form of a solution (a pure‐strategy equilibrium point) to imperfect information games expressed in their extensive (game tree) form. We introduce to the artificial intelligence community a classic algorithm, due to Wilson, that solves 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 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 show that in games with perfect recall but more than one player, finding a pure‐strategy equilibrium point, given that such an equilibrium point 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 theoretical framework (model) and analyze IMP‐alpha‐beta in that model. IMP‐alpha‐beta is of direct value for one‐player, perfect‐recall games. It also has strong potential for other imperfect information games, as it is a natural (but as yet untested) heuristic in those cases.