Finding Optimal Strategies for Imperfect Information Games
Abstract
We examine three heuristic algorithms for games with imperfect information: Monte-carlo sampling, and two new algorithms we call vector minimaxing and payoffreduction 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.
Cite
Text
Frank et al. "Finding Optimal Strategies for Imperfect Information Games." AAAI Conference on Artificial Intelligence, 1998. doi:10.1016/s0091-6749(99)70403-3Markdown
[Frank et al. "Finding Optimal Strategies for Imperfect Information Games." AAAI Conference on Artificial Intelligence, 1998.](https://mlanthology.org/aaai/1998/frank1998aaai-finding/) doi:10.1016/s0091-6749(99)70403-3BibTeX
@inproceedings{frank1998aaai-finding,
title = {{Finding Optimal Strategies for Imperfect Information Games}},
author = {Frank, Ian and Basin, David A. and Matsubara, Hitoshi},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1998},
pages = {500-507},
doi = {10.1016/s0091-6749(99)70403-3},
url = {https://mlanthology.org/aaai/1998/frank1998aaai-finding/}
}