|
AITopics /
GamesGames & 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 Places to StartA Gamut of Games. By Jonathan Schaeffer. AI Magazine 22(3): Fall 2001, 29-46. "In 1950, Claude Shannon published his seminal work on how to program a computer to play chess. Since then, developing game-playing programs that can compete with (and even exceed) the abilities of the human world champions has been a long-sought-after goal of the AI research community. 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."
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." Be sure to see our collection of Games in the news!  Do not pass Go. Computers can beat the world's best chess players but have yet to master other classic games like Go. By David Levy. The Guardian (October 24, 2002). "Ever since Garry Kasparov's sensational 1997 loss to the IBM chess monster Deep Blue, the chess world has thirsted for revenge. But the first opportunity ended in failure in Bahrain on Saturday, when Kasparov's former pupil and successor as World Champion, Vladimir Kramnik, could only draw an 8-game match against one of the world's leading chess engines, Fritz. But this was just the latest in a long series of human versus computer encounters that illustrate the inexorable march of artificial intelligence (AI). It's a story that began at a Dartmouth University conference in 1956, when several of the founding fathers of AI defined the goals of that infant science. One of them was to create a computer program that could defeat the world chess champion. Success would, those scientists believed, reach to the very core of human intellectual endeavour. By the early 1990s, due in no small part to the successes achieved in computer chess, the interest of the AI community had spread to many other games of skill, including backgammon, bridge, Go and Scrabble. Where exactly are we now in this fascinating struggle? ... Two games proving even tougher to crack than chess are bridge and Go."
Readings OnlineAI in the news: Games & Puzzles 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. The Game of Hex: An Automatic Theorem Proving Approach to Game Programming. By Vadim V. Anshelevic, . 2000. In Proceedings of the Seventeenth National Conference on Artificial Intelligence,189 - 194. Menlo Park, Calif.: AAAI Press. Selected as an Outstanding Paper AAAI-2000. Abstract: "The game of Hex is a two-player game with simple rules, a deep underlying mathematical beauty, and a strategic complexity comparable to that of Chess and Go. The massive game-tree search techniques developed mostly for Chess, and successfully used for Checkers, Othello, and a number of other games, become less useful for games with large branching factors like Go and Hex. We offer a new approach, which results in superior playing strength. This approach emphasizes deep analysis of relatively few game positions. In order to reach this goal, we develop an automatic theorem proving technique for topological analysis of Hex positions. We also discuss in detail an idea of modeling Hex positions with electrical resistor circuits. We explain how this approach is implemented in Hexy - the strongest known Hex-playing computer program, able to compete with best human players."
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." Computers, Games and the Real World. By Matthew L. Ginsberg. Scientific American (special issue: Exploring Intelligence - Winter 1998). "More than just competing with people, game-playing machines complement human thinking by offering alternative methods to solving problems." Playing with AI. Edited by Haym Hirsh. IEEE Intelligent Systems, November / December 1999. "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." Games lecture slides and accompanying transcripts from Professors Tomás Lozano-Pérez & Leslie Kaelbling's Spring 2003 course, Artificial Intelligence. Available from MIT OpenCourseWare. "The key idea that underlies game playing programs (presented in Shannon's 1949 paper) is that of limited look-ahead combined with the Min-Max algorithm." [Slide 3.4.7] 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 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:
Related Web SitesAI 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 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 Competition. "The AAAI General Game Playing Competition is designed to test the abilities of general game playing systems by comparing their performance on a variety of games. ... In the qualification round, entrants will play several different types of games, including single player games (such as Maze search), competitive games (such as Tic-tac-toe or some variant of Chess), games with both competitors and cooperators. In some cases, complete information of the board will be available (as in Chess or Tic-tac-toe); in others, only partial info will be available (as in Battleship). In some cases, the game will be exhaustively searchable (as in Tic-tac-toe); in other cases, this will not be possible (as in Chess). Players will have to handle all of these possibilities. Entrants will be evaluated on the basis of consistent legal play, ability to attain winning positions, and overall time; and the best will advance to the second round." [Also see related articles and links elsewhere on this 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" Our Game Pages
More Readings_____. 1981. Game Trees. In The Handbook of Artificial Intelligence, ed. Barr, Avron and Edward A. Feigenbaum, Volume 1, 43-45. Stanford and Los Altos, CA: HeurisTech/William Kaufmann. _____. 1993. Computer Games. In Encyclopedia of Computer Science, 3rd edition, ed. Ralston, Anthony and Edwin D. Reilly, New York: Van Nostrand Reinhold. Abramson, Bruce. 1990. The Expected-Outcome Model of Two-Player Games: Research Notes in Artificial Intelligence. San Francisco: Morgan Kaufmann. Banerji, R. 1987. Game Playing. In Encyclopedia of Artificial Intelligence, Vol. 1, ed. Shapiro, Stuart C., 312-319. New York: Wiley & Sons. Buro, Michael, and Richard E. Korf, Michael Littman, Brian Sheppard, Jonathan Schaeffer. 1999. Playing with AI: Trends & Controversies. IEEE Intelligent Systems. 14 (6): 8 - 18. Haym Hirsh's collection of five essays which demonstrate how "[m]any ideas that have developed in other areas of AI are now finding important applications for those working on game-playing and puzzle-solving systems. Similarly, these problems...have proven to be fertile terrain for research in AI and have contributed ideas back into other areas of AI." 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 |
