Overconfidence or Paranoia? Search in Imperfect-Information Games

Abstract

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 for-mula and algorithm are general enough to incorporate a wide variety of opponent models. We analyze two opponent mod-els. The “paranoid ” model is an information-set analog of the minimax rule used in perfect-information games. The “over-confident ” model assumes the opponent moves randomly. Our experimental tests in the game of kriegspiel chess (an imperfect-information variant of chess) produced surpris-ing results: (1) against each other, and against one of the kriegspiel algorithms presented at IJCAI-05, the overconfi-dent 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 re-sults suggest that the usual assumption of perfect-information game tree search—that the opponent will choose the best pos-sible move—isn’t as useful in imperfect-information games.