Me
home
research
papers
activities
personal
links

Nathan Sturtevant

Pathfinding | Multi-Player Games : Hearts, Spades


As part of my efforts in multi-player game research, we have developed a program to play Hearts. Those unfamiliar with the game and the rules can find information on it and many other games at www.pagat.com. An older version of the program used custom node ordering with speculative pruning to seach monte-carlo generated opponent hands, making the move to minimize one's expected score. (See publications for more details.)

In 2003 we played a 90 game tournament against Freeverse Software's Hearts Deluxe hearts program. We played one of our players against three of the Hearts Deluxe players set at the highest strength. Players got -26 for shooting the moon, and games were played to 100 points. Card passing was not enabled. There results were:

average score/gameaverage score/hand
Our Program55.85.16
Hearts Deluxe75.16.98

A free program based on this research will soon be released at www.ns-software.com. This program is currently using monte-carlo sampling of opponents' hands with the UCT algorithm for play. The program handles shooting the moon much better than the previous program, although there are known problems with the monte-carlo hand generation. This currently is not based on good opponent modeling techniques, and is probably the next area in which the program will be improved.

Hearts-specific 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.
  • Last-Branch and Speculative Pruning Algorithms for Maxn, Nathan Sturtevant, IJCAI '03.
  • Thesis: Multi-Player Games: Algorithms and Approaches
  • 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.