An introduction to Genetic Algorithms

An introduction to Genetic Algorithms
Author: TheCell
Description: This article introduces genetic algorithms and explains how they are related to game development and AI.

Post your discussions/comments here by clicking on Add Reply.

Excellent article I've always wanted to learn this stuff and how I have the opportunity.

While I was reading through the article, I didn't understand one thing: how do you determine which baby mutates? Is it random?

Basically, yes, it's random. Every baby have about 1% of being mutated, but it's not a strict rule. You can modify it for different results, like if stagnation happens too often, you can incrase the mutation rate, but a too high mutation rate won't do any good, because you won't keep the bests since they're always changed.

My few questions on Genetic stuff:

Wouldn't it take the computer a while to get better?
Should the children be able to compare themselves to others, and think hmm, I've got more of this and am more alive...
Wouldn't the game dev be a lot more assured the AI will turn out the right way if they just up the eyesight of half of them every 5 mins or something?
What if the AI ends up with a super peep that your peeps can't combat with?
Does this stuff apply to the AI's methods of doing things (ie playing with their own scripting)?

This sounds like tinkering fun!

<quote>Wouldn't it take the computer a while to get better?</quote>
Well, it's evolutive and adapatative. It sure can take a while, depending on when you make ALife mate. The more often, the quicker the adaptation/evolution.

<quote>Should the children be able to compare themselves to others, and think hmm, I've got more of this and am more alive...</quote>
As one children is born, he is considered as a part of the whole group, and by such, get an equal chance to mate(Before the Fitness is calculated).

<quote>Wouldn't the game dev be a lot more assured the AI will turn out the right way if they just up the eyesight of half of them every 5 mins or something?</quote>
Eyesight is a characteristic that we're sure the more you put in, the better it is. Genetic Algorithm is used for those uncertain amount, like how to distribute computer cycle between Evaluating a Threat, Planning an attack, Micromanaging, etc....But as I mentionned, Genetic Algorithm is doing things mother nature's way. If nobody needs eyesight better than 5 unit, chances are that eyesight will be kept at not much more than 5 unit(After all, the need to fly created wings...). You must not forget that everything that survive have an equal chance of mating. So, one with 5 of eyesight has as much chance to survive as one with 7. You'll enventually end up with creatures which all have 5 or 7(excluding mutated one).


<quote>What if the AI ends up with a super peep that your peeps can't combat with?</quote>
It's a simple matter of rules for fitness. You can define a simple rule which says : "If a Genome(Set of Chromosone for your A.I....Forgot to mention it in the article). beats too easily a player, it has less chance to mate". Thus, you can create an A.I. which is always in range with a player's skilll. But if a very skilled friend comes and play on his computer, he might finds the A.I. rather easy to defeat. But let him play some games, and the A.I. will eventually catch up.

<quote>Does this stuff apply to the AI's methods of doing things (ie playing with their own scripting)?</quote>
I'm not sure I understand, but I'll try to answer. Genetic Algorithm is used to get the best of the given rules. I've heard about some research about a Maze and some ALife Bug(can't find the site anymore). The rules were very simple. Chromosone consisted of a single Gene. Genes were the direction the bug was to take. Chromosone(gene) were always read in the same order. The bug was placed in the begining of the maze, and must reach the end. The longer it walked before hitting a wall, the better. if it was going into a wall, it's course ended here, and time was recorded. Those are very simple rules, but it can make a bug go through a maze withouth touching a wall. Going back and forth many times, I admit, but going through it nevertheless. But improvement could have been made. Implemenanting a way to stop the timer of a bug if it has been on the same square 2 time would prevent them from going back on their feet. This was just an exemple at what Genetic Algorithm can do with the right set of rules and good implementation. I must admit though that it was more like trial/error, but I still call it genetic algorithm. But as to know if Genetic Algorithm is able to modify a script, it all depends on the implementation. I think it would be very hard, but hey, who doesn't like challenge?

I can see how genetic algorithms work when applied to values when applied to functions, but can the functions themselves become adaptive?

this site is really getting filled with very useful content. thanks for all the people who contributed so far. way to go !!!

Moomin : To be completely honest, I don't know. I know for sure that value can be adpated, and you could use these value to determine what function to use(as in the maze research). But as to use function as gene value, I really don't know. You can always use something like "if (GeneValue == 0) SomeFunction; if (GeneValue == 1) SomeOtherFunction;" etc....

