Abstract
The maxn algorithm for playing multi-player games is flexible, but there are only limited techniques for pruning maxn game trees. This paper presents other theoretical limitations of the maxn algorithm, namely that tie-breaking strategies are crucial to maxn, and that zero-window search is not possible in maxn game trees. We also present quantitative results derived from playing maxn and the paranoid algorithm (Sturtevant and Korf, 2000) against each other on various multi-player game domains, showing that paranoid widely outperforms maxn in Chinese checkers, by a lesser amount in Hearts and that they are evenly matched in Spades. We also confirm the expected results for the asymptotic branching factor improvements of the paranoid algorithm over maxn.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hsu, F.: Behind Deep Blue. Princeton University Press, Princeton (2002)
Schaeffer, J., Culberson, J., Treloar, N., Knight, B., Lu, P., Szafron, D.: A world championship caliber checkers program. Artificial Intelligence 53, 273–290 (1992)
Ginsberg, M.: GIB: Imperfect information in a computationally challenging game. Journal of Artificial Intelligence Research 14, 303–358 (2001)
Luckhardt, C., Irani, K.: An algorithmic solution of N-person games. In: Fifth National Conference of the American Association for Artificial Intelligence (AAAI 1986), pp. 158–162. AAAI Press, Menlo Park (1986)
Sturtevant, N., Korf, R.: On pruning techniques for multi-player games. In: Sixteenth National Conference of the American Association for Artificial Intelligence (AAAI 2000), pp. 201–207. AAAI Press, Menlo Park (2000)
Billings, D., Davidson, A., Schaeffer, J., Szafron, D.: The challenge of poker. Artificial Intelligence 134, 201–240 (2002)
Hoyle, E., Frey, R., Morehead, A., Mott-Smith, G.: The Authoritative Guide to the Official Rules of All Popular Games of Skill and Chance. Doubleday (1991)
Korf, R.: Multiplayer alpha-beta pruning. Artificial Intelligence 48, 99–111 (1991)
Knuth, D., Moore, R.: An analysis of alpha-beta pruning. Artificial Intelligence 6, 293–326 (1975)
Pearl, J.: Asymptotic properties of minimax trees and game-searching procedures. Artificial Intelligence 14, 113–138 (1980)
Ginsberg, M.: Partition search. In: Thirteenth National Conference of the American Association for Artificial Intelligence (AAAI 1996), pp. 228–233. AAAI Press, Menlo Park (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sturtevant, N. (2003). A Comparison of Algorithms for Multi-player Games. In: Schaeffer, J., Müller, M., Björnsson, Y. (eds) Computers and Games. CG 2002. Lecture Notes in Computer Science, vol 2883. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-40031-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-40031-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20545-6
Online ISBN: 978-3-540-40031-8
eBook Packages: Springer Book Archive