| Abstract | We derive a recursive formula for expected utility valuesin 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.
|
