Games & Puzzles
AI Technology in the Computer Game World
AITopics > Games & Puzzles
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:
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.
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."
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."
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:
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:
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."
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