|
|
|
My Pages at FUN |
|---|
|
|
|
Projects |
|
Payoff-reduction Minimaxing Ian Frank, David Basin, Hitoshi Matsubara Presented at the Fourth Game Programming Workshop in Japan, Pages 169--178, 1997 The version on these pages is an ETL Technical Report, ETL-TR-97-21
Abstract:We describe payoff-reduction minimaxing, a new search algorithm for games with incomplete information. We formalise this algorithm and present results that show it dramatically outperforms the major competing algorithm: Monte-carlo sampling. On simple game trees where Monte-carlo sampling is never able to identify an optimal strategy, payoff-reduction minimaxing has a success rate of up to 40%. Payoff-reduction minimaxing is designed for incomplete information games in which the opponent is assumed to know the state of the world. This is exactly the situation found in expert analysis of the game of Bridge. We analyse further simple game trees on which Monte-carlo sampling has the same success rate as it does for Bridge (about 65%). On these trees, payoff-reduction minimaxing has the even better success rate of 93%. |
