COMP.AI.GAMES
Frequently Asked Questions

Table of Contents

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

Portions copyright 1999 David J Burbage. All rights reserved.
Portions 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

As the new maintainer of this FAQ, it needs a spring clean. So it may be changing somewhat over the next few weeks and months. I'm going to introduce a version number so it can be tracked historically. All versions previous to this can be considered as 1.x where x is a changing date... there is a new revision history at the bottom of this text.

The FAQ has been maintained rather sporadically in the past, I hope to do at least a bit better. So nag me if you don't see updates. Especially if you've submitted new information for inclusion.

0.4 Netiquette and Related Topics

See Section 1 for the introduction to comp.ai.games . This is the official FAQ.

The newsgroup is rather good insofar as there are not thousands of messages every day, and there is a good mix of expertise from people in the games industry, people who are interested in the topic but work in other computing fields, and people who are simply interested in the topic for itself. This makes for a better newsgroup than some. I'd like to see it kept that way.

We don't see much flaming, there is (of course) some spamming but far better than in some other newsgroups. 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.

Some guidelines to keeping everyone sane and happy are as follows:

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 pertinent and contributory information to the keeper of the FAQ, dave@blueleg.co.uk . 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 (in the UK, known as wind-up merchants) 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. If your software allows it, of course.

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 Dave Burbage (dave@blueleg.co.uk).

0.6 What's new in this release?

(2.00) - Inclusion of explanation of some important algorithms. Newer links to the interesting sites on the Web. Additional book references. An online version with hyperlinks will be available soon. Again, nag me if it doesn't happen soon.

(2.01) - Corrections from Sunir, Bjorn and others.

---------------------------------------------------------------------------

1 Overview 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.

It should be pointed 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?

There are plenty. Frequently occurring topics include

• pathfinding
• minimax algorithms
• neural nets
• boardgame logic
• algorithm discussions and approaches

It is certainly in order to post links to samples, demos and downloads for purposes of discussion of AI in games. There are a fair number on the Net already, and many can be listed in this FAQ. Send me your URLs. 1.2.1

