|
Abstract : |
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 point, given that such an equilibrium point exists, remains NP-hard, in games with more than a single player. Our second contribution is to present a pruning algorithm for Wilson's IMP-minimax algorithm to make the latter more tractable. We call this new, |
