Overconfidence or Paranoia? Search in Imperfect-Information Games

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Search and Game Playing

We derive a recursive formula for expected utility values in imperfect-information game trees, and an imperfect-information game tree search algorithm based on it. The formula and algorithm are general enough to incorporate a wide variety of opponent models. We analyze two opponent models. The "paranoid" model is an information-set analog of the minimax rule used in perfect-information games. The "overconfident" model assumes the opponent moves randomly. Our experimental tests in the game of kriegspiel chess (an imperfect-information variant of chess) produced surprising results: (1) against each other, and against one of the kriegspiel algorithms presented at IJCAI-05, the overconfident model usually outperformed the paranoid model; (2) the performance of both models depended greatly on how well the model corresponded to the opponent's behavior. These results suggest that the usual assumption of perfect-information game tree search—that the opponent will choose the best possible move—isn't as useful in imperfect-information games.