Multi-Player Games :
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.
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
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
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
of node (a) is (1, 3, 5). Player 2 acts similarly at node (b) selecting the
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)
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
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
- 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.