By using the "Function Call" system I described, it actually more closey resembles how DNA actually works.

In real DNA each codon (in natural animals these are made up of 3 base pairs, but scientists have recently made a DNA system that uses 4 base pairs) is a function that typically syas: Add this amino acid to the protein (there are quite a few others, but that is the main "function call").

Now the real flexability in using this type of system in an GA is that you can define the function to be whatever you want, and if you want to add in new function then this is as simple as putting in the new function into your progrma's code and assigning it a valid value an array elemnt can have.

The other thing this kind of system does is introduce competition into the genome. If you used your system where you just assigned a value to a particular variable as the genetic code, then what stoips that variable form becoming arbitarily large (upto the system's limits).

For example: In your system, what is to stop a mutation from doing this:

Before mutation:
S: 3
D: 4

After mutation
S: 4
D: 4

In my system for D to increase, there has to be some cost to other "codons" in the genetic code. The only way you could increase S to 4 would be to drop D to 3 (so one 'D' would mutate into an 'S').

This way, the genes of the creature ends up having to compete with each other and this creates a more interesting system, where as yours would create a system where every single value would rapidly increase without limit (except for the system limits).

Genetic Algorithms are about optimisation, not maximisation. For optimisation you need compeating aspects, otherwise the "optimal" value is the maximum value as there is no cost to maximise the value.

Quote:

Original post by Edtharan By using the "Function Call" system I described, it actually more closey resembles how DNA actually works. In real DNA each codon (in natural animals these are made up of 3 base pairs, but scientists have recently made a DNA system that uses 4 base pairs) is a function that typically syas: Add this amino acid to the protein (there are quite a few others, but that is the main "function call"). Now the real flexability in using this type of system in an GA is that you can define the function to be whatever you want, and if you want to add in new function then this is as simple as putting in the new function into your progrma's code and assigning it a valid value an array elemnt can have. The other thing this kind of system does is introduce competition into the genome. If you used your system where you just assigned a value to a particular variable as the genetic code, then what stoips that variable form becoming arbitarily large (upto the system's limits). For example: In your system, what is to stop a mutation from doing this: Before mutation: S: 3 D: 4 After mutation S: 4 D: 4 In my system for D to increase, there has to be some cost to other "codons" in the genetic code. The only way you could increase S to 4 would be to drop D to 3 (so one 'D' would mutate into an 'S'). This way, the genes of the creature ends up having to compete with each other and this creates a more interesting system, where as yours would create a system where every single value would rapidly increase without limit (except for the system limits). Genetic Algorithms are about optimisation, not maximisation. For optimisation you need compeating aspects, otherwise the "optimal" value is the maximum value as there is no cost to maximise the value.

Good point. But what is to stop increasing the size of the genome in any system? Don't they just evolve to have a larger genome so that they can have bigger numbers? The answer is of course that there are factors external to the genome that cause trade-offs. In reality, I think it's the ratio that determines the phenotype, not the absolute value, because more of everything gets balanced by slower production.

I have actually been careful to either define the numbers as being trade-offs, or to have external balance factors. I suppose what you're talking about is a global internal balance, which is an interesting idea. I intend to do that for the phyical characteristics so they only have a certian number of "food points" to distribute between sensors, food absobtion, thrusters and turning rate, because as you say it doesn't make sense for these to be unbounded.

For behavioral traits the trade-offs aren't so clear; it's not like being more passionate about something directly requires more of some resource. I suppose you could make the argument for behaviors competeing for brain-time, but even then, having arachniphobia (for example) doesn't take brain time when there are no spiders around. With that in mind, we should look at the instant to decide how the behaviors trade off. For example, if some tasty food is at 0 degrees, and a predator is at 90 degrees going towards the food, and you are going towards 120 degrees, what do you do? You can attach arbitrary unbounded importance to any of these factors, but you are constrained by the eventual fact of only being able to choose one direction to steer.

I havn't really taken the threat of unbounded traits seriously because I havn't had to. If I discover that certain genes get maximised under all circumstances, I'll either remove them from the equation and maximise that trait (as the population is supposed to be already optimised for a certain lifestyle), or find out what trade-off I failed to include and fix it. So far, however, the critters have managed to find trade-offs, and nothing has gone unstable.

As for your concern about my optimization being different from the original "string of functions", it wasn't intended to be different, I was just pointing out that the exact same semantics could be created by putting a certain sort of smarts in the functions that manipulate the genome. The idea was only to make it more space efficient, not to change the semantics.

Your idea of composing arbitrary functions to create the phenotype is a good one, I might do it that way if I do any major refactoring. Thanks!

Thanks for all the info on how DNA works, I think it will definitely be handy. I not sure I've mentioned it, but these critters are actually not earth-life, in fact they are not even based on chemistry (they are based on magic fields and stuff (insert hand waving)), so I'm not too concerned about being faithful to how life works here on earth. Besides, the genetic system is only a small implementation detail, I'm more concerned with making a fun casual game, not a sweet GA system (though I may want to do that some time).

