Was musing the other day at the dinner table, thinking of concepts for using GAs for AIs. I was wondering if we could start a discussion here on the possibilities of doing so. The game that I've been thinking of making is a 2D inertia-physics space sim, and using GAs for the AIs to "evolve" into a playing style that is best against the user in the SP campaign seems like a unique idea. My thoughts include the binary genetic code representing things like aggressiveness, favored tactics (jinky maneuvering, setting up good shots, etc.) and teamwork (AIs can send messages to each other, so whether AIs "work as a team" or not would be something to consider). I'm at a loss, though, as to how they should evolve. Genetic modifiers I know, but in terms of where to apply them? All the enemies (should) be killed each level, so it's not like they survive to reproduce. Maybe ones that do the best on each level have a higher likelihood of being carried on and mutated for the next one. If anyone else has thoughts on this subject, feel free to speak up. =)

Well, a pure genetic algorithm implementation would require *many* iterations/generations of enemies.

What you describe could probably be better implemented with a symbolic list of tactics ordered by priority which is then modified by a kind of reinforcment learning. For example, the enemy could try one tactic (chosen randomly but depending on priority or maybe by some predefined rules) and if it successful this tactic's priority is increased otherwise it is decreased. This would actually be able to adapt during a single game round.

IIRC Dark Reign did something similar to this.

Yeah, I think a "true" GA wouldn't work for anything short of Civ or Spore, probably. =)

But adapting enemies, using a variation upon a GA, might be possible. For example, the possibility I'm considering right now has "points" that AIs have allocated towards certain attributes - like aggressiveness, energy saving, etc., all things that could be characterized as attributes of a player. Shifting those points around (take one from aggressiveness, add one to maneuvering capability) could be used as a kind of hack-GA. =)

You may be able to create a model that competes well against a player, but uses such a strange strategy that it reduces immersion/fun. Just something to remember when using machine learning techniques for agent behavior.

I've used a GA implementation in chess, it works quite well. GA in games is fun, but applying it to the stock market is even better. :D

Hah, maybe I should check up on that...

Well, you really don't have to be stuck on using a GA in binary form. You can have GAs that run on real coded values as well. There's really no issue with iterations and such.

If you're coding in attributes, then what you can do is have an elitist GA. This is kind of unorthodox, but you can try this.

Let's say you have 25 enemy planes/space ships or whatever. You can then initialize them heuristically or randomly at first. Then when a ship gets blown up, the others will iterate, perform crossover and reproduce or simply, re-adapt their behavior. In this sense, the fitness function becomes implicit as to survival. So, the longer a ship stays alive or kills more user ships even, the more it gets to reproduce and the more of its attributes will spread through the population. So, the last ship left will most likely have the best combination.

Then what you can do is use the last ship that was blown up in the last wave of attacks to seed the population of the next wave of attacks.

This case, you'll probably have a generational GA where the worst fit member is constantly kicked out, which will be the ship that gets blown up. While the surviving ships reproduce and are replaced by their offspring.

Now, how does that sound. :p

wow - this sounds EXACTLY like the concept for the game I've been working on... cool! Nice to know someone else thinks the same way.

That's true. Which is why you then throw in a tournament selection for the surviving ones based on a fitness assigned to them. This can be a combination of the health they have left, the number of kills, etc. That way, though you favor the actual acts of evasion, but you also penalize not killing.

I have always liked the idea of each enemy having a completlly different way of thinking. So I think, ofcourse just opinion. You could make multiple algorithms for all enemies. And at each level every enemy get's a style of AI algorithm choosen at computer psuedo random. Which means nobody controls the outcome at all, and it is never reaches a repition. I have always wanted to do this in a game, and have sorta figured out how to go about that.

For instance lets say we set the seed of a random long variable to the possible number of different AI's to choose from. 25. Then every enemy at the start of each level picks an algorithm to choose at psuedo random. This is like encryption/decryption of files. In fact when I made my program Encryptonite V1.0 that is when I got the brainstorm of having enemies having psuedo random intelligence. Yes, it's nothing new, but I would still like to see it implemented in a game that I make in the near future, or if you use it.

Any ways getting back to the statement. When every enemy picks an algorithm at psuedo random they may go over the long in which you have set. No worries just set an if statement saying.

if(code_to_test_for_algorithm > set_seed_of_pseudo_random) code_to_text_for_alogrithm-= set_seed_of_pseudo_random;

Ofcourse I do not know the syntex to use in C++ but in java you would make a random mehtod

Random gen = new Random(the seed); //the seed equalling the number of algorithms.

int a - f; // enemies psuedo random integer.

a - f gen.nextInt(the seed); //pick random number round to an integer.

I think this would really make a game exciting, and completlly hard to beat if the algorithms themselve's are really different, and difficult to follow.

But remember this is always just an idea.

For my help in programming, email me finch17@gmail.com