COMP.AI.GAMES FREQUENTLY ASKED QUESTIONS 96/05/24 Currently maintained by (Drumroll) Sunir Shah (sshah@intranet.ca) --------------------------------------------------------------------------- TABLE OF CONTENTS 0 Introductory Stuff 0.1 Copyright 0.2 Disclaimer 0.3 Work in Progress 0.4 Netiquette and related topics 0.5 Whom to blame 0.6 What's New in this Release? 1 Overview of comp.ai.games 1.1 What is the purpose of comp.ai.games? 1.2 What are appropriate topics on c.a.g? 1.3 What are _not_ appropriate topics on c.a.g? 1.4 Is there an archive for this group? 2 Overview of Artificial Intelligence 2.1 What is Artificial Intelligence 2.2 What constitues AI in games? What doesn't? 2.3 Should computer opponents be considered AI at all? 2.4 What languages and tools are available for developing AI applications? 2.5 What development methods have been shown to work? 2.5A Choose the least amount of AI that will get the job done 2.5B Start Small 3 Solved and Unsolved Problems in AI for Games 3.1 What game AI problems have been solved? 3.1A Finding the shortest path from point A to point B 3.1B Traversing a maze 3.1C Exhaustive search of sequences of a limited set of moves (gametrees) 3.2 What game-applicable AI problems have not been solved yet? 3.3 What games have been "solved" 4 Promising areas of AI research in gaming 5 Fact Sheets and descriptions of gaming AI projects 5.1 RARS 5.2 Bolo 5.3 OMEGA 5.4 WASTE 6 Summaries of useful c.a.g threads 7 Game AI in the larger world 7.1 Who is sponsoring research into AI in games? 7.2 How can I get a job or assistanceship writing games? 7.3 What commercial games use AI? 7.4 What commercial games advertise AI but don't really use it? 7.5 Are there any AI competitions? 8 Further information 8.1 What are some related news groups? 8.2 Where can I FTP text and binaries? 8.3 What books are available on AI and gaming topics? 9 Source Code 10 Glossary 11 Acknowledgements Note: You can most easily move from section to section below by searching for lines of ``-''. --------------------------------------------------------------------------- Proposed FAQ for comp.ai.games 0 Introductory Stuff 0.1 Copyright Copyright 1996 Sunir Shah. All rights reserved. Portions copyright (c) 1995 by Steve Furlong. All rights reserved. Portions copyright 1995 by Doug Walker and others. Sunir Shah currently has permission to edit sections copyright Steve Furlong, Doug Walker and Rob Uhl. This FAQ may be freely redistributed in its entirety without modification provided that this copyright notice is not removed. It may not be sold for profit or incorporated in commercial documents (e.g., published for sale on CD-ROM, floppy disks, books, magazines, or other print form) without the prior written permission of the copyright holder. Permission is expressly granted for this document to be made available for file transfer from installations offering unrestricted anonymous file transfer on the Internet. 0.2 Disclaimer This FAQ is provided AS IS without any express or implied warranty. While the copyright holder and others have made every effort to ensure that the information contained herein is accurate, they cannot be held liable for any damages arising from its use. 0.3 Work in Progress This is very preliminary, and incomplete, not very nicely formatted, illogically orderded, etc.. But it IS a starting point. I'd appreciate any answers you can give to be mailed to me at sshah@intranet.ca. For those topics that have threads currently underway, could an interested party summarize the discussions? This is a relatively new group, and this FAQ has bounced from person to person and I've (foolishly?) agreed to take it over. Hopefully this will become the "official" FAQ of comp.ai.games but don't hold your breath. 0.4 Netiquette and Related Topics Some Guidelines to Better Living: In general, there are several broad areas which can harm the signal-to-noise ratio in a newsgroup. By taking a little extra care in posting, we can all help keep the noise down. First, do not post questions which are answered in the FAQ. The FAQ will be posted regularly and will also be available by www. DO, however, send useful information to the keeper of the FAQ, sshah@intranet.ca. That will help us keep the FAQ useful. The reason some questions are frequently asked is that the FAQ has dated information and just asking often provides much more information than reading the FAQ. Second, do not respond to flames, flame-bait, and other obnoxious posts. Often, trollers will post false or inflammatory messages and attempt to whip up a flamewar by working both sides of the debate. Let them flame each other, there's no need to help them out. Third, use KEYWORDS. If your post is about chess, put "CHESS:" at the start of your subject line. This will enable those with smart newsreaders to automatically select or kill your article. If it's a question, add "Q:" to the subject line. A larger list of suggested keywords will be included in the FAQ. Any keywording conventions which arise in the course of the group's development will also be added. Fourth, please don't cross-post. If an article is earth-shatteringly important to more than one group, fine. When following up an article which is excessively cross-posted, remove the cross-posts. There was a three- month flamewar/debate over the merits of Ada which would have died if the original troll hadn't been cross-posted to every comp.lang group in existance. What finally killed it was a lot of people removing the excessive cross-posts. If it starts here, let's put it out of our misery quickly. You can set a Follow-Up To: newsgroup in your article, to let folks who are interested follow the discussion without taking up more than one newsgroup. Finally, if someone is posting in the wrong group, tell them via mail. There are a lot of newbies out there, and there are more on the way. If we let a flamewar erupt every time a newbie posts in the wrong place, we'll be all noise and no signal in no time. 0.5 Whom to blame If you have comments or concerns about this FAQ, please direct them to Sunir Shah, sshah@intranet.ca. One thing you may notice is that this FAQ is more an introduction to the topic of AI in gaming than an actual list of frequently-asked questions. When the bulk of the FAQ was written, the newsgroup hadn't been around long enough to have any frequently asked questions. Well, there are a few now. 0.6 What's New in this Release? Lukas Bradley has graciously HTMLized the FAQ. It is now available at http://intranet.ca/~sshah/cagfaq.html. He also added something to the 4th generation language section. And a couple typos were fixed. --------------------------------------------------------------------------- 1 Overview of comp.ai.games 1.1 What is the purpose of comp.ai.games? CHARTER for comp.ai.games The newsgroup comp.ai.games will provide a forum for the discussion of artificial intelligence in games and game-playing. The group will explore practical and theoretical aspects of applying artificial intelligence concepts to the domain of game-playing. In addition to the traditional game areas such as chess and go, the group will also welcome those seeking to bring artificial intelligence into other computer games. Computer games in this context would consist of games played by humans against computers, and by computers (including robots) against each other. This newsgroup is not an appropriate place for the discussion of machine specific coding problems, nor is it the proper place to discuss strategies for defeating computer opponents in existing games. There are other newsgroups already in existence to answer these questions. [Addendum begins . . . here!] I would also like to point out that comp.ai.games is *not* just for professional or academic discussion of artificial intelligence in games. Amateurs and hobbyist game developers will find themselves welcome here as well. 1.2 What are appropriate topics on comp.ai.games? 1.3 What are _not_ appropriate topics for comp.ai.games? - Discussion of tips for beating existing games. - Discussion of why you liked or didn't like a particular game, except as it used AI. - Endless is not/is too discussions of what constitutes AI, of why academics do or do not have anything to show for all their work, or of why Game A's purported AI is better than Game B's. 1.4 Is there an archive for this group? Yes: ftp.cs.cmu.edu:/user/ai/pubs/news/comp.ai.games/ --------------------------------------------------------------------------- 2 Overview of Artificial Intelligence 2.1 What is Artificial Intelligence? [insert definition of choice here ] [However, please mention that the definition of AI is a moving target. It seems to me that "AI" means whatever hasn't been achieved yet. By the standards of 1950, we already seem to have AI.] Note from Sunir: Yes, this is a self-reference. :) WASTE (the AI contest I'm running) has an article that summarizes AI and ALife as well as can be expected in a 12-page seminar outline. Currently, the URLs are: http://intranet.ca/~sshah/waste/art4.html and ftp://ftp.intranet.ca/usr/synapsis/waste/rtfm/article.004 If those change, goto the WASTE pages and/or the WASTE Article Collection pages and read ``An Explanation of AI and ALife'' [Self-reference #1] 2.2 What consitutes AI in games? What doesn't constitute AI? Give me a break. The only correct answer to this question is to not ask this question. 2.3 Should computer opponents be considered AI at all? Some games can be attacked by mathematical means instead of AI. While analyzing a game ahead of time and coding in an optimal algorithm might not be considered AI, mathematical analysis -- when possible! -- usually achieves much better results than AI. For analysis on hundreds of such games, see "Winning Ways for your mathematical plays" volume 1 & 2, by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. ISBN 0-12-031101-9 and 0-12-091102-7. 2.4 What languages and tools are available for developing AI applications? 2.4A "Pure" AI Languages 2.4A1 LISP 2.4A2 PROLOG Games in these languages will probably not be commercially released, but who knows? Abuse has its own version of LISP to run the AI. 2.4B Conventional Languages 2.4B1 C and Pascal 2.4B2 C++ and Object Pascal I'll do all these at once ... AI techniques are algorithms. The language they are implemented in is besides the point. So, if you can code most algorithms in a language you're all set. Screwy languages like Turing, etc. that take out some fundamental programming techniques like goto can cripple some algorithms, but that shouldn't be a big problem. Turing is a teaching language (much like Pascal, but Pascal is better), so that's to be expected. 2.4C 4th Generation Languages [?] [Note from Sunir: What the heck is a 4th Generation Language?] [Added by Lukas Bradley: Sunir, you can edit this] A very high-level language. May use natural English or visual constructs. Algorithms or data structures may be chosen by the compiler. Best example is Smalltalk. 2.4D Third-party Libraries "AISEARCH--C++ Search Class Library", Victor Volkman, C/C++ Users Journal, November 1994. Describes a library with several search algorithms. The library is available in binary from the C Users Group Library as CUG volume 42. [?] 2.4E Development Environments [?] ANYTHING ... go wild. But don't drink and drive. 2.5 What development methods have been shown to work? 2.5A Choose the least amount of AI that will get the job done [General note: I'd like to see some more examples, particularly of games people are likely to have played recently. Chess, auto, commercial wargames, strategy games, action games, whatever.] Q#: I'm writing a game, and want to use artificial intelligence for the computer opponent. What's the best way to go about that? A#: Oof. You certainly don't choose small goals. There are several answers, as you may have deduced from other Q/As in this FAQ. This "Answer" won't give any specifics, but will give guidelines and the "philosophy" behind several approaches. A#a: Fixed Responses You can easily write a computer opponent which behaves in a set fashion. ("Easily" is a relative term, of course, but compared to the other techniques discussed in this answer, you can do this in your sleep.) For instance, the Space Invaders aliens move in a fixed pattern and drop bombs at random. The PacMan ghosts always moved toward your guy, subject to the constraints of the walls. (Getting from point A to point B can be a non-trivial undertaking. See Q/A ### of this FAQ for details on finding the shortest path between two points.) Yes, these examples are very dated, but I wanted to use examples which almost everyone will have seen, and which used the most basic computer opponent methods. The computer opponent either takes no notice of the player's activities (eg, Space Invaders) or treats them in a simplistic manner (eg, PacMan). This makes for easier programming, with "memory" and "reasoning" taking almost no part in planning the computer's actions. The problem with these methods, of course, is that they aren't too satisfying to the player. The only way for the computer to beat a non-klutz in all of the older and most of the newer action games is to throw so many opponents that the player is overwhelmed, or speed up to the point that human reflexes just can't keep up, or simply wear him out. This can make for an exciting, playable game even today, but it shouldn't be confused with AI. A#b: Fixed Rules The next rung on the complexity ladder is giving the computer opponent some "judgement". I put "judgement" in quotes because here we're talking about decisions based on an algorithm determined when the program is written, not a truly intelligent judgement worthy of a human being with a brain worthy of the name. Appropriate techniques might include having a space craft choose a weapon based on the distance to and velocity of the target, or even deciding to run away. The decision on which weapon to fire can be taken from tables generated by the programmer, based on his walk-through experience, or mathematical calculation, or simply his best guess as to the most appropriate choice in different circumstances. More generally, the computer opponent can choose among alternatives by using an arbitrarily complex fixed algorithm and an arbitrarily large database. This leads to a good simulation of intelligence which will satisfy most players. In fact, many of the early posters to comp.ai.games referred to this method in their quest for intelligent opponents. A computer playing backgammon decides its next move based on the current board position, the dice roll, and the value of the doubling cube. Similarly, a chess program uses an algorithm which assigns values to the different pieces, and usually to positions as well. The computer will determine the value of each position some number of moves down the road, assuming (at this level) perfect play by the human, and will choose the move which leads to the position with the maximum value. Another currently popular example is Auto. [Is that the right name? I'm talking about the program with human players and pre-programmed killer tanks and airplanes. Someone posted a lengthy, excellent discussion of its genesis. Naturally, I can't find the copy I kept, and my host computer doesn't keep things that far back.] The algorithms and values, though complex and very effective, are written by humans before the combat begins, and don't adapt to changes in the environment. (If anyone has developed a bot with an adaptive algorithm, please post a review!) This cannot really be called "intelligence" on the part of the computer opponent, because the computer is obeying rules set forth when the program was written. The computer also is not analyzing the user's style. A computer opponent could, I suppose, analyze the human player's style and use that as another variable in a fixed algorithm or lookup table. That could lead to a combinatorial explosion in table size. A variation on this method is to have several computer opponents, which have different styles and possibly different capabilities. The computer opponent can be chosen by the player or at random. A#c: AI-Generated Lookup Tables When I characterized the "Fixed Rules" method as non-intelligent, I didn't mean to diminish the amount of work that goes into developing the algorithms or the lookup tables. In the case of backgammon, for instance, the computer has to choose two or four moves from possibly several dozen moves, as well as decide whether to double or resign. The programmer could conceivably write a lookup table for every possible piece position and dice roll, but that requires too much storage to be practical. A practical backgammon program (to continue the example) assigns weights to different combinations of positions and calculates the value of each position reachable from the current position and dice roll. The programmer might develop a weighting system to evaluate the worth of each potential position, but that's a very difficult proposition even in an easy game like backgammon or chess. In a hundred-unit wargame, with every unit having unique characteristics, and the terrain and random factors complicating the issue still further, the optimal system of weights cannot be determined by a person, possibly cannot theoretically be determined, and certainly couldn't be determined in any reasonable amount of time, even with lots of big computers working on it. The solution is to settle for "good enough" rather than "best". One of the best ways to get the "good enough" weights and algorithms is to set up the computer to play both sides in a game, with a lot of variation in the algorithms and weights. Let the two computer "players" duke it out and see which set wins most often. Modify the programs and try it again until you're happy or the game needs to ship. An even better refinement of the above method is to let the computer do its own modifications to find the best winning technique. A convenient way to look at this is that there is a top-level program which is trying to develop a winning set of algorithms and values. The top-level program constantly fiddles with the "player" programs to find the best one. If the human programmer feels that the algorithms are good enough, then only the weights assigned to each position or piece or whatever need to be optimized. Choosing the weights at random is not the most effective way to find the best set, but it has the benefit of easy implementation. Development of algorithms and more sophisticated assignment of weights can be performed with "genetic algorithms", discussed elsewhere in this FAQ. [Well, will be, anyway.] In any event, the programmer sets up the program which will determine a good set of parameters, then lets it run for a while. When he comes back, he takes the best algorithm and weights that were generated, sticks that into his program as a fixed algorithm and lookup table, and goes to market. This "AI During Development" method has both the worst and the best of both worlds. On the "worst" side of the ledger, the programmer is going to the effort of learning and using real AI techniques during development, but is distributing a fixed routine for the real game. On the "best" side, a program written using a procedural language and algorithms will run much faster and use fewer resources than a program using real AI techniques. Moreover, the AI toolkits, whether they be for genetic algorithms, neural nets, or just a LISP interpreter on which these run, often require run-time license fees. A#d: Flexible Algorithms Next we come to adaptive algorithms and data tables for the computer opponent. This class of methods uses algorithms and weights which are adjusted at runtime to get better results. For instance, in a complex wargame, the computer opponent can start out using a given method of moving units and attacking under different circumstances. Or, better yet, it initially uses a variety of techniques. The program monitors the effectiveness of each algorithm and set of weights, and gradually weeds out the least effective. This method greatly resembles the one described above, except that the modification of algorithms and weights happens while the game is running, rather than during development. Re-read the list of the drawbacks of run-time artificial intelligence toolkits. The use of genetic algorithms and other methods of self-modifying the program is considered by some to be artificial intelligence, but it doesn't quite make the grade. For one thing, something as simple as this would never pass the Turing test. See Q/A ### in this FAQ for a further discussion of what constitutes "intelligence" in a computer program. A#e: Analyzing the Human's Actions The next step up is analysis of the human player's actions. In this context, "analysis" means just that: identification, study, and classification of elements of the human's style. We've now reached an area of serious AI research. At the least, a program at this level will need strong pattern recognition capabilities. Computer pattern recognition, though much progress has been made recently, doesn't come anywhere near the ability of a human being or most house pets. Think about a shooting game. If your opponent always dodges left when you shoot at him, you, the human, will probably catch on pretty quickly and learn to fire a quick second shot to his left. A computer, on the other hand, might see only that sometimes the human moves 14 units over, and sometimes 15; no pattern there! See ????? for a fuller discussion of pattern recognition, including the current state of the art. Pattern recognition is much more effective as the number of cases grows. In neural-net terms, the training session can continue forever, even if the net needs to give results before forever is over. And being able to divide the experiences into different buckets can help even more. For this reason, asking the player to identify himself and storing as much information permanently will greatly increase the game's apparent intelligence. A#f: Sub-Goal Selection Sub-goal selection has a pretty obvious meaning: the choice of goals to accomplish, each of which lead to the accomplishment of the overall goal. For instance, in the space shoot-em-up we've used several times in this answer, let's say the computer checks energy levels and basic abilities and determines that the human has a definite advantage because it has a higher energy level, but is otherwise equal. The computer opponent could decide on the subgoal of depleting the human's energy without giving up any advantage. To do that, the computer could decide to zip in, attract fire, and dash off without being hit. The actions the computer would perform in this scenario could have been pre-programmed to crop up in the proper circumstances, assuming that the programmer was infinitely far-sighted. In a proper AI system, the computer would somehow recognize a need, sift through a large number of possible goals and actions, and choose the one most likely to succeed. So far as I know, no game on the market uses anything approaching this technique. A#g: Artificial Intelligence This is a tough section to write. The major problem is that there is no widely-agreed-upon definition of "artificial intelligence". Another is, if anyone developed a truly intelligent computer, it might well decide that it has better things to do than play games. A#h: Sunir's self-reference #2 to WASTE Read ``An Explanation of AI and ALife'' in the WASTE Article Collection already. http://intranet.ca/~sshah/waste/art4.html ftp://ftp.intranet.ca/usr/synapsis/waste/rtfm/article.004 It's a big summary of a bunch of techniques. A#i: Be creative Combine, change, alter, come up with new, mutate, evolve, destroy, reconstruct, burn, spray paint algorithms to come up with a solution. So now, to return to the original question, how should you add AI to your game? You first need to decide what level of computer response will suit your needs, abilities, and available time. If your main intent is to write a game which will keep the human players entertained and challenged, go with the lowest workable level, as they are defined above. Do research, and lift whatever you can from public-domain sources. The job of adding convincing responses to your game will probably dwarf any estimates you make, so anything you can do to minimize the work is research effort well spent. 2.5B Start Small Many posters in c.a.g state that they wish to develop a World War II simulation with an intelligent computer opponent, or some similarly ambitious goal. That's fine for a long-term goal, but the details are likely to swamp all but the true code gods. I don't mean to sound defeatist here; I just want to get y'all thinking about what you're biting into. That being said, what is the best way to get started? Why, in small steps, of course. Rather than writing the data structures and movement rules for an armored division and all subordinate units, and then wondering how to have the lower units find their way from point A to point B, start with a small, simple map or grid or generalized graph and simple movement rules. Write code to get a single unit from point A to point B. Then add complications piece by piece and get a good algorithm for each step. Your final product may well be general enough to handle any conditions your real game will need, but you may want to hang on to the earlier algorithms as well; they should be faster for their specific domains than a more general routine. Another way to start small is to write an opponent for a simple game. Many simple games exist; just see any book of kids games from the pre- electronic days. Fox and Geese or an Awari variant should give a good starting point.