Finding Optimal Strategies for Imperfect Information Games

Weexaminethree heuristic algorithms for gameswith imperfect information: Monte-carlo sampling, and two newalgorithms wecall vector minimaxingand payoffreduction minimaxing. Wecomparethese algorithms theoretically and experimentally, using both simple gametrees and a large database of problemsfrom the game of Bridge. Our experiments show that the new algorithms both out-perform Monte-carlo sampling, with the superiority of payoff-reduction minimaxing being especially marked. Onthe Bridge problemset, for example, Monte-carlo sampling only solves 66% of the problems, whereas payoff-reduction minimaxing solves over 95%. This level of performance was evengoodenoughto allowus to discover five errors in the expert text used to generate the test database.

Authors

• Ian Frank Electrotechnical Laboratory; David Basin

Keywords

No keywords are indexed for this paper.