This is not a reply to anything in particular, just some more info and some areas I'm looking for feedback in.

Control Scheme
The game is controlled entirely with the mouse. You move the mouse around and your predator adjusts facing to point directly at the mouse. The screen gets offset from the player by a bit towards the mouse, so that you can look far/near depending on where the mouse is.

Right now, you are always accelerating forward, proportional to the distance of the mouse from the centre of the screen. It used to be full accelleration on click, none otherwise. I forget why I changed it.

The player is modeled as an airfoil, so as you change direction, you get lift forces that tend to keep you going forward (for small turn rates). I have not modeled stalling, though there are similar things that seem to happen if you turn too quick. Like you can loose all speed quickly by getting sideways yo the wind, or you can end up flying backwards even.

You don't have to do anything special to catch a critter, just collide with it. I may put some more smarts on how you eat them, like a cap on how many you can eat per second or something.

This scheme works quite well, it feels very smoothand natural and people who have played find just flying around to be quite fun.

What does everyone think of this setup? Any alternate control schemes that could work? Any ideas to imporve it? Should I post the source so that people can try it out?

Score System and Energy Balance
When you catch a critter, you gain their energy. It costs energy to accelerate and change direction and stuff, so you are constantly losing energy. This implies you have to catch them at a certain rate to keep your energy going up. As they adapt to your presence, they will become harder to catch, eventually to the point where you are no longer gaining energy.

At this point (you have to figure out when this is) you are supposed to signal to go into low energy mode (or something) and fly out of the level, which will end the game and log your energy as your score.

What does everyone think of this? Should there be special abilities (like a speed boost) that use up more energy? What do you think of the player having to know when to walk away?

Critter Reproduction and Genetics
When critters get up to a certain amount of energy, they can either reproduce asexually, or use energy to advertise sexually (not implemented fully yet). They reproduce asexually by dividing (like bacteria), the children are slightly different. They reproduce sexually by meeting other critters that are also advertising to combine together into one with some kind of average of thier traits (uniform randomly wieghted average right now).

The physical traits I am planing to have are: sensor range, acceleration, food absorbing ability, and maneuverability (turn rate). These would be a trade-off, so more food absorb means less everything else.

I havn't decided on the behavior traits so much. basically it would be a bunch of numbers that decide what direction to turn, how much to accelerate, and whether to divide, advertise or just chill based on where the predator is, how fast it is going and in what direction, how much food we are getting right now, where the friends are, where sexually advertising friends are, what direction the food is, etc.

I want to keep the number of different genes to a minimum so that things evolve quickly.

Does anyone have ideas about what genes should or should not be included? Anything redundant in all this? Is sexual reproduction really necessary? If it is, is there a better system?


Any feedback on these would be great. Thanks!

Quote:

Good point. But what is to stop increasing the size of the genome in any system? Don't they just evolve to have a larger genome so that they can have bigger numbers? The answer is of course that there are factors external to the genome that cause trade-offs. In reality, I think it's the ratio that determines the phenotype, not the absolute value, because more of everything gets balanced by slower production.

The genome would be a fixed size (the size of the array).

It is possible to do this with variable sized genome, but it is more tricky to have the genes compete. The simplest way is to have the number of codons for a trait determine a ratio of that trait to the others (that way increaseing the size of the genome does not increase the total value of the stats, it just increases the resolution of the ratio) and to have some small disadvantage for having a long genome (more likely for a mutation that causes the long genome to break into a short genome on replication, or an enemgy cost). This disadvnatage must be small enough to allow the genome to increase in size a bit, but strong enough to prevent genomes becomeing too large for the system to handle.

It is a bit of a balancing act, but it can be done.

Quote:

I suppose what you're talking about is a global internal balance, which is an interesting idea. I intend to do that for the phyical characteristics so they only have a certian number of "food points" to distribute between sensors, food absobtion, thrusters and turning rate, because as you say it doesn't make sense for these to be unbounded.

Here is the basic idea of how you would do this:

If you have 4 traits (from your post):
F = Food Absorbing
R = Sensor Range
A = Acceleration
M = maneuverability (turn rate)

If you say that the largest value these could be is 100 (but the specific value would depend on what you have designed your game to be), then you would have a genome 100 codons (the array size would be 100 elements) long. The size of the array for any creature will always be 100 elemnts long.

This way if the entire array consisted of 100 'F', then the food absorbing trait would be at maximum. However, all the other traits would have to be at 0 (which you might not allow).

It is possible that even with a limit of 100 as the maximum value you can have an genome array greater than that, you just have to make sure that your program ignores any codons for a trait that is already at 100.

Quote:

