The University of Alberta GAMES Group

GAMES 
 Game-playing,
 Analytical methods,
 Minimax search and
 Empirical
 Studies

Projects | News | What We Do | People | Links | Publications | FTP directory

Projects
Checkers
Chinook is the official world checkers champion
Chess
TheTurk is a state of the art chess program.
Lines of Action
YL & Mona are the two best LOA programs in the world.
Hex
Queenbee is one of the two best Hex programs in the world.
Awari
Bambam is one of the strongest Awari entities in existence.
Poker
Poki is probably the strongest poker AI in the world.
Amazons
Antiope and Arrow are new contenders among the top Amazons programs.
Go
Explorer is a Go program written by expert Martin Müller.
Othello
Keyano is one of the world's top Othello programs.
RoShamBo
Home of the International RoShamBo Programming Competition
Sokoban
Rolling Stone pushes the boundaries of single agent search.
Shogi
ISshogi is the world computer Shogi champion.

GAMES Group News   (July, 2001)
The GAMES group is pleased to welcome another excellent researcher: professor Robert Holte. Dr. Holte is well known for his work in single agent search and combinatorial optimization, and he is the executive editor of the journal Machine Learning.
Mona has won the Fifth Annual Lines of Action E-mail Tournament with a perfect 14-0 score, including wins over most of the top human players in the world.   Complete details are available on the Lines of Action page.
New M.Sc. student Ling Zhao has done some interesting work on Post's Correspondence Problem (PCP), which is easy to state, but is undecidable in the general case.
Theodore Tegos has discovered a new Amazons position with a combinatorial game theory value of (nimber) *2. The first such position in any partizan game was found last year by Raymond Georg Snatzke, for an Amazons board with 8 empty squares. Theo's position has only 5 empty squares.
The ISshogi team of Tanase, Kishimoto, and Gotoh successfully defended their title at the 11th Computer Shogi World Championships held near Tokyo, Japan.   They scored a perfect 9-0 in the finals against the strongest qualifiers.   Congratulations!   Complete results.
Martin Müller is currently verifying his proof of a first player win in 5x5 Amazons.   The Amazons page has information about Martin's program Arrow, and Theodore Tegos's program Antiope, which you can now play against on the Amazons applet!   new
Queenbee has strongly solved the game of 6x6 Hex, giving the exact distance to mate for every possible position.   You can now browse many of the opening positions.
The Poker applet, Hex applet, Awari applet, Lines of Action applet, and now the Amazons applet are available.   Please send your feedback to Aaron Davidson at davidson@cs.ualberta.ca.
The results of the second International RoShamBo Programming Competition are available, and will be updated soon.  
The GAMES group had a strong presence at the Fifth Computer Olympiad, held in conjunction with the Mind Sport Olympiad.   The U of A competed in four events, winning one gold and three silver medals.   Several photographs are available at the MSO site.
One Jump Ahead, by Jonathan Schaeffer is the story of Chinook, the World Checkers Champion.   The book is available from Springer-Verlag.

What We Do
The GAMES research group produces high-performance, real-time programs for strategic game-playing. We employ a variety of techniques from many areas of computer science, including artificial intelligence, parallel processing, and algorithm analysis. Our primary goals are improvements in empirical performance, and applications to broader domains. Some of the major projects include:
  • Game-playing programs, with the goal of playing at or above the level of the best human players. Some of these programs include Chinook (checkers), YL and Mona (Lines of Action), Bambam (Awari), Queenbee (Hex), and Poki (poker). Chinook was the first computer program to win an official World Championship in a game of skill.

  • Sequential minimax search algorithms. This includes improvements to alpha-beta search efficiency, and new approaches to minimax search control.

  • Using heuristic knowledge. We are investigating new methods for discovering and using heuristic knowledge, such as data mining endgame databases for automatic feature identification and tuning of evaluation functions.

  • Handling imperfect information, and making decisions under conditions of uncertainty. This research includes probabilistic evaluation techniques, risk assessment, betting strategies, and opponent modeling.

  • Single-agent search. This research focuses on extending and enhancing the traditional single-agent search methods to handle much more complex domains with new search-space properties. For example, see the Sokoban home page.

  • Parallel alpha-beta search algorithms. New projects in parallel search have begun recently. Past projects include Mark Brockington's massively parallel asynchronous search engine, APHID.

  • Combinatorial game theory. This is a mathematical theory of games that can be analyzed as a sum of smaller independent subgames. We are implementing search algorithms that use this powerful divide-and-conquer approach for the analysis of games. Examples include "decomposition search" and "generalized thermography", which we are applying to endgames in Go and Amazons.

People

Faculty

Graduate Students

Research Associates

Recent Members

Related Links
  • Jürg Nievergelt's Research Group, at ETH Zürich in Switzerland has done some excellent work, and Thomas Lincke has written a cool Awari Endgame Database applet, that allows you to browse any position with up to 34 stones, with perfect knowledge.

  • The Computer Games Group, at Universiteit Maastricht in the Netherlands also studies heuristic search techniques and perfect domain knowledge for a variety of games.

  • The Complex Games Lab, at Electrotechnical Laboratory (ETL) in Japan is investigating many games, including Go, Shogi, Bridge, Othello, and RoboCup Soccer.

  • Logistello, written by Michael Buro, is the strongest Othello player in history. He has now retired the program, and is working on Amazons, among other things.

  • GIB, written by Matthew Ginsberg, is the strongest Bridge program in the world. It is the first program to play at the level of a human master, and is available commercially.

  • Proverb, written by a group from Duke University headed up by Michael Littman, is a program that solves crossword puzzles without understanding the clues. A crossword clue helper is available at oneacross.com.

  • Hexy, written by Vadim Anshelevich, is probably the best Hex program in the world. A very nice Windows version is also available.

  • Maven, written by Brian Sheppard, is a strong Scrabble ® program that appears to have surpassed the best human players. This is the AI in the commercial program by Hasbro.

  • The Mind Sports Olympiad is an annual event held in August in London, England. The Computer Olympiad is held in conjuction with this event. The MSO website is a massive collection news and information relating to games.

  • The International Computer Games Association publishes the ICGA Journal for game related research papers and tournament reports.

  • Richard's PBeM (play by e-mail) server hosts a wide variety of strategic board games, and attracts many skilled players.

  • Abstract Games is a new magazine devoted to lesser known strategic board games, like Hex and Lines of Action. The content and presentation are excellent!

Projects | News | What We Do | People | Links | Publications | FTP directory

You are visitor to this page since February, 1996.

[CS Department Home Page] [University of Alberta Home Page]

Last Modified:   July 11, 2001