Moomin: That's what I was trying to get at but didn't word to well.

I was imagining an AI in a game that was scripted to use genetic algorithms. And, each AI had it's own little script (all the same at the start). Now the AI could "mutate" it's script by adding randomly generated (within limits) statements now and again, or maybe changing values for the better or worse. Of course like real life this would cripple many, but it's just the same as mother nature (And her way is usually the best when it comes to programming ). Then, the better of course get passed on. For this to work I think that the AI needs to feed of useful action (ie moving, killing, making money ect..) and of course use up this mana stash. The only worry is that an AI could get crippled, but also criple it's feeding system making some sort of useless zombie.. With this in mind, I have to have a go at Lua!

Nice article!

Just a short question TheCell...Have you tried to use GA's to controll the weighting in neural networks?
And if yes...how did they performe, compared for example to backpropagation methods?

I've never really worked with Neural Network for now. I've read on them for some time now, but it's only starting to trigger in my head on how to use them. I know the basis of them, like the weight, inputs, layer, learning process, synapse, etc... but as for how to use it, it's still a mystery for me. As soon as I'm enlightned, expect an article from me.

update : I've found a site(http://www.ai-junkie.com) where the guy use Genetic Algorithm to update the weight on his synapse to get an accurate output from his neural network. The exact page is http://www.ai-junkie.com/nnt7.html

Well, I think NNs are very cool(), logical, and easy to understand; my only problem is, I don't understand the backpropagation...

I'll give it another try this week(already a few months since I tried to code one...)...
if I'm successfull, I might write an article about it

Hi!

I've just read the article and liked it a lot! However I'm wondering how this concept could be used in "real" Situations to develop the AI for a game.

As far as I understood it I need to allow the AI to asses the situation. Based on the situation and some parameters defined by it's genes the AI decides what is to do. So I need methods to get the information about the situation, methods to perform actions and "something" that links both. (Just to do a rough scetch)

Well, now this "something" that controlls everything needs to be parameter based because only these parameters will evolve... So I wonder what's the best way to aproach this?

Let's take a simple Pong game as an example... is it possible to use genetic algorithms for an AI controlling that pannel? How would you approach it?
If not... what are the applications where GA could be usefull?

Thanks,
Lith

Well, I think it could be possible. You could use genetic algorithm to make it actually "learn" the game. The gene wouldn't be much complexe, and would probably describe the obvious. You could have 3 gene, one to use if the ball is below the panel, one to use when the ball is above the pannel, and one to use when the ball is directly in front of the paddle. The gene could describe the action to do. ex: "Move up", "stay here" and "Move Down". The fitness rules would be fairly simple : if it wins, the greater the chances to mate. The results could be that at first, the paddle would probably be very stupid, like moving the paddle up while the ball is below it. But eventually, you will end up with a paddle that can follow a ball.

But a more appropriate way to use GA in pong would be to determine what setting an AI will use against a player. Like if someone is very very good at pong, you can use GA to tweak your setting so that the AI Paddle move faster. You could also have a gene that enable or disable trajectory prediction. So, depending on your gene, your AI could simply try to stay even with the balls, or place itself according to the trajectory. If I resume, a bad pong player would more likely end up with a slow paddle, with no trajectory prediction. But when the player gets better, the AI would adapt itself, increasing it's speed. When the player gets even better, the AI could even add trajectory prediction.
But you might ask : "What if a player is very, very bad? He could ends up playing against a very good GA, and so, never win?"
Well, that might be true, but only for some time. Remember that if your rules are "If it wins, it has better chance to mate", every set of gene would have the same chance of mating. So, your bad player would play against both poor and good AI. He would eventually(I hope) progress, and the more he progress, the better the AI.
In other word, I could compare it to something like this. Let's say that we rate the player's skill. 1 is worst, 10 is best. The same goes for the AI. Now, if a player of skill 1 try to play the game, those with skills from 1 to 10 have equale chance of mating since they will all win the game(presumably). But let's say that a player with a skill of 5 now plays the game. AI from skills 5 to 10 have better chance to mate than those from 1 to 4, since it's more likely that 1 to 4 will lose. And now, if a player of skill 10 play, Probably only 10 will have a chance to mate, since it's the only AI that stand a chance against him.
Translated back to GA, skills are in fact chromosone(sets of gene). Those who lost against a player of average skill are less likely to mate than those with better skill.

