Heuristic Search

I am interested in anything to do with search algorithms that can be applied to games and puzzles, such as  alpha-beta, A*, and Monte-Carlo-based search. All our work is more generally applicable, but we prefer to use games and puzzles to demonstrate our research results. Some of our projects include:

Poker: We have developed strong poker-playing programs as part of our research into decision making in imperfect information domains. Our two-player limit Texas Hold'em program is super-human in its playing ability.

Go: Building a world-class 19x19 Go program remains challenging, but progress is being made. The Go research group is one of the top two or three teams in the world.

Hex: Interested in the mathematics of games? This project uses beautiful mathematics to help tame the game's complexity. The group is currently working on completely solving 9x9 Hex.

Checkers: Chinook is the World Man-Machine Checkers Champion. Chinook has been recognized by the Guiness Book of World Records as the first computer to win a human world championship in any game. In 2007, we announced that checkers was solved: perfect play leads to a draw.

Past results include the first super-human Othello program, Logistello, super-human programs at Lines of Action, world champions at computer billiards, and shogi (Japanese chess).

An important project is building a General Game-Playing (GGP) program, a program that can learn to play a game well, given only the set of rules). In the 2010 competition, our program, Maligne, came second.

Commercial Game AI

We have branched out to work on commercial games with our partners Electronic Arts and BioWare. Some of the projects we work on include:

ScriptEase: Easy-to-use scripting for the commercial games industry.

ORTS: an engine for real-time strategy games.

PaSSAGE: Player modeling and adaptive story generation.

Pathfinding: new algorithms for rapid and realistic pathfinding in commercial games.

Other Games

Pinball: We have a robotic pinball player. I am looking for someone to write the AI engine so that we can have a robotic pinball wizard.