GAMES

The University of Alberta GAMES Group

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

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

Announcements
  • GAMES group meetings are often from 4-5pm on Thursdays at CSC333.

Projects

Checkers
Chinook is the official world checkers champion.
Poker
Poki is the strongest poker AI in the world.

Lines of Action
YL & Mona are two of the best LoA programs in the world.

Hex
Queenbee is one of the best Hex programs in the world. Research on computer Hex is ongoing.
Go
The Computer Go group has developed the top program Fuego.
Real-Time Stategy
We are trying to apply AI to real-time stategy games.
Othello
Logistello defeated the human world Othello champion, 6-0, in 1997. Keyano is another strong program.
Sokoban
Rolling Stone pushes the boundaries of single agent search.
RoShamBo
Home of the International RoShamBo Programming Competition
Amazons
Three programs, and several theoretical contributions.
Spades & Hearts
Spades & Hearts are the test beds for the research on multi-player games.
Shogi
ISshogi has won the world computer Shogi championship many times (currently inactive).
Real-time Heuristic Search
We are developping heuristic search methods where the planning time per action is limited.
Emotion and Culture Modeling
It is important to understand the role of emotions in intelligence both theoretically and practically.
Player Modeling and Adaptive Story Generation
We explore interactive storytelling and player modelling in video games.
Hide and Seek
We are investigating hide and seek human behavior in a pen-and-paper as well as a 3D environment created with the Source engine.
Previous Projects:

Chess

Awari

Chinese Chess

Post's Correspondence Problem

Domineering

Applied Research
Electronic Arts
We are working with EA Sports on the AI for their popular FIFA Soccer game.
BioWare
We are working on intelligent path-finding and on NPCs in games such as Baldur's Gate.
Sequence Alignment
We have developed fast algorithms for Optimal Sequence Alignment for DNA and proteins.
Scripting languages
We are developing scripting languages for computer role-playing games such as BioWare's Neverwinter Nights.
Pathfinding
We have explored both theoretically and empirically for pathfinding in commercial games.
Team Intelligence in On-line Tactical Games
We are investigating methods for analyzing and building human-level team intelligence using the testbed of Counter-Strike.

