Games & Puzzles

AI Technology in the Computer Game World

AITopics > Games & Puzzles

"There are two principal reasons to continue to do research on games ... First, human fascination with game playing is long-standing and pervasive. Anthropologists have catalogued popular games in almost every culture....Games intrigue us because they address important cognitive functions....The second reason...is that some difficult games remain to be won, games that people play very well but computers do not. These games clarify what our current approach lacks. They set challenges for us to meet, and they promise ample rewards. - Susan L. Epstein, Game Playing: The Next Moves

Susan Epstein

Why are games fun? In part, because they challenge our ability to think. Even simple games like Tic-Tac-Toe, Nim and Kalah, or puzzles like the Eights Puzzle, are challenging to children. More complex games like checkers, chess, bridge, and Go are difficult enough that it takes years for gifted adults to master them. Nearly all games require seeing patterns, making plans, searching combinations, judging alternative moves, and learning from experience, all being skills which are also involved in many daily tasks.

It's no surprise that Alan Turing proposed chess playing as a good project for studying computers' ability to reason. In many ways, games have provided simple proving grounds for many of AI's powerful ideas.

Good Starting Places

COMPUTER GAME PLAYING: BEATING HUMANITY AT ITS OWN GAME by Daphne Koller, Stanford University, and Alan Biermann, Duke University. From Computer Science: Reflections on the Field, Reflections from the Field (2004), Computer Science and Telecommunications Board (CSTB), Section 6. "... This story teaches us very much about game playing. But it also teaches us about the nature of computation and the nature of human problem solving. Here are some of the major lessons:

• Our intuitions and thoughtful insights into a process as complicated as playing one of these board games are very unreliable. ...
• The process of decision making in games is vastly more complex than we imagined. ...
• It is not always the case that to achieve human-level performance, a computer should use the same techniques that a human does. ...
• Rather than designing a program in its entirety, it may be better to let the computer learn for itself. ...
• The research in game playing over the years has had ramifications for many other areas of computing. ..."

A Gamut of Games, Jonathan Schaeffer, AI Magazine, volume 22, number 3, pp. 29-46, 2001. An overview of progress in the classic board and card games. "...In Shannon's time, it would have seemed unlikely that only a scant 50 years would be needed to develop programs that play world-class backgammon, checkers, chess, Othello, and Scrabble. These remarkable achievements are the result of a better understanding of the problems being solved, major algorithmic insights, and tremendous advances in hardware technology. Computer games research is one of the important success stories of AI. This article reviews the past successes, current projects, and future research directions for AI using computer games as a research test bed." //A more technical version of this material can be found in Chips Challenging Champions, Schaeffer and van den Herik (eds), Elsevier, 2001.

AI Game Programming Wisdom from Charles River Media -- this is an ongoing series of books with short articles by commercial game practitioners on how they do AI in their games.

AI Game Dev -- a site where many commercial game developers hang out and contribute content. Articles, Forums, Notices and more.

Behind Deep Blue:Building the Computer that Defeated the World Chess Champion, Feng-hsiung Hsu. Book available from Amazon. Not available online.

One Jump Ahead: Computer Perfection at Checkers, Jonathan Schaeffer. Book available from Amazon. Not available online.

General Readings

Game Playing: The Next Moves. By Susan L. Epstein. 1999. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 987 - 993. Menlo Park, Calif.: AAAI Press. "This paper summarizes the role of search and knowledge in game playing, the state of the art, and recent relevant data on expert human game players. It then shows how cognitive skills can enhance a game-playing program, and poses three related challenge problems for the AI community. Although rooted in game playing, these challenges could enhance performance in many domains."

• See our History page for more information about The Dartmouth Conference.

Artificial Intelligence, January 2002 (Volume: 134, Issue: 1-2). Here are just a few of the articles that can be found in this issue: Games, computers, and artificial intelligence; A probabilistic approach to solving crossword puzzles; Deep Blue; Computer Go; World-championship-caliber Scrabble; and, Games solved: Now and in the future. Bibliographic pages (some include an abstract) for each article can be accessed by non-subscribers.

