Multiplayer games: Algorithms and approaches.

摘要

Historically, much work in Artificial Intelligence research has gone into designing computer programs to play two-player perfect-information games such as Chess, Checkers, Backgammon, and Othello. Comparatively little work, however, has gone into multi-player games such as Chinese Checkers, Abalone, Cribbage, Hearts, and Spades. As a result, we have highly optimized techniques for two-player games, but very little knowledge of how they work in multi-player games.; In this thesis we extend many of the standard techniques from two-player games to multi-player games. We present two decision rules, maxn [Luckhardt and Irani, 1986] and paranoid, examining their theoretical properties. For maxn we also introduce several pruning techniques, including Alpha-Beta Branch-and-Bound pruning and Speculative pruning. Speculative pruning is the first multi-player pruning algorithm that can prune any constant-sum multi-player game, and provides an order of magnitude reduction in node expansions over previous search techniques in games like Chinese Checkers.; We also analyze the properties of common two-player game techniques, such as zero-window search and iterative deepening, showing how their properties change in multi-player games. Finally, we present results of all these techniques in a variety of multi-player domains, including Chinese Checkers, Abalone, Cribbage, Hearts and Spades. These methods have allowed us to write state-of-the-art programs for playing Hearts and a version of Chinese Checkers on a smaller board.