|
|
|
My Pages at FUN |
|---|
|
|
|
Projects |
|
Finding Optimal Strategies for Imperfect Information Games Ian Frank, David Basin, Hitoshi Matsubara Presented at the Fifteenth National Conference on Artificial Intelligence, AAAI-98. Please note that the AAAI copyright agreement allows authors (but only authors) to post their papers on a Web or ftp site.
Abstract: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 the new algorithms both out-perform Monte-carlo sampling, 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. |