For behavioral traits the trade-offs aren't so clear; it's not like being more passionate about something directly requires more of some resource. I suppose you could make the argument for behaviors competeing for brain-time, but even then, having arachniphobia (for example) doesn't take brain time when there are no spiders around. With that in mind, we should look at the instant to decide how the behaviors trade off. For example, if some tasty food is at 0 degrees, and a predator is at 90 degrees going towards the food, and you are going towards 120 degrees, what do you do? You can attach arbitrary unbounded importance to any of these factors, but you are constrained by the eventual fact of only being able to choose one direction to steer.

You are right, behavioural traits are more complex than physical characteristics and can't simply be encoded to compeat like the physical traits.

A solution I have used is to break the genome up into "Chromosomes" (not functionally the same as real chromosomes, but it works as an analogy).

What these "Chromosomes" are is section of the gene that are related. For instance, the Physical Traits can be encoded into their own Chromosome of a fixed length (although other chromosomes could be fixed or variable as needed) and this allows the physical traits to compeate wihtout disturbing any other information on encoded on other chromosomes.

What you will find is that behavious will have some variables that are associated with them that have to be optimised. The value can't be too big or too small, but somewhere in between these extremes and what you want is the GA to find this value (and this could change depending on the behaviours that other creatures have in your game).

So what you do is to introduce "Junk" codons into the GA. These codons, when read by the program do absolutly nothing. You then have each variable for your behaviours that you want to include in the GA as its own Chromosome (fixed or otherwise).

Now, when the GA reads the chromosome for a particular behavioural trait variable, you use a Codon value to indicate an increase in the variable and a Junk Codon to pad out the chromosome (that is don't increase the variable's value).

This also has the advantage of also allowing certain behavioural traits to have compeating traits.

eg: how often to turn left, to turn right ro to keep going straight ahead.
This coudl be encoded like this:
[LLLLRRRRSSSSSSSSSSJJ]
L = Chance to turn left
R = Chance to Turn Right
S = Move Straight ahead
J = junk (or don't move)

This would give
R = 4
L = 4
S = 10
out of 20
It would move forwatd 50% of the time, turn left 20% of the time, turn right 20% of the time and not move 10% of the time.

You can, of course get much more complex than this. You can use this to encode movement sequences (eg: LFRFLFR as a Zig-zag movement). And you can even encode conditional clauses as well (this is much more complex and probably would need several posts to describe it properly - it esentially means you create your own scripting/programing language!).

Quote:

Besides, the genetic system is only a small implementation detail, I'm more concerned with making a fun casual game, not a sweet GA system (though I may want to do that some time).

Yeah, using what I am talking about you can make a very powerful GA system, but most of what I am tlaking about would be overkill for most games, however, if breeding and evolution was to be a big part of the game then it probably would be aplicable. Doing it this way provides a very deep system, but for msot games, a shallow system is all that is needed.

Hmm, this sounds a bit like flOw, but in a different way hehe

To keep with the evolution theme, I'd suggest allowing the player's craft to evolve, and letting the player choose different evolutionary paths periodically to adapt to the game. These choice could include special abilities (stealth, speed boost, energy boost, ability to consume plants), or just stat increases (passive speed gain, size gain).

Allowing the player to progress and gain energy in different ways would cause the AI creatures to evolve in interesting ways, too. Instead of competing by avoiding you, they might try to seek you out to follow you to food sources, or try and hunt you (ambitious pricks), or simply eat more quickly than you do.

Randomly generated terrain would increase playability significantly, in my opinion. Add that if you ever have the time.

Out of curiosity, how many species does the game start with? Can they diverge? Can any species breed with any other?

Quote:

Original post by GiantGames To keep with the evolution theme, I'd suggest allowing the player's craft to evolve, and letting the player choose different evolutionary paths periodically to adapt to the game. These choice could include special abilities (stealth, speed boost, energy boost, ability to consume plants), or just stat increases (passive speed gain, size gain). Allowing the player to progress and gain energy in different ways would cause the AI creatures to evolve in interesting ways, too. Instead of competing by avoiding you, they might try to seek you out to follow you to food sources, or try and hunt you (ambitious pricks), or simply eat more quickly than you do. Randomly generated terrain would increase playability significantly, in my opinion. Add that if you ever have the time. Out of curiosity, how many species does the game start with? Can they diverge? Can any species breed with any other?

Thanks for the reply!

The player's avatar is an individual, so proper evolution is impossible, but I think the idea of letting the player actually change stats might be a good one. I have been thinking about this a bit, but I havn't thought of an elegent way to do it. The game is supposed to be just a simple arcade game, so I don't want to create too much complexity. If I can think of a simple mechanism (or anyone can suggest one) that makes sense in the game universe, I'll do it, but it's not a top priority.

There is only one species in the game (not including the player). I don't think they will seperate into species or anything, as there is no mechanism for that. I'm trying to keep it very simple. I don't think one player would be able to put enough pressure on multiple species to get them to eveolve.

There is no terrain. The game takes place high in the atmosphere of a planet like venus. I will probably randomly generate the backdrop (clouds n such) and the foreground cloud, though.

There's some more info in my other posts, read if you're intrested.