A theoretical and empirical investigation of search in imperfect information games

We examine search algorithms for games with imperfect information. We first investigate Monte Carlo sampling, showing that for very simple game trees the chance of finding an optimal strategy rapidly approaches zero as size o f the tree increases. We identify the reasons for this sub-optimality, and show that the same problems occur in Bridge, a popular real-world imperfect information game. We then analyse the complexity of the underlying problem , proving it to be NP-complete and describing several polynomial time heuri stics. We evaluate these heuristics theoretically and experimentally, demon strating that they significantly out-perform Monte Carlo sampling. Indeed, on a set of Bridge problems drawn from a definitive expert text, our heuris tics consistently identify strategies as good as, or superior to, the exper t solutions - the first time a game-general tree search algorithm has been capable of such performance. (C) 2001 Elsevier Science B.V. All rights rese rved.