Nathan Sturtevant

Pathfinding | Multi-Player Games : Hearts, Spades

As part of my efforts on multi-player games, I've have a program that plays Spades and some of the variations of the game. (Currently not publically available.) If you are not familiar with this game or the variations discussed here, follow the links to get a more complete description of the rules and variations. We are mostly interested in the non-team versions of the game. So, with 3-players, or games that are related to Spades such as Sergeant Major (3-5-8), or Oh Hell! For convenience, when using the term Spades on this page, we are referring to this entire family of card games

Spades is a convenient game to play, because the game tends to allow many optimization techniques not available in games like Hearts. These optimizations generally buy us an extra trick (3-ply) of search depth when compared to Hearts. Specifically, it is a very uniform game, since each trick has the same value, 1 point, and the points are evenly distributed throughout the game. It is also easier to assume that we are trying to maximize our score, although that isn't always the case.

For instance, if we are using a paranoid strategy to play the game (assuming our opponents are ganging up against us - see the Pruning Techniques for Multi-Player Games paper for more information), and we are searching iteratively deeper by tricks, we are guaranteed that at each successive iteration our score will either increase by 1 or stay the same. This means that if you got a score of s at depth i, at depth i+1 you can treat all leaf nodes with a score of s+1 as a win, and everything else as a loss. If our search returns a win, we know how to achieve it. If it returns a loss, we can use our result from the previous search to achieve our previous score.

Using such techniques will allow us to easily search 30-ply into a perfect information hand using the paranoid algorithm. But, does that extra seach depth help? Apparently not, as when compared to algorithms such as a standard maxn implementation, there is no measurable difference in performance.

Such experiments have only been run in computer v. computer matches. We are hoping to be able to set up a server soon that will allow us to play many more games against human players to see how difference enhancements affect play against humans.

In many variations of Spades the goal isn't just to maximize the number of tricks taken. For instance, in Oh Hell! you try to make your bid exactly, while in Spades there is a delayed penalty for overtricks. This can thwart the technique discussed above, because we are no longer trying to maximize our score at each step of the game.

In this case it is very important to have some reasonable model of one's opponents that is flexible enough to recover or not make disastrous moves when our opponent model is incorrect. We have very promising results in this direction and will post more information here when available.

See Current Challenges in Multi-Player Game Search in the publications section for more detailed information on the current issues we are working on.