COMP.AI.GAMES
FREQUENTLY ASKED QUESTIONS
8th January 2000
Version 2.01

Currently maintained by David J Burbage
(dave@blueleg.co.uk)


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

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 - minimax)
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

6 Game AI in the larger world
6.1 Who is sponsoring research into AI in games?
6.2 How can I get a job or assistanceship writing games?
6.3 What commercial games use AI?
6.4 What commercial games advertise AI but don't really use it?
6.5 Are there any AI competitions?

7 Further information
7.1 Where is Web information on XXX?
7.2 What are some related news groups?
7.2 Where can I FTP text and binaries?
7.3 What books are available on AI and gaming topics?

8 Source Code

9 Glossary

10 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

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


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.

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!


1.4 Is there an archive for this group?

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


2.1 What is 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 How do I (or why does the computer)

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?

2.5A Choose the least amount of AI that will get the job done

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! 

[end part 1]

1