Nathan Sturtevant

Pathfinding | Multi-Player 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 "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.