
Pathfinding 
MultiPlayer Games :
Hearts,
Spades
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 "kingmaker" who cannot win the game, but can strongly influence
who wins the game. Some research areas in multiplayer games are below.
Search Algorithms
Until recently, the max^{n} algorithm has been the primary search
technique used to play multiplayer games. But, research in opponent modeling has
lead to two new algorithms, probmax^{n} and softmax^{n}.
The UCT algorithm has also been extended to, and shown to be effective in
multiplayer games.
Search Optimization
A lot of work
has gone into optimizing search for twoplayer games, but there are many
differences when we try to apply methods from twoplayer games to multiplayer
games.

A threeplayer game tree Unlike twoplayer games
we backup a ntuple 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
max^{n} 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 multiplayer games, as well as speculative pruning, an
analogous algorithm to alphabeta in twoplayer games. Additionally,
these techniques were used to write highquality
Hearts and Spades
programs.
In twoplayer games it has generally been seen that deep search is much
better than a broad, shallow search. However, in multiplayer 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 MultiPlayer 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.
 ProbMax^{n} : Opponent Modeling in NPlayer Games, Nathan Sturtevant, Michael Bowling, and Martin Zinkevich, AAAI06, Boston, MA.
 Robust Game Play Against Unknown Opponents, Nathan Sturtevant and Michael Bowling, pp 713719, AAMAS06, Hakodate, Japan.
 LeafValue Tables For Pruning NonZero Sum Games, Nathan Sturtevant, IJCAI05.
 Current Challenges in MultiPlayer Game Search, Nathan Sturtevant, Proceedings, Computers and Games 2004.
 Thesis: MultiPlayer Games: Algorithms and Approaches
 LastBranch and Speculative Pruning Algorithms for Max^{n}, Nathan Sturtevant, IJCAI '03.
 A Comparison of Algorithms for MultiPlayer Games, Nathan Sturtevant, Proceedings Computers and Games 2002.
 On Pruning Techniques for MultiPlayer Games, Nathan Sturtevant and Rich Korf, Proceedings
AAAI2000, July, 2000.
