Overconfidence or paranoia? Search in imperfect-information games

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 "over-confident" 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.