Challenges in Game Artificial Intelligence Papers from the 2004 AAAI Workshop. Dan Fu, Stottler Henke, and Jeff Orkin, Program Cochairs. "The science of game development is still in its infancy. While researchers and developers seek a better understanding and awareness of game AI problems and techniques, dialog between these two communities is limited. This workshop sought to identify the problems currently facing game AI programmers, to explore the emerging techniques within development circles, and to highlight AI research that could be of potential use."

Playing with AI. Edited by Haym Hirsh. IEEE Intelligent Systems, November / December 1999. Available free to subscribers or for purchase. "The essays in this 'Trends and Controversies' feature make it clear that success in games and puzzles requires more than minimax or A* search and a fast computer, and that puzzles and games can still play an important role in AI research."

When computers play games, artificial intelligence is the key to victory. By Kendall Madden. Stanford News Service (June 20, 2005). "From mahjong to Monopoly, bridge to Bingo, Sorry to Scrabble -- games are serious fun. And with their diverse rules, they're also the perfect tools for exploring concepts in artificial intelligence (AI) and new approaches to programming, say Stanford computer scientists. 'Programs that think better should be able to win more games,' wrote Michael Genesereth, computer science professor with the Stanford Logic Group, and Nathaniel Love, a computer science doctoral student, in an article on general game playing (GGP) to be published in the summer 2005 issue of AI Magazine. The concept of general game playing is 'drastically different,' Genesereth said, from the computer programming done in the past to create programs like IBM's Deep Blue, which beat world chess champion Gary Kasparov in 1997. ... But the research is not just about games. The philosophy underneath GGP -- that a computer program should be able to adapt with different information and make independent decisions -- has wide application. Business management would be one sector that Genesereth thinks would especially benefit from this revolution in programming."

AI Magazine 26(2): Summer 2005, 62–72. "A general game playing system is one that can accept a formal description of a game and play the game effectively without human intervention. Unlike specialized game players, such as Deep Blue, general game players do not rely on algorithms designed in advance for specific games; and, unlike Deep Blue, they are able to play different kinds of games. In order to promote work in this area, the AAAI is sponsoring an open competition at this summer’s Twentieth National Conference on Artificial Intelligence. This article is an overview of the technical issues and logistics associated with this summer’s competition, as well as the relevance of general game playing to the long range-goals of artificial intelligence."