GAMES Group News
Wolve and MoHex win gold and silver again at the 14th Computer Games Olympiad in Pamplona, Spain. (May 18, 2009)
Fuego wins gold on 9x9 and silver on 19x19 at the 14th Computer Games Olympiad in Pamplona, Spain. (May 18, 2009)
Wolve and MoHex win gold and silver at the 13th Computer Games Olympiad in Beijing ahead of three-time gold medallist Six. (October 5, 2008)
Mike Smith won the gold medal of Computer Billiards tournament again in the 11th Computer Olympiad, held in Turin, Italy. (July 1, 2006)
In the 10th Computer Olympiad in Taiwan, Mike Smith won the gold medal in the Computer Billiards tournament. (September 9, 2005)
The University of Alberta checkers project has won the International Joint Conference on Artificial Intelligence (IJCAI) 2005 Distinguished Paper Award. The paper, entitled "Solving Checkers", by Jonathan Schaeffer, Yngvi Bjornsson, Neil Burch, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu and Steve Sutphen, was one of three papers to be awarded the honour (from over 1500 submission). (May 29, 2005)
In January 2005, the first milestone in solving the game of checkers was achieved. The infamous White Doctor opening has been proven to be a draw. (January 18, 2005)
New Scientist, "The World's No.1 Science & Technology Magazine", has a feature article on the U of A Computer Poker Research Group in their 2003 year-end double issue (pages 64-68). (January 7, 2004)
A commercial poker package has been released, featuring the AI developed by our Computer Poker Research Group. Visit http://www.poker-academy.com/ for more information about Poker Academy. (Dec 11, 2003)
In the 8th Computer Olympiad, the U of A GAMES group won a medal in almost every game it participated in: Vexbot and Sparbot developed by the Computer Poker Research Group took both gold and silver medals in Poker, NeuroGo by Markus Enzenberger won a silver medal in 9x9 Go, and so did Mongoose by Ryan Hayward's team in Hex, and ISShogi by Akihiro Kishimoto and his colleagues in Shogi. (November 27, 2003)
The University of Alberta Computer Poker Research Group has won the International Joint Conference on Artificial Intelligence (IJCAI) 2003 Distinguished Paper Award. The paper, entitled Approximating Game-Theoretic Optimal Strategies for Full-scale Poker, by Darse Billings, Neil Burch, Aaron Davidson, Terence Schauenberg, Robert Holte, Jonathan Schaeffer, and Duane Szafron, was one of two papers to be awarded the honour. (Aug 9, 2003)
Isshogi, developed by Yasushi Tanase, Norifumi Gotou, and Akihiro Kishimoto won the 13th World Computer Shogi Championship. Isshogi won with a score of 6-1 on a tiebreak ahead of YSS. More information is available at the website. (May 5, 2003)
There are two games-related graduate courses taught in academic year 2002-2003: CMPUT 657 by Jonathan Schaeffer and CMPUT 605 by Michael Buro. (Apr 4, 2003)
Isshogi, developed by Akihiro Kishimoto and his colleagues, won the Computer Shogi Championship in the 2nd International Shogi Forum. The program shared the title with another program, YSS, authored by Hiroshi Yamashita. More information is available at the forum website. (Oct 25, 2002)
The U of A Games Group members were actively involved in the 3rd International Conference on Computers and Games (CG'2002). Yasushi Tanase gave an invited talk on Computer Shogi, and Michael Buro, Martin Müller, Adi Botea and Ling Zhao gave paper presentations. (Aug 6, 2002)
The 3rd International Conference on Computers and Games (CG'2002), the two workshop on Game Informatics and Agents in Computer Games, and the 21st Century Championship Cup and Trading Agent Competition (TAC 2002) were successfully completed. (Aug 6, 2002)
The 21st Century Championship Cup computer Go competition was held in Edmonton. David Fotland's Many Faces of Go won the Cup wonderfully without losing a game. Here is the tournament crosstable. An article titled In an Ancient Game, Computing's Future from the New York Times discussed Computer Go and also covered this competition. (Aug 6, 2002)
Akihiro Kishimoto and Jonathan Schaeffer's paper Transposition Table Driven Work Scheduling in Distributed Game-Tree Search was awarded the Best Paper Prize at the Fifteenth Canadian Conference on Artificial Intelligence (AI'2002). (July 28, 2002)
The 3rd International Conference on Computers and Games (CG'2002) was held July 25-27, 2002 at the University of Alberta, Edmonton, Canada.
Yasushi Tanase and Akihiro Kishimoto's program Isshogi won the gold medal at the Seventh Computer Olympiad. Congratulations! Here are the complete game results. (July 21, 2002)
Yngvi Bjornsson's Line of Action program YL has defended its gold medal at the Seventh Computer Olympiad, held in Maastrict, The Netherlands. It is the third time the program has won the title. Mona, the 2001 E-mail World Champion, did not compete. For more information, please view the game results. (July 9, 2002)
The game of Awari has been solved, by John Romein and Henri Bal at the Free University in Amsterdam, Netherlands. With perfect play, Awari is a draw. (July 2, 2002)

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), Logistello (Othello), YL and Mona (Lines of Action), SoftWari (Awari), Queenbee, Wolve and MoHex (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. Robert Holte investigates fundamental principles and results in single-agent search (puzzle games), some of which build on previous work by Jonathan Schaeffer and Joe Culberson. Past GAMES group research has focused on extending traditional methods to handle much more complex domains, with challenging new properties. For example, see Andreas Junghann's Sokoban page.

  • Parallel alpha-beta search algorithms. Recent projects in parallel search include Akihiro Kishimoto's M.Sc. thesis on transposition table driven search. 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.

  • Planning. The area of planning is being overtaken by search-based approaches. We are applying tight algorithms for planning in single-agent search (Adi Botea on standard planning benchmarks and Sokoban), and high-level planning in Go.

  • Learning and adaptation. Many of the current research topics address learning and adaptation in games and search domains. This has always been a major topic in computer poker, but is equally important in commercial entertainment games, among others.

  • Commercial games. In addition to learning and adaptation, we are also interested in high-level architectures for AI in commercial games, and applying certain AI techniques such as good path-finding for real-time stategy games, and scripting languages for plot-based games. Also, the IRCL research group is working on many interesting research projects to improve AI in video games.

  • Applications. We are applying our heuristic search expertise to solving optimization problems in civil engineering. David O'Connell is working on automating the layout of storm and sanitary sewers in the design of a subdivision.

People

Faculty

Graduate Students

Research Staff

Research Associates

Recent Members

Related Links

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

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

You are the No. visitor to this page since February, 1996.
Last Modified:   April 2, 2006.
Please send advice and comments to the webmaster.