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.
|