A Comparison of Algorithms for Multi-player Games

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.