The problem we end up with here is that the player will always play with someone better than him. One way to prevent it is to adjust your fiteness rules. Here, the rule chosen was "if it wins, it has better chance to mate". It doesn't make it very adaptative.... What would be best is that the more a chromosone bounce balls back, the better the chance to mate. So, if an AI either win too easily, or loose too fast, chances are that it won't mate. Even though the player will still play against stronger and weaker AI, most of them will be about as good as him. As I once said, everything is in the rule of fitness. Define good rules of fitness, and your AI will adapt to your player's skill.

TheCell

when ever i read Genetic Algorithms i think i read Generic Algorithms.. too much c++ and templates for me

nice to see stuff about geneTic algos on the page, i'll have to read it once i got awake

Sorry, that it took me such a long time to reply! I've had no internet over the weekend.

Your Pong-Example was very usefull in showing the pro's and con's of genetic Algorithm.
The problem in my eyes is that the AI can't do anything that is not allready implemented. It won't learn to precalculate the movement of the ball if it's not programmed allready. So basically the GA doesn't do more than adopting it's predetermined behaviour to a situation/quest, right?

I've been thinking about the second example, where the AI is adopting to the players skill. Is this really usefull? I mean, if I play against an AI it will take quite a time to adopt to my skills through mating. And these games might be pretty frustrating... Wouldn't it be easier to implement the AI thatway that you can adjust it's strength in play? Let's take a strategy game as example. If the players armie is bigger then the AI armie you could just switch to the next level... (reduce the delay between building tanks or try cut the players supplie-support - whatever!) if the AI's army is stronger decrease the level... thatway every game would be interesting!

I guess I'm just missing the power of the concept! =)

Still, it's very interesting. I think I'll implement just some little playground to make some experience with it. Just some little desktop-evolution thing!
Perhaps, with the concept in mind, I'll won't miss the oportunities where GA comes in handy!

-lith

Well, it all depends on where you implement your GA. You could actually make its "guess" better the trajectory of the ball. You could simply do a little multiplication of your results of your trajectory prediction by a number. Let's say you have an X and Y axis for your pong game. You want to predict where the ball on the Y axis, since the X axis is always at the same place(usually just before the paddle). You can establish a true trajectory prediciton algorithm, which predict the Y value that the ball will be, and make it multiplied by a number(which I will call "M"). As you you might imagine, the best number for M would probably be 1, since 1 * N = N, and you want a prediction as close as possible to N. You could set 2 genes, one to represent a number from 0 to 63, and another gene that represents another number from 0 to 63. when you multiply both number, you would get your M. So, whenever you make a trajectory prediction, you would end up with N * M/1000. You take the difference between N(the desired results) and M/1000. The bigger the difference, the less likely that this set of gene has to reproduce. Hence, your GA would adapt itself to be more accurate.

But as to learning, I would recommend reading about Neural Network. I mentionned in another post that I'm currently working at an article about Neural Network, but if you can't wait until then, you can always PM me your question, or ask them directly there.

Hi i'm studying math and I'm really interested on this topic. I truly like the article but I need some more help of you all. I'm making my thesis on Game Theory and I desperatedly need some help if any of you had ever related Game Theory with genetic algorithms i.e: solve a problem modeled by game theory using genetic algorithms?? Had any of you ever done it or ever seen such a mix, cause all I have too basic papers and i need some help. Please help me......

Hi,

Just wondering, what's the difference between GA and EA (evolutive algorithms). If anyone has any resources i would be gratefull.

Kenny66

Hello,

I think there is much more things to say about Genetic Algorithms in your introduction. the baseline algorithm can be deeply improved at each state. Moreover, It might be interesting discussing a little about Genetic Programming (Automatic generation of trees such as programm trees) and especialy Evolutionnary Strategies (genetic algorithm in continuous spaces)

Also, you should not consider too much the relation to the actual Darwin's evolution theory. More recombination (mutation,crossover) methods exists and have different implications in different contexts that may not happen in real life. The representation of the problem also have a real impact on the possibility to find a solution. You might want to insist more on it.

Anyway, it is allways realy nice to have people share their knowledge, so, i thank you for your good job.

S.