Abstract
The games research community has devoted little effort to investigating search techniques for stochastic domains. The predominant method used in these domains is based on statistical sampling. When full search is required, Expectimax is often the algorithm of choice. However, Expectimax is a full-width search algorithm. A class of algorithms were developed by Bruce Ballard to improve on Expectimax’s runtime. They allow for cutoffs in trees with chance nodes similar to how Alpha-beta allows for cutoffs in Minimax trees. These algorithms were published in 1983—and then apparently forgotten. This paper “rediscovers” Ballard’s *-Minimax algorithms (Star1 and Star2).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ballard, B.: The *-Minimax search procedure for trees containing chance nodes. Artificial Intelligence 21(3), 327–350 (1983)
Billings, D., Davidson, A., Schaeffer, J., Szafron, D.: The challenge of poker. Artificial Intelligence 134(1–2), 201–240 (2002)
Ginsberg, M.: GIB: Steps toward an expert-level bridge-playing program. In: International Joint Conference on Artificial Intelligence, pp. 584–589 (1999)
Hauk, T.: Search in trees with chance nodes. Master’s thesis, Computing Science, University of Alberta (2004)
Hauk, T., Buro, M., Schaeffer, J.: *-Minimax performance in backgammon. In: Cai, Y., Abascal, J. (eds.) Ambient Intelligence in Everyday Life. LNCS (LNAI), vol. 3864, pp. 51–66. Springer, Heidelberg (2006)
Michie, D.: Game-playing and game-learning automata. In: Fox, L. (ed.) Advances in Programming and Non-Numerical Computation, pp. 183–200. Pergamon, New York (1966)
Sheppard, B.: Towards Perfect Play of Scrabble. PhD thesis, Institute for Knowledge and Agent Technology (IKAT), Universiteit Maastricht (2002)
Tesauro, G.: Temporal difference learning and TD-Gammon. Communications of the ACM 38(3), 58–68 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hauk, T., Buro, M., Schaeffer, J. (2006). Rediscovering *-Minimax Search. In: van den Herik, H.J., Björnsson, Y., Netanyahu, N.S. (eds) Computers and Games. CG 2004. Lecture Notes in Computer Science, vol 3846. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11674399_3
Download citation
DOI: https://doi.org/10.1007/11674399_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32488-1
Online ISBN: 978-3-540-32489-8
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.