In another thread, the question was asked about whether people here had used ANNs or GAs in their work. I''d like to followup that question and expand it to be more specific. If you have used a ANN or GA in a computer game (does not have to be a shipped game, and it could have been in a testbed) to make a decision or perform some AI function, then we want to hear about it. Can you describe the type of implementation you developed and what the ANN or GA actually did? The idea behind this request, is that if more of us saw how others were able to used these tools, then maybe these tools would get used more often. Since I asked the question, I guess I should offer one usage. I implemented a GA to solve a Vehicle Routing Problem in a RTS. The problem was that whenever a building was built or a building was ordered to produce stuff, certain amounts of materials had to be located in other buildings and then picked up and delivered to the building in need. For instance, to make steel at the smelter, required certain amounts of coal and iron to be delivered. The coal was produced and stored at coal mines (another buiilding) and the iron was produced and stored at iron mines. The AI controlled a fleet of transport trucks that could be assigned to go and pick up and then deliver materials. So, when the smelter was out of material to make steel, the AI would have to decide on which truck that was best available to go to the best location for coal and pick up the best amount of coal that it could and then decide on the best location for iron and pick up the best amount of iron that it could and then take the best route to get the materials to the smelter. Did you notice that everything had the use of the word best in it? This problem is an optimization problem, one that GAs are very well suited to perform. When I implemented the GA and then ran it and ran it and ran it (GAs take lots of iterations) the GA eventually solved the problem and found the truck that was best suited to go to the best sites for coal and iron and follow the best paths to get there and then deliver the materials to the smelter. The only drawback to the GA was its speed of performance. In the tests that I set up for it, it averaged 33,000 ms to make a decision. While some would say that this is not bad performance for a GA, it was unacceptable performance for a decision-making process in a RTS game. I worked with the GA, its evaluation function, the mutation value, the cross-over value and the genotype for a couple of weeks but never was able to get the performance to improve much, so I canned the approach and went with a greedy algorithm that performed the same tests in an average of 13 ms but did not calculate as well (ie. the truck selected was not always the best, the sites selected were not always the best, but instead they were always just "good enough"). Anyway, applying a GA to a Vehicle Routing Problem (VRP) is pretty easy, as the problem of optimizing the best routes and sites and truck selection were a natural for a GA. Now, lets hear from someone else, and their experience with an ANN or GA implemented in a computer game or testbed. Eric

This is not my story but actually from an old, old issue of GDMag. The principle was to develop an AI system that would play a good game of RISK or something similar. The author developed a representation which was very much like assembly language. Then, using random ordering of commands, various "players" were developed and played against each other. Each was given a score based on its average perrformance at all four possible board positions. Standard crossover was used along with a simple mutation operator. Ultimately, the result was a very good AI.

The take home message: representation is the critical key. Also, this coevolutionary strategy has been shown to be very powerful in a number of different types of GA problems where performance within a group is critical.

I wonder how it would have performed had the operators been a little more exotic. Such as subroutine compression (tree brach compression) and expansion.

-KirkD

As may have been made obvious from previous posts I''m well on the GA/ANN bandwagon, however I don''t think I''d use it in game as a quick optimisation procedure to get the best answer in a straight forward way. Geta, in your example you had to decide on the best truck to get the best amount of resources from the best point in the world. Simply put GA''s are directed random search and I''m not surprised a more direct heuristic algorithm worked. However it is possible you could have used the GA beforehand to reduce the search space, or direct it, by optimising the heuristics used by a depth/breadth first search algorithm, given the world state (position of trucks and resources) as an input. Also, if the the trucks continually make trips around the world, then you could evolve any heuristics in game as the world changed by mutating them and testing their average performance on choosing routes.
Obviously I don''t know the problem in depth so these ideas may be completely unfeasible/useless but using GA''s in conjunction with other methods can often be useful in a more subtle way.

For myself, I''ve only worked with testbeds using GA evolved ANN''s as robot controllers for fairly simple tasks, such as light following in physically simulated environments. The bots collide with the lights, have momentum and knock the lights away from them as they hit them. They do optimise to good, if not perfect, solutions. Often using the physics of the world to their own advantage. Such as one bot that had a flat backside but pointed nose and would back at the light to trap it between its rear jets and carry it around as it moved.
I''m currently working on a running open source project at sourceforge using evolved ANN''s as robot controllers. The system is easy to use, designed to be extensible and available to download using cvs (no compiled version yet I''m afraid). Search for its unix name "galab" or full name "Genetic Algorithm Lab - robot evolver" at http://www.sourceforge.net if you''re interested. Still in development, not a hint of a helpfile yet but it does work. It''s also in Java (use 1.3).

Mike

Hey Mike, let me guess. You are, or have been, a member of the COGS group at Sussex, haven''t you??!!!

Timkin

Being honest I have not deployed a GA or ANN in a game. However, I have developed test beds for GAs as a part of some research I did about 5 years ago. I''ve also implemented ANNsfor several function learning problems.

My GA research would be of use to anyone using them in games as it was an investigation of the asymptotic convergence properties of the canonical (standard 3 operator, haploid chromosome) GA. The primary finding of my work was a new form of Holland''s schemata theorem that explained the asymptotics. The asymptotic convergence was caused by the breakdown of the crossover operator as the population converged. This is precisely why hybrid methods (combining GAs with deterministic search algorithms) work better than GAs on many problems. The answer for the poor little GA was a very simple method to re-map the problem space based on the search statistics. Unfortunately, another author had derived a similar method (without actually developing the underlying theory as to why it worked) and published ahead of me. Hence, I didn''t bother publishing my work, although I should have (and probably should still!).

So, the bottom line is this... there is a very simple method to accelerate the convergence of the GA and obtain orders of magnitude improvement in convergence time. If you''d like to know what it is, drop me a line and I might be able to work out sending you a copy of the research report.

Cheers,

Tim

My goodness Timkin, can you tell the signs of Inman''s indoctrination techniques from that distance? I''ve nearly finished the evolutionary and adaptive systems MSc, just working on my dissertation now.
I''d definately be interested in looking at your paper, mail it to me (.ps format fine if you have it) at Mike@Ducker.org.uk

Mike

Timkin,

I would also like to see your report. Please send to rkdelisle@earthlink.net.

Thanks!!

-Kirk

Ack, such interest in my work! I don''t think I have an electronic copy any more, only hard copy. I''ll hunt around my archives and see what I can drag up, otherwise I could probably send out a hard copy or two.

If I do find my electronic version, I''ll put it up on the web and place the URL here.

Cheers,

Tim

quote:Original post by MikeD
My goodness Timkin, can you tell the signs of Inman''s indoctrination techniques from that distance?

Hehe.. not quite. I came this --> ][ close to doing my PhD at Sussex. It''s only that I got offered my current research opportunity that I didn''t go.

Tim