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