Game Designers - If you are/have/will be working on a commercially released game, please feel free to discuss how the AI was approached for the game(s) in question. Of course, we don't want to know anything which is commercially sensitive, but there's a distinct lack of knowledge in this area (how are well known games' AI approached)?

1.3 What are _not_ appropriate topics for comp.ai.games?

• Discussion of basic 'hints and tips' for games. Where a game has poor or strong AI, on the other hand, let us know.
• 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.
• Veering into basic programming issues, apart from approaches to the AI development. There are many other newsgroups which are better places for these discussions!

Older ftp archive (up to 16th August 1997): ftp://ftp.cs.cmu.edu:/user/ai/pubs/news/comp.ai.games/

New archive : use DejaNews (http://www.dejanews.com).

If there is a desire to keep an independent (not in the hands of DejaNews) archive then let me know and it can be planned accordingly. If anyone knows of another source of the newsgroup archive, let me know and I will point to it in this FAQ.

---------------------------------------------------------------------------

2 Overview of Artificial Intelligence

Unfortunately there's no easy answer to this, as it means different things to different people.

2.2 What constitutes AI in games? What doesn't constitute AI?

What it is : Code which looks at game information which results in apparently 'intelligent' responses. Whether this is as a result of a Finite State machine, a Fuzzy State Machine, genetic algorithms, scripting rules, minimax, database lookup or plain cheating, it can all be called AI with varying degrees of honesty.

What can't be called AI : random responses (with few exceptions). Fixed scripts eg the gate opens after 10 seconds, a predetermined happening.

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? There are LISP-like scripting elements in some commercial games.

2.4B Conventional Languages
2.4B1 C and Pascal
2.4B2 C++ and Object Pascal
2.4B3 Visual Basic or other BASICs

All these can be summarised 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. The intelligence is in the algorithm, not the language.

2.4C 4th Generation Languages

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. Not known for their applicability to Games.

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

2.5 What development methods have been shown to work?

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#: Start simple. Make the computer opponent do something. You can always build on the success of the bits that work, and clear out the bits that don't. Evolutionary programming...

There are many different approaches :

A#a: Fixed Responses

You can easily write a computer opponent which behaves in a set fashion. A 'Finite State Machine' would be an example of this. 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. These examples are very dated, but this should ensure that the examples are those 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". "Judgement" is 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.

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, supposedly, 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

"Fixed Rules", when characterized as non-intelligent, it 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". This could be characterised as a 'Fuzzy Logic' state machine, as opposed to a Finite State Machine. 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".

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.

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.

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!

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: 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. The best AIs implemented have been shown to use a combination of many approaches.

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. Learn the Minimax algorithm for board game variants, and the A* pathfinding algorithm for moving units in a Real Time strategy game. Learn how to write a finite state machine for use in running bots in a 3D shoot-em-up. It can all get very complicated very quickly!

3 Solved and Unsolved Problems in AI for Games

Steve Woodcock keeps his finger on the pulse of current AI evolution. You can usually get some good leads on all things comp.ai.games by visiting his excellent site at:

http://www.gameai.com

He has a page about "solved" *games*. That means that computer AI has evaluated enough combinations to know whether a win is possible by moving first. Or second, or whatever. Just like in O's and X's, you know that "it's always a draw" with optimum play, it has been shown that, for example, Connect 4 is always a Win for the first player, again, with optimum play. Chess hasn't been solved...

3.1 What game AI problems have been solved well enough that I can build them into my next game?

3.1A Finding the shortest path from point A to point B.

The A* Algorithm

This is the best known, and most widely implemented Shortest Path Algorithm. The algorithm forms a star, and this is the shape of the potential paths spread out from point 'A'. Point 'B' will, at some point, be under the star shape as it spreads out looking for all paths from point A. Weighting is given to each discrete area covered by the search to find the best path.

There are lots of shortest path algorithms (SPAs) around. There are some animations present on the internet.

An good page is Smart Unit Navigation:
http://home.sol.no/~johncl/shorpath.htm

Another, academically focussed page is
http://home1.stofanet.dk/breese/aaai99.html

A complete 3D RTS (Real Time Strategy) game which is using A* has been written by Keith Mukai. It can be downloaded and is described at :
this page has disappeared. Keith, are you there?

Finally, there is much information on A* and variants at Amit's Game Programming site :
http://theory.stanford.edu/~amitp/GameProgramming/

James Matthews has written a demo app with source code which can be found at
http://www.generation5.org/

3.1B Traversing a maze.

Traversing a maze is a variant of the above. For our purposes here, "traversing a maze" involves moving from position to position toward an unknown but specific goal, with only partial knowledge of the maze. The effort to move from one position to another is usually constant.

A monte carlo algorithm, randomly choosing a direction at each intersection, will in principle eventually solve any maze. And an infinite number of monkeys typing randomly will eventually recreate the works of Shakespeare.

A brute force algorithm, such as following the left wall until you find the exit, will solve most mazes, but can be defeated by special maze design.

A more sophisticated algorithm will remember that part of the maze which has already been travelled or seen, and will avoid aimless retravel of known segments. The algorithm should attempt to fill in blank spaces by directed searching.

3.1C Exhaustive search of sequences of a limited set of moves. (gametrees) known as Minimax

[eg, chess]
[Note that the practicality of building this into your game depends on the power of your processor, amount of memory, time constraints, number of possible moves at each step, and number of moves you wish to search.]

Such games are often represented as minimax trees---we assume the first player is trying to maximize some payoff for himself, and the second player is trying to minimize the payoff to the first player. At the end of each sequence of tried moves, we assign a number (the payoff) to the reached position using an "evaluation function".

>>>> [example here to follow]

Alpha-beta pruning is a method that (usually) allows minimax trees twice as deep (i.e., move sequences twice as long) to be searched in the same time. Alpha-beta is described in almost any introductory AI text book. It is basically an optimisation of the evaluation function so that redundant nodes can be eliminated as soon as it is known, rather than evaluating all nodes and leaves before inspecting minimax style.

3.1D Database knowledge of information to apply

Larger game AI developments, in particular chess, and backgammon, have libaries of 'openings' which huge historic and stored analysis has already been done to help find the best next move. A good online version of how a database mimics human intelligence can be found in a "Twenty Questions" on the Web called http://come.to/20Q and it's great fun!

3.2 What game-applicable AI problems have not been solved yet?

The current best backgammon player, TD-Gammon, by Gerald Tesauro, was trained using temporal difference learning on a neural net (ref: March 1995 CACM)

3.3 What games have been "solved"

First off, the following games have been solved by analysis and exhaustive searches, not by "artificial intelligence". However, they are included here so you won't put a lot of time into writing an AI program to beat someone at these games. (This isn't to discourage you from writing the games, just to advise you that AI, per se, won't be needed.)

The meaning of "solved" is subject to some debate. In some games (e.g., Hex) we know who will win if the game is played perfectly (the "game theoretic value"), but not how to play perfectly. The following are games for which computer opponents are available that do achieve the game theoretic value.

[ If anyone has code snippets or entire programs for these, or pointers to such, please drop me a line. ]

• Connect 4. First player wins.
• Gomoku (5 in a row) on a 15x15 board. First player wins. The game is solved both with and without overlines (six or more in a row) being counted as a win.
• 3-D Tic-Tac-Toe (3x3x3). First player wins.
• Qubic (4x4x4 three-dimensional tic-tac-toe). First player wins.
• Nine Men's Morris (also called Mill). The game is a draw.
• Awari. The general name of "Awari" covers a huge number of variants. Some of these have been solved analytically and some have not.
• Sprouts, for some numbers of points, anyway. Sorry, I don't have the figures on hand, but they were given in the original Scientific American article back in the '70's. I haven't heard of any further investigation.

---------------------------------------------------------------------------

4 What are some promising areas of research in AI, as applied to games?

Case-Based Reasoning (CBR), sometimes (not necessarily correctly) known as knowledge-based systems or expert systems.

Neural Nets.
Steve Woodcock's Round Table discussions at the Gamedev meet have sometimes touched on this. Many programmers quote it as the next great thing to implement, but few have actually succeeded. The problem is one of complexity and practicality.

Fuzzy Logic.
Monitoring and adapting to the opponent's style of play. A number of rules which can be adapted, graded, modified and measured are an excellent way of computer learning.

---------------------------------------------------------------------------

5 Fact Sheets and descriptions of Gaming AI projects

Projects come and go, but some of the latest ones can be found at http://dir.yahoo.com/Recreation/Games/Computer_Games/Programming/Projects/

A subject much in discussion during the latter half of 1999 was the 'Rock, Scissors, Paper' or 'RoShamBo' competition, along with the whole of the rec.games.poker newsgroup. The competition has now completed, but the discussion goes on. Find out more about it at http://www.cs.ualberta.ca/~darse/rsbpc.html and play a bot at http://www.sportsrocket.com/cgi-bin/roshambo/roshambot.cgi

---------------------------------------------------------------------------

6 Summaries of useful c.a.g threads

This note is here because we can refer to Steve's pages again. He has these threads archived, not summarized :

http://www.gameai.com

---------------------------------------------------------------------------

7 Game AI in the larger world

This section lists game-specific links which serve as good starting points for those interested in resources and approaches for programming game AI in each specific game. Please email the maintainer with new links for other games, or better links if you can find them.

7.1.1 Chess

A good, but not recently updated guide, is at http://www.xs4all.nl/~verhelst/chess/programming.html

7.1.2 GO

A good opening for AI discussion of GO is at: http://www.usgo.org/computer/

7.1.3 Backgammon

A fine starting point for Backgammon, including a discussion of the various AI programs available and their capabilities : http://www.statslab.cam.ac.uk/~sret1/backgammon/

7.1.4 Othello / Reversi

There doesn't appear to be a specific programming page around, but a good starting point would be http://www.iioa.org

7.1.5 Checkers / Draughts

Again, no specific programming AI page, but this is a good place to start : http://www.mcn.net/~jimloy/checkers.html

7.1.6 3D shootemups AI

Bots, programming of both server and client, can be found at http://www.planetquake.com/botshop and many more at http://www.botepidemic.com/

7.1.7 Other game AI links

The list below will give you many hours AI surfing :

http://www.gameai.com/ai.html
http://www.gamedev.net
http://www.gamasutra.com
http://www.programmersheaven.com

Grant Castillou has put together some downloads which cover Gomoku, Checkers and Othello. You can get them at: http://skyscraper.fortunecity.com/apple/230/

This section (7.1) needs additional resources for AI in card games, board games, driving games, fighting/arcade and AI for other computer hosted / simulated games. Let me know if you have any.

7.2 Who is sponsoring research into AI in games?

Lots of people. Professional game developers can either just want to get the game out the door or can be dedicated to the AI. Whether they get their code included or not! University research projects are usually focused on the techniques used instead of the domain.

7.3 How can I get a job or an assistanceship writing games?

Learn C or C++. Buy a book on games. Write a simple game. Write a more complicated game that's enjoyable to play. Send the demo to a company which wants talented, useful game programmers.

You could offer to work for free, of course, if the bank balance allows, and you're confident enough.

Further details of the game industry from the developer viewpoint can be found at http://www.godgames.com especially, check out 'The Oracle' where pretty much every aspect of the game developer's questions are asked (and answered).

7.4 What commercial games use AI?

Pretty much all of them. You will see people complaining in the related games newsgroups about poor AI if it hasn't been implemented coherently.

7.5 What commercial games advertise AI but don't really use it?

This is getting into the definition of AI.

7.6 Are there any AI competitions?

The Loebner Prize, based on a fund of over $100,000 established by New York businessman Hugh G. Loebner, is awarded annually for the computer program that best emulates natural human behavior. During the contest, a panel of independent judges attempts to determine whether the responses on a computer terminal are being produced by a computer or a person, along the lines of the Turing Test. The designers of the best program each year win a cash award and a medal. If a program passes the test in all its particulars, then the entire fund will be paid to the program's designer and the fund abolished. For further information about the Loebner Prize, write Dr. Robert Epstein, Executive Director, Cambridge Center for Behavioral Studies, 11 Waterhouse Street, Cambridge, MA 02138, or call 617-491-9020.

The International Computer Chess Association presents an annual prize for the best computer-generated annotation of a chess game. The output should be reminiscent of that appearing in newspaper chess columns, and will be judged on both the correctness and depth of the variations and also on the quality of the program's written output. The deadline is December 31, 1994. For more information, write to Tony Marsland tony@cs.ualberta.ca, ICCA President, Computing Science Department, University of Alberta, Edmonton, Canada T6G 2H1, call 403-492-3971, or fax 403-492-1071.

---------------------------------------------------------------------------

8 Further information

The entire comp.ai.* hierarchy. Particular topics people seem interested in include comp.ai.fuzzy, comp.ai.genetic, and comp.ai.neural-net. The rec.games.* and alt.games.* hierarchies.

The comp.ai FAQ in particular has an enormous fund of information. I plan to incorporate as much of it as I can without being accused of plagiarism, but for now, just look it over. This FAQ has a long list of reference books and articles covering topics of interest to AI gamers. http://www.cs.uu.nl/wais/html/na-dir/ai-faq/general/.html

8.2 Where can I go to FTP text and binaries?

Some info can be found in x2ftp.oulu.fi:/pub/msdos/programming/ directory.. Please note that the "msdos" part in path does NOT mean everything is dos related

x2ftp.oulu.fi:/pub/books/game/
3d-books.320 3D graphics books reviewed by Brian Hook - 3.20
aaa_set.toc Action Arcade Adventure Set - Diana Gruber 1994 (FastGraph)
cgames_1.txt Computer Games I - Levy 1988
cgames_2.txt Computer Games II - Levy 1988
explorer.toc PC Game Programming Explorer - Dave Roberts 1994 playgod.zip Playing 
God, Creating Virtual Worlds - Roehl 1994 (TOC/errata)
tricks.rev Tricks of the Game Programming Gurus - LaMothe/Ratcliff 1994
tricks.toc Tricks of the Game Programming Gurus - LaMothe/Ratcliff 1994

x2ftp.oulu.fi:/pub/msdos/programming/ai/
x2ftp.oulu.fi:/pub/msdos/programming/theory/

Especially the latter directory has some excellent documents.

BOLO : the 'official' archive seems to be down. I suggest starting at the home page, but the development seems to have died. http://www.lgm.com/bolo/

8.3 What books and magazines are available on AI and gaming topics?

_Neural Networks and Fuzzy Logic Applications in C/C++_, Stephen T. Welstead, Wiley Professional Computing, 1994. Discusses the topics and gives library and application source code for Borland C++.

Another resource is Sunir Shah's "Programmers' Booklist," a list of, you got it, books (plus magazines, e-mags, web sites, and files) of interest to the programmer. This list is indexed hypertext. The web site is at http://www.intranet.ca/~sshah/booklist.html. There is a "binary searchable" version at: http://www.intranet.ca/~sshah/booklist. This list is a very comprehensive and inclusive one.

---------------------------------------------------------------------------

10 Glossary

Case-based Reasoning:
Technique whereby "cases" similar to the current problem are retrieved and their "solutions" modified to work on the current problem.

Fuzzy Logic:
In Fuzzy Logic, truth values are real values in the closed interval [0..1]. The definitions of the boolean operators are extended to fit this continuous domain. By avoiding discrete truth-values, Fuzzy Logic avoids some of the problems inherent in either-or judgments and yields natural interpretations of utterances like "very hot". Fuzzy Logic has applications in control theory.

SPA:
Shortest Path Algorithm.

---------------------------------------------------------------------------

11 Acknowledgements

[Dave Burbage's]
My thanks to:
Sunir Shah - for handing me the FAQ.
Bjorn Reese - for not bullying me too much in getting this version out at all!

[Sunir Shah's]
My thanks to:
David Burbage for taking over the FAQ.
Steve Furlong
Doug Walker for conferring the copyrighted on me.
Robert Uhl
Lukas Bradley for HTMLizing the FAQ.
Steven Woodcock for putting up http://www.gameai.com
Everyone else for putting up with me.

[Steve Furlong's]
My thanks to:

Dan Thies for the charter, and for creating this group
Doug Walker, the original FAQ maintainer
Mark Kantrowitz, maintainer of the comp.ai FAQ
Jouni Miettunen
Paul Colley
Frits Daalmans
Robert Uhl
Mitchel Timin
Jessie Montrose
Will Uther
Timothy Huang

and everyone else that submitted questions or answers or pointers to answers

[document ends]

Discuss this article in the forums

Date this article was posted to GameDev.net: 7/31/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Introduction

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!