Howdy. Consider this small game/problem/whatever : - There are two teams. - Each team has a player that has an attribute representing their health. - When a player of one team is touching a player of another team, they can slowly drain their health from them. That is, they can only drain the person of _one_ enemy player, even if a number of enemy players are touching them. - A team wins when the enemy team is eliminated. Now.. what I want to be able to do is to write the AI for a team and/or its individual players. An "end heuristic" is easy. The culmination of all players'' health with the highest value will obviously reflect the best strategy, and the best strategy is obviously the fact that the greater number of players in a team that are touching an enemy player will drain their health quicker and result in less health-drain from a player from their own team. Following so far ? ;-D If anyone could answer any of the following questions, or point me towards a source/topic that will introduce me to solving this problem, it would be greatly appreciated : - Is writing such an AI program feasible ? - I want to allow the AI to be able to analyse different aspects of its approach towards finding the optimum strategy. When I start adding additional functionality to the players'' abilities, I want to be able to use the same, unmodified AI engine to determine the new optimum strategy given the extra functionality. Is THAT possible, or must I explicitly add sections to the AI to account for new functionality ? It''s late.. I''m rambling.. I''ll leave it at that for now.

It sounds like a good candidate for Evolutionary Programming. Essentially, you represent the individual units'' behaviors as various primitives, e.g., conditional statements (if...then), property returns (enemy to the left, energy low, etc.), and terminators (move left, move up, etc.). You''ll have to adapt these considerably for your particular project. It''s helpful to think of this with the analogy of assembly language where you have various primitive commands that do very specific and simple operations. String 10 or so together and you have a function that performs a desired task.

Next, use a genetic algorithm to optimize the behavior. Each chromosome could represent a decision tree made up of your primitives. Of course, any type of representation which is interpretable into and out of a chromosome will work.

In order to optimize the situation, use tournaments. If there are two teams, pick two chromosomes randomly and assign one to each team within the game. Assess the performance with some measure like time to eliminate the other team - this would assume the the minimum value is better. This would be your fitness function and could easily consist of anything you want to measure.

Continue the tournaments until you''ve chosen every existing chromosome from the population and given it a fitness score. You could also pick each one multiple times and pit them against a different opponent, then use the average score. This might actually give you a better assessment of the abilities of that chromosome.

Do the standard crossover and mutation operations, and start over. Do this for some number of generations, and BAM!! You''ve got a unique AI.

Problems:

This is a lot of work and encoding the representation into chromosomes might be tough.

Your final chromosome will probably have a lot of excess information that can be trimmed out. It would be hard to automate this trimming process.

Time. This may take a lot of time to not only implement but to actually run.

There is an old article in Game Developer that did this very thing using a 4 player Risk clone. The results were very impressive. I''ll see if I can find the reference for you. I''ve also got papers in which this type of system was done to develop a checkers AI, snake game AI (the game where you have a snake which runs around a rectangular area and each time it eats a piece of food, it grows - goal is to get as much food as possible without crashing into a wall or body segment), Pac-Man and ghost AI, neural net architecture.

Sorry for the LONG post - this is a great interest of mine. I''d be more than happy to clarify or help with more info. Don''t hesitate to ask.

-Kirk

Ah, it''s just the answer I was looking for.

Yeah, I find the whole evolutionary-AI aspect fascinating too, although I''m afraid that genetic algorithms/neural-nets/etc. are pretty much just buzz-words to me at the moment. They sound funky and of unbounded potential, but I really don''t know enough about them to know their limitations, so sorry if my questions/ideas seem immature or of too high an expectation.

Questions :

- You mentioned that a section of creating the primitives was creating a set of (if..then) conditionals. How vital are these ? I can imagine that they add personality to the players (ie. retreat from an enemy player should they have less health than them).. but by adding them in, do they interrupt the linear flow of finding the optimum chromosome ?

- If I dedicated a chromosome to each individual player and ran the test numerous times, could chromosomes of distinctly different personalities evolve between the players of the same team, operating independantly ? Or would each chromosome represent one general "overmind".. (for lack of a less cheesy term)..

- Know any good books on the subject ?

Thanks ''eaps.
: msv.

In my opinion, the primitives should be as primitive as possible. For example, let's use the following primitives:

01 = IF...THEN such that the code immediately following is the conditional and the next code is the decision.

10 = ENEMY_TO_LEFT - returns true if an enemy is to the immediate left of the current position

11 = ENEMY_TO_RIGHT - returns true if an enemy is to the immediate right of the current position

00 = MOVE_RIGHT - forces the player to move to the immediate right.

So, a chromosome like:

011100

would translate to
IF (ENEMY_TO_RIGHT) THEN (MOVE_RIGHT)

Now, obviously you'd want a lot more primitives and the results could be a lot more complex, but it all becomes decision trees. Also, don't follow my example but rather make up your own representation. As long as you can go from representation to implementation, you're OK.

Remember also that this is an incredibly simplistic example. Consider what would happen and how this would look if we had 32 different primitives (6 bits per primitive) and a chromosome that was 600 bits long!

As for your second question, yes, you could get distinct personalities for players on the same team. The fitness function would need to take into consideration who is on what team and how they're interacting with each other. Again, this is fully up to you so you've got a wide array of possibilities. You just have to walk a thin line between complexity and simplicity. Too much either way causes problems.

Another answer to your question is that co-evolution can occur. For example, let's say I was making a Pac-Man game and letting the ghosts develop their decision AI by this method. If the Pac-Man follows a consistent pattern, then the ghosts will become adept at attacking that specific pattern. But, if we let the Pac-Man develop his AI in the same way, then to two will evolve simultaneously and will likely be a more general (and potentiall more robust) type of decision tree. By always changing the landscape during evolution, you push for more general approaches to emerge.

I've got a few good books but they're very academic. I've got some references from GD Mag, too. I'll try to get them together and post them ASAP.

-Kirk



Edited by - KirkD on October 5, 2001 3:55:03 PM

Edited by - KirkD on October 5, 2001 3:56:37 PM

Ok, here are some references:

GOOD book: Genetic Programming: On the Programming of Computer by Means of Natural Selection by John Koza. A fantastic (albeit dated) primer on evolutionary computation. This one has the Pac-Man example I mentioned. The first 100-150 pages are introductory and analytical, with the next 500+ being examples.

VERY academic book, but highly recommended: Evolutionary Computation vols 1 and 2, Thomas Back, et. al. Extremely good analytical, academic approach to understanding GAs and EC.

Game Developer Premier Issue, p51 - How to Grow a Starship Pilot. Good article on using GAs to develop a control system for a spaceship. The effect is similar to solving the traveling salesman problem.

Game Developer February/March 1996, p26 - Using Genetic Algorithms to Evolve Computer Opponents. This particular article is probably exactly what you need to read. This is the Risk clone I mentioned earlier and is an excellent article. Highly recommended!!

I've got both GDMag articles sitting in front of me, so let me know if you can't seem to get access. I'm sure we can find a way.

-Kirk


Edited by - KirkD on October 5, 2001 12:06:23 AM

Ferrettman,

Do you happen to have any other references or links to EC being used in this type of situation? Fun stuff!!

-Kirk