• Also see:
  • Producing the ultimate game-playing bots. By Celeste Biever. New Scientist (July 29, 2006; Issue 2562, subscription req'd). "Last week [Michael Genesereth] organised the second General Game Playing competition at the annual conference of the American Association for Artificial Intelligence (AAAI) in Boston. The winner, a bot called Fluxplayer, earned its creators Stephan Schiffel and Michael Thielscher at the Dresden University of Technology in Germany a $10,000 prize."

• Icelanders world champions in artificial intelligence. Iceland Review (July 28, 2007). "Dr. Yngvi Björnsson and student Hilmar Finnsson from Reykjavík University (RU) won the international General Game-Playing (GGP) Competition at the AAAI Conference in Vancouver, Canada, this week. The conference is one of the largest and most prestigious artificial intelligence (AI) conferences in the world and the GGP Competition, held for the third time this year, is one of several side events at the conference. ... The AAAI GGP Competition was founded by Stanford University with the purpose of encouraging research in the field of artificial intelligence. Software entered in the competition is designed to play nearly all games, unlike conventional gaming software."
  • Meet the winner: CADIAPlayer, the game-playing software agent from the Center for Analysis and Design of Intelligent Agents (CADIA) at Reykjavik University.

• Computers master the game board - They reign supreme in checkers and chess. Poker may be next. What other areas will artificial intelligence soon dominate? By Chris Gaylord. The Christian Science Monitor (August 8, 2007). "On July 24, Polaris lost a close match against two top poker players. After two days and 4,000 hands of limit Texas hold em, the computer was behind by only about 30 bets. 'It was a tough opponent,' says Ali Eslami, one of the two poker pros who beat Polaris. 'To tell you the truth, if I had the chance to face it again right now for money, I wouldn't. There are easier humans out there. I'll stick with them.' The encroachment of lifeless data crunchers into our favorite pastimes marks more than just a countdown until computers are better at virtually everything. Any tabletop defeat is also milestones in the advancement of artificial intelligence. ... Some games are still too complicated for computers to master. The Japanese game of Go stands as the usual example. ... 'They've done eye tracking on Go experts,' says Susan Epstein, a computer science professor at Hunter College in New York City. 'The studies found that while there are hundred of good moves in front of them, the best [human] players only see three or four.' So how do you teach computers to 'see' what humans see? For one, stop relying on programs that simply map out a single game, suggests Michael Genesereth, director of the Logic Group at Stanford University in Stanford, Calif. ... [H]e researches general gaming, where machines learn patterns and principles that work in a variety of puzzles. At the same conference where Polaris battled human opponents, Genesereth held his annual machine-on-machine championship. The competition pitted general-gaming programs against one another in a series of board game mash-ups. May the best code win."

AI Game-Playing Techniques. By Dana S. Nau. AI Magazine 20(1): Spring 1999, 117-118. "In conjunction with the American Association for Artificial Intelligence’s Hall of Champions exhibit, the Innovative Applications of Artificial Intelligence held a panel discussion entitled 'AI Game-Playing Techniques: Are They Useful for Anything Other Than Games?' This article summarizes the panelists’ comments about whether ideas and techniques from AI game playing are useful elsewhere and what kinds of game might be suitable as 'challenge problems' for future research."

Two overview articles from Science News written by Ivars Peterson:

• Playing Your Cards Right - Poker comes out of the back room and into the computer science lab. (July 18, 1998)
• Silicon Champions of the Game - Computers have conquered tic-tac-toe, checkers, and chess. What's next? (August 2, 1997)
• Also listen to this interview with Jonathan Schaeffer: Computers and Poker? You Bet. Podcast (July 26, 2005). "[Jonathan Erickson of] Dr. Dobb's Journal discusses the high-stakes world of computers and Poker with Jonathan Schaeffer, leader of the University of Alberta's Computer Poker Research Group. Computers are getting better, but are they up to taking the best human players to the bank on a regular basis?"

Subtopics

• Arimaa
• Bridge
• Checkers
• Chess
• Crossword Puzzles
• Go
• Hex (orig. Nash)
• Jeopardy (TV Quiz Show)
• Othello
• Poker
• Rubik's Cube
• Scrabble
• Traveling Salesperson & NP-Complete Problems
• More Games & Puzzles
• ... and Applications: Video Games, Toys, Pets & Entertainment

Related Resources

AI on the Web: Search and Game Playing. A resource companion to Stuart Russell and Peter Norvig's "Artificial Intelligence: A Modern Approach" with links to reference material, people, research groups, books, companies and much more.

Bibliography on Machine Learning in Strategic Game Playing. Maintained by Johannes Furnkranz, University of Vienna. [Part of The Collection of Computer Science Bibliographies.] "This bibliography contains a variety of references concerning Machine Learning in Strategic Game Playing, i.e. on ideas how game playing programs can improve their play by learning from their own or others' experience. Included in the list are only references in which the application of a Machine Learning algorithm to a game playing problem forms a considerable part of the paper."

Boston University's Interactive WWW Games. Boston University Scientific Computing and Visualization Group. Can you beat the computer in Tic-Tac-Toe?

CRESS: "The Centre for Research in Social Simulation (CRESS), based in the Department of Sociology in the School of Human Sciences at the University of Surrey, is a multidisciplinary centre bringing together the social sciences, software engineering and agent-based computing to promote and support the use of social simulation in research in the human sciences. ... What is social simulation? There is growing interest in using computer simulation to explore issues in the social sciences. Simulation is a novel research method in most parts of the social sciences, including sociology, political science, economics, anthropology, geography, archaeology and linguistics. It can also be the inspiration for new, process-oriented theories of society. Learn about social simulation: See Agent-based social simulation: dealing with complexity (PDF), by Nigel Gilbert," from which this excerpt is taken:

• "While the idea of computer simulation has had enormous influence on most areas of science, and even on the public imagination through its use in computer games such as SimCity, it took until the 1990s for it to have a significant impact in the social sciences. The breakthrough came when it was realised that computer programs offer the possibility of creating ‘artificial’ societies in which individuals and collective actors such as organisations could be directly represented and the effect of their interactions observed. This provided for the first time the possibility of using experimental methods with social phenomena, or at least with their computer representations; of directly studying the emergence of social institutions from individual interaction; and of using computer code as a way of formalising dynamic social theories."
• Also see our Social Science page.

Game Developers AI Special Interest Group. International Game Developers Association. "The main purpose of the Game AI SIG is to talk about Artificial Intelligence in games - its implementation, problems, purpose, technology, etc. We want to talk about what developers are doing, what technical problems they face, what games they think have great AI, what tools they're using to build the AIs for their next games."

GAMES Group at the University of Alberta. "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." Visit the site and you'll find several games you can play online as well as their link to an extensive collection of publications.

"Game Theory .net provides resource material [including lecture notes, news, games, dictionary, interactive materials and links to journals] to educators and students of game theory and its applications to economics, business, political science, computer science, and other disciplines. Primarily, the site is directed at less rigorous presentations of the material, concentrating more on making the lessons of game theory relevant to the student. Administered by Mike Shor and hosted at the Owen Graduate School of Management at Vanderbilt University."

• Also see Game Theory on our Multi-Agent Systems page.

General Game Playing Project: "The General Game Playing Project is a research project of the Stanford Logic Group, part of the Stanford University Computer Science Department. Our AI Magazine article describes the General Game Playing concept and the AAAI GGP competition; a brief GGP Overview is also available. The GGP website contains information the Logic Group's research in general game playing, and forms the central resource for General Game Playing Competitions, the first of which was held at AAAI '05 in Pittsburgh. The website also hosts a GGP Game Manager, allowing General Game Players to connect and play single or multi-player games online, in order to help prepare for future competitions."

Machine Learning in Games. Maintained by Jay Scott. "How computers can learn to get better at playing games. This site is for artificial intelligence researchers and intrepid game programmers. I describe game programs and their workings; they rely on heuristic search algorithms, neural networks, genetic algorithms, temporal differences, and other methods. I keep big list of online research papers. And there's more."

TIELT - Testbed for Integrating and Evaluating Learning Techniques. "TIELT is a software tool that is designed to faciliate the evaluation of decision systems in simulators. Our initial focus is on decision systems that include machine learning components, and on simulators for several types of game engines (e.g., real-time strategy, discrete strategy, role playing, team sports, first-person shooter), with emphasis on those related to military simulators of Computer Generated Forces (CGF). However, TIELT can be used with decision systems other than those that have learning (or learned) components, and can be used with non-gaming simulators. ... TIELT's development is sponsored by DARPA's Information Processing Technology Office." - excerpt from "About"

Other References Offline

Banerji, R. 1987. Game Playing. In Encyclopedia of Artificial Intelligence, Vol. 1, ed. Shapiro, Stuart C., 312-319. New York: Wiley & Sons.

Dorfman, Leonard, and Narendra K. Ghosh. 1996. Developing Games That Learn. Upper Saddle River, NJ: Prentice Hall, Inc. Using game examples, the authors show single trial learning in three algorithms.

Herik, H.J. van den, and L.V. Allis, editors. 1992. Heuristic Programming in Artificial Intelligence 3 - The Third Computer Olympiad. Chichester, UK: Ellis Horwood. Knuth, Donald E., and Ronald W. Moore 1975. An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6: 293-326.

Levy, David N., and D. F. Beal, editors. 1991. Heuristic Programming in Artificial Intelligence 2 -The Second Computer Olympiad. Chichester, UK: Ellis Horwood.

Levy, David N. L., and D. F. Beal, editors. 1989. Heuristic Programming in Artificial Intelligence: The First Computer Olympiad. Chichester, UK: Ellis Horwood. Some longer papers on specific topics and short reports of the results of contests.

Rich, Elaine, and Kevin Knight. 1991. Game Playing. In Artificial Intelligence, ed. Shapire, David M. and Joseph F. Murphy, 307-327. New York: McGraw Hill, Inc.

Russell, Stuart, and Peter Norvig. 1995. Game Playing. In Artificial Intelligence: A Modern Approach, 122-145. Upper Saddle River, NJ: Prentice Hall. Gives an overview and then some specifics for chess, checkers, othello, backgammon and Go.

Samuel, Arthur L. 1959. Some Studies in Machine Learning Using the Game of Checkers. In Computation and Intelligence: Collected Readings, ed. Luger, George F., Menlo Park, CA/Cambridge, MA/London: AAAI Press/The MIT Press, 1995