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 constitutes 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.3 Where can I FTP text and binaries?
7.4 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):

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! 

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


7.1 Where can I find information on XXX game programming?


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



8.1 What are some related news groups?


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]

1