Home Page


My Pages at FUN

Publications

Misc AI Links

My Weather


Projects

FINESSE

MIKE


A Theoretical and Empirical Investigation of Search in Imperfect Information Games

Ian Frank, David Basin

Theoretical Computer Science, 252 (2001) Pp 217-256

Abstract:

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 of 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 heuristics. We evaluate these heuristics theoretically and experimentally, demonstrating that they significantly out-perform Monte Carlo sampling. Indeed, on a set of Bridge problems drawn from a definitive expert text, our heuristics consistently identify strategies as good as, or superior to, the expert solutions --- the first time a game-general tree search algorithm has been capable of such performance.

Viewable With Any Browser