Abstract:

Finding Optimal Strategies for Imperfect Information Games

Ian Frank and David Basin and H. Matsubara


We examine three heuristic algorithms for games with imperfect information: Monte-carlo sampling, and 
two new algorithms we call vector minimaxing and payoff-reduction minimaxing. We compare these algorithms
 theoretically and experimentally, using both simple game trees and a large database of problems from the 
game of Bridge. Our experiments show that Monte-carlo sampling is out-performed by both of the new 
algorithms, with the superiority of payoff-reduction minimaxing being especially marked. On the Bridge 
problem set, for example, Monte-carlo sampling only solves 66% of the problems, whereas payoff-reduction 
minimaxing solves over 95%. This level of performance was even good enough to allow us to discover five 
errors in the expert text used to generate the test database.