On Pruning Techniques for Multi-Player Games

Nathan R. Sturtevant and Richard E. Korf. University of California, Los Angeles

Maxn is the extension of the minimax backup rule to multi-player games. We have shown that only a limited version of alpha-beta pruning, shallow pruning, can be applied to a maxn search tree. We extend this work by calculating the exact bounds needed to use this pruning technique. In addition, we show that branch-and-bound pruning, using a monotonic heuristic, has the same limitations as alpha-beta pruning in a maxn tree. We present a hybrid of these algorithms, alpha-beta branch-and-bound pruning, which combines a monotonic heuristic and backed-up values to prune even more effectively. We also briefly discuss the reduction of a n-player game to a CEparanoid 2-player game. In Sergeant Major, a 3-player card game, we averaged node expansions over 200 height 15 trees. Shallow pruning and branch-and-bound each reduced node expansions by a factor of about 100. Alpha-beta branch-and-bound reduced the expansions by an additional factor of 19. The 2-player reduction was a factor of 3 better than alpha-beta branch-and-bound. Using heuristic bounds in the 2-player reduction reduced node expansions another factor of 12.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.