Games with more than two players are fundamentally different from games with only two players (or two teams). Additional players allows opportunities for players to team up (explicitly or implicitly). Games with multiple players often have a "king-maker" who cannot win the game, but can strongly influence who wins the game. Some research areas in multi-player games are below.
Search Algorithms
Until recently, the maxn algorithm has been the primary search technique used to play multi-player games. But, research in opponent modeling has lead to two new algorithms, prob-maxn and soft-maxn. The UCT algorithm has also been extended to, and shown to be effective in multi-player games.
Search Optimization
A lot of work has gone into optimizing search for two-player games, but there are many differences when we try to apply methods from two-player games to multi-player games.
 |
|
A three-player game tree Unlike two-player games
we back-up a n-tuple of values, the utility of a position for each
each player. At a node where player i is to play, they select the
child with the value for which the ith value is maximum.
In this tree there are three players; the player to move is marked inside each node. At node (a), Player 2 is to move. Player 2 can get a score of 3 by moving to the left, and a score of 1 by moving to the right. So, Player 2 will choose the left branch, and the maxn value of node (a) is (1, 3, 5). Player 2 acts similarly at node (b) selecting the right branch, and at node (c) breaks the tie to the left, selecting the left branch. At node (d), Player 1 chooses the move at node (c), because 6 is greater than the 1 or 3 available at nodes (a) and (b). |
Major results from my thesis include a better analysis of pruning techniques for multi-player games, as well as speculative pruning, an analogous algorithm to alpha-beta in two-player games. Additionally, these techniques were used to write high-quality Hearts and Spades programs.
In two-player games it has generally been seen that deep search is much better than a broad, shallow search. However, in multi-player games this may not be the case. We have preliminary experimental evidence that shows many cases where it is better to do a broad search instead of a deep narrow search.
Publications
- An Analysis of UCT in Multi-Player Games, Nathan Sturtevant, Computers and Games 2008, Beijing, China
- Feature Construction for Reinforcement Learning in Hearts, Nathan Sturtevant and Adam White, Computers and Games 2006, Turin, Italy.
- ProbMaxn : Opponent Modeling in N-Player Games, Nathan Sturtevant, Michael Bowling, and Martin Zinkevich, AAAI-06, Boston, MA.
- Robust Game Play Against Unknown Opponents, Nathan Sturtevant and Michael Bowling, pp 713-719, AAMAS-06, Hakodate, Japan.
- Leaf-Value Tables For Pruning Non-Zero Sum Games, Nathan Sturtevant, IJCAI-05.
- Current Challenges in Multi-Player Game Search, Nathan Sturtevant, Proceedings, Computers and Games 2004.
- Thesis: Multi-Player Games: Algorithms and Approaches
- Last-Branch and Speculative Pruning Algorithms for Maxn, Nathan Sturtevant, IJCAI '03.
- A Comparison of Algorithms for Multi-Player Games, Nathan Sturtevant, Proceedings Computers and Games 2002.
- On Pruning Techniques for Multi-Player Games, Nathan Sturtevant and Rich Korf, Proceedings AAAI-2000, July, 2000.