I just started reading about Genetic Algorithm and I sort of understand the basic concept of it. What I am unsure about is how to use the genetic algorithm. Here is one example. You have a character at point A and you want to move it to point B. You can encode some directions in the chromosome and check to see if the fitness score is equal to 1. From my understanding once you get a fitness score of 1, you then tell your character to follow the path encoded in the chromosome. If there are no fitness scores of 1 in the initial population, then you do the crossover and mutation and continue until there is a score of 1. Did I get that right? What if there are no possible paths from point A to point B? Does it just keep on running until it hits a set number for max generations and then the character never moves? What I want is to have the character wander around but progress toward the end point even though there is no path. How would I do this? At the max generation, move according to the chromosome with the highest fitness score?

A genetic algorithm is like other algorithms a way of processing input data and receiving an output (genetic algorithms are used to acquire approximate results if perfect solutions can't be guaranteed by other means efficiently). As you have described a genetic algorithm runs until a perfect solution is found or a maximum number of iterations has been hit. Therefore given the problem of finsing a path from to B the output will be the best path it can find. If you want the character to walk around aimlessly slowly progressing towards B then this is some form of behaviour simulation which is another algorithm that perhaps takes the path calculated by the genetic algorithm as input. Perhaps it will also use the map as another input.
The bottomlin s you need to create a behaviour simulation. You can either read up on papers about your specfic application or just use your imagination. For instance you could randomly alter the direction vector by rotating slightly every time frame while giving the 'correct' direction a higher probability. If no path is found then there are no preferences or perhaps the direct path through a wall is used and the character will get stuck. It's up to you, this is probably not a very nice behaviour algorithm but it should make it clear what direction you could go towards

Quote: Original post by dukon
You have a character at point A and you want to move it to point B.

Genetic algorithms are generally a very poor match for path-finding or steering problems. Generally they are for optimisation purposes, ie. some sort of task where it's easy to see how different approaches yield different degrees of success and failure, and combining aspects of the approaches to maximise the degree of success.

Quote: You can encode some directions in the chromosome and check to see if the fitness score is equal to 1.

It's worth noting that no genetic algorithm is ever guaranteed to find you a fitness score of 1 (where 1 in your situation presumably means complete success). You have to choose the cut-off point, whether that is a maximum number of generations, process execution time in seconds, or a minimum fitness level to reach.

Quote: If there are no fitness scores of 1 in the initial population, then you do the crossover and mutation and continue until there is a score of 1.

Every generation, you perform the crossover and mutation, hopefully bettering the population until you reach your terminating condition.

Quote: What if there are no possible paths from point A to point B? Does it just keep on running until it hits a set number for max generations and then the character never moves?

Yes. Genetic algorithms are not specific to path finding and have no notion of your need to have a character move, nor can they know whether reaching your chosen stopping condition is possible or practical. They just continue to attempt to improve the fitness of the population, generation after generation.

Quote: What I want is to have the character wander around but progress toward the end point even though there is no path. How would I do this? At the max generation, move according to the chromosome with the highest fitness score?

That sounds reasonable to me.

From what I remember about genetic algorithms, they're a good approach if you have a situation where you can easily express the problem as a bunch of small modifiable little elements (the "genes"), and you can also devise a fitness function for expressing how good the situation is in a way that a better situation almost always results in a better score - even if it's just a tiny little bit. It works well if that fitness function will gradually increase little by little as the situation gets better, as this small increase in the score will ease the generations of samples towards ever better results.

A good problem for genetic algorithm is timetabling a school, where you've got maybe a thousand students, several dozen teachers, a wide variety of classrooms and classes to teach, and you've got to budget everyone's time appropriately. It isn't too hard to come up with a good algorithm for rating a timetable for how well it gives everyone the classes they need to take and where they are held, and you can add lots of little details like the amount of load on a particular day or how far people have to walk between classes. Get the fitness algorithm right and you can get a really good timetable from a genetic algorithm.

A hard problem to solve with genetic algorithm is general A.I. for a soccer game, if you're going from the very base level using simple commands like "sense ball", "move" and "kick" as your genes. The problem with this is that it's very hard to come up with a fitness function that smoothly scales from low to high scores. Your starting set of random genes for a team will likely be as dumb as a rock, and it's hard to rank a team that doesn't move at all from one that just spins on the spot.

For something like path finding there are a bunch of other solutions that can solve the problem much better than a generic algorithm would. Unless you're trying to solve this as a learning exercise I'd be using another approach.

Quote: Original post by Trapper Zoid
A hard problem to solve with genetic algorithm is general A.I. for a soccer game, if you're going from the very base level using simple commands like "sense ball", "move" and "kick" as your genes. The problem with this is that it's very hard to come up with a fitness function that smoothly scales from low to high scores. Your starting set of random genes for a team will likely be as dumb as a rock, and it's hard to rank a team that doesn't move at all from one that just spins on the spot.

I did actually use a GA to evolve the AI for a (really simple) football game once. The AI was basically just a bunch of steering behaviors - defense was made up of ones like "move back while", "approach ball holder to tackle", "cover attacker to intercept pass", attacking was stuff like "move up pitch", "move into free space" etc.

The "genes" for the GA were the configs of the individual steering behaviors (like the threshold distance for what was considered "free space") and the weights which determined the relative strength of the behaviors. It actually evolved really well - hand-picked values were ok but pretty dumb even after a lot of tweeking, but leaving the GA running overnight produced a really good AI which was very difficult to beat. Along the way were all sorts of intermediate AIs which would have been good for various difficulty levels.

The fun bit was when it evolved to exploit flaws in the actual gameplay model. At first players could pass as soon as they received the ball, which led to a team which would pass the ball around instantly and never actually dribble. It'd bounce madly around the team for about ten seconds until one of them got a clear shot at goal and stuck it in. Completely indefensible. [grin]

Heh, nice. Most of the attempts I've seen to develop that kind of AI with genetic algorithms tend to result in teams of royally stupid agents, where it takes three days just to get one team that even bother to move. That might just have been the particular examples I've seen though; I haven't attempted to make a team AI with a GA myself. I'd wager it's down to the skill in which you select the rule set for the genes and the fitness function - but devising the fitness function will be about as hard as just hardwiring up the rules yourself.

I think my fitness function was really simple - I just played two teams against each other and took the winner. [grin] Of course since this was a really simple football game (coloured squares on a big green rectangle) I could get away with mildly wonky behaviour which would look hideous if they were proper 3d animated characters. Great for a football management sim but probably not workable if you wanted a playable game like FIFA.

You're right though - getting good results out of a GA is all about the rules for the genes and a good fitness function, both of which are something of a black art.

That might explain the difference. The example I'm thinking of was closer to a robotic simulation. All the players knew were roughly where the nearest players were and the ball if it was within sight, and the commands you could give were along the lines of "kick the ball at this strength", not "pass the ball to player X". So the players had to learn a fair amount just to kick the ball, such as spotting the ball, moving up close to it, aiming in the right direction and then doing a kick command.

The guy who was trying a GA approach didn't seem to have pretty sophisticated teams. The most developed team I saw had developed mad spinning-on-the-spot skills, beating their opponents stand-still-and-do-nothing skills. It wasn't the most exciting simulated match of soccer I've seen.

Quote: Original post by Trapper Zoid
That might explain the difference. The example I'm thinking of was closer to a robotic simulation. All the players knew were roughly where the nearest players were and the ball if it was within sight, and the commands you could give were along the lines of "kick the ball at this strength", not "pass the ball to player X". So the players had to learn a fair amount just to kick the ball, such as spotting the ball, moving up close to it, aiming in the right direction and then doing a kick command.

The guy who was trying a GA approach didn't seem to have pretty sophisticated teams. The most developed team I saw had developed mad spinning-on-the-spot skills, beating their opponents stand-still-and-do-nothing skills. It wasn't the most exciting simulated match of soccer I've seen.

But if you left it running for a thousand years...

you guys are really deep and hyper intelligent.
i have brain envy