Nathan Sturtevant

Pathfinding | Multi-Player Games : Hearts, Spades

Heuristic search is a broad domain encompassing single-agent, two-player, and multi-player search. I have made research contributions to a variety of areas within heuristic search, including applications in commercial video games, learning, and multi-player games. General areas of research are described below.

Multi-Player Games
There have been large and well-known successes in writing computer programs to play two-player games, but the task of playing a game with more than two players or teams is much more difficult. While research in two-player zero-sum games has become slightly isolated from general AI research, the problems faced in multi-player games are common to many other current domains.

In multi-player games, we cannot escape a need for an opponent model. If our opponent model is inaccurate, we will need to be able to learn details of our opponents play. But, the process of search has also proved to work surprisingly well. Thus, we see a need to not only investigate search techniques, but also how techniques being develope in areas such as multi-agent learning can be used effectively on real problems.

My current efforts include work in optimizing search techniques to minimize tree size, using more advanced opponent models in game trees.

I have investigated learning techniques in the context of multi-player games. These include techniques both for learning how to play games well, as well as learning about the strategies of one's opponents.

Pathfinding and Search
Pathfinding is an important task in games and robotics. I will be giving a tutorial on pathfinding with Sven Koenig and Michael Buro at AAAI 2008

Other work on pathfinding include cooperative pathfinding and research on inconsistent heuristics. I implemented the pathfinding engine for BioWare on their upcoming game Dragon Age.

HOG (Hierarchical Open Graph) is a framework which I've written that provides a simple environment for testing and visualizing algorithms before implementing them in ORTS. HOG is currently being used by myself and other researchers at the Univeristy of Alberta as a testbed for multi-agent environments, pathfinding, abstraction and learning.

ORTS is an Open Real-Time Strategy game framework. I used to maintain the OS X port.