### DNA Modeled P.Random Numbers?

Posted:

**Mon Oct 06, 2014 6:57 pm UTC**Just because I was bored, I started trying to see if I could re-approach an old program involving the fitness of some random RTS units.

The units at their core only have a handful of stats:

HP, Armor, Damage, Num-Shots, Armor Piercing, Reload, Speed, Range

And these values were derived utilizing five random numbers and a "point buy" system: The first random would pick how many of the (remaining) points went to hitpoints, the next to armor, and so on.

The last couple of stats were derived based on the five random values (speed was the number of points left over, with some penalties for high HP and high Armor). AP was on an inverse of damage: lower damage, more Armor Piercing. I forget the exact math at the moment, but around 10 or 12 damage-per-shot was about when AP hit 0 (1 point of AP reduced the target's Armor by 2).

The result was pretty good. Basically the thing produces a random unit as "current best", then produce 10 units and faces those 10 off against 10 copies of the "current best." When one of the new ships beats the old ship by a certain margin (at least X% health left, X ended up being like 10, too much higher and the statistical odds were too far against) it becomes the current best and it repeats until it has a list of 7 (the original random unit is discarded). Then it tries to find a triangle within that list of 7. "Unit3 beating Unit2 beating Unit1 beating Unit3" for example (the only test that needs to run is 1 vs. 3, as "3 vs. 2" and "2 vs. 1" are known due to list order).

Usually takes around 10 to 15 seconds (although there are still some outliers I never managed to eliminate, so if it runs more than that without seeming to make progress, just refresh it and start over).

Last week I thought I'd revisit trying to do this using a genetic algorithm, rather than simply creating 10 unrelated units every time, each one making 5 calls to Math.random(). Or at least, try and work out what the underlying genetics system would be such that it would be possible to use the resulting values for said units. And while I've manage to cobble together a "DNA-like" object that will spit out a decently random number (there's quite a bias, but it was as close as I could get) the real problem is that it's almost impossible to breed for specific traits: the sequence by which the DNA string is translated down into a single 0-1 value is too unpredictable. A high-value crossed with a high-value has a very large statistical probability of swinging wildly. E.g. a 0.98 crossed with a 0.93 can result in a 0.47, even before mutations are considered!

Here's a few example fitness values which seem to just fluctuate rather than actually improve over time (all of these are compared against the same benchmark):

So the question is:

I want to go all the way back down into my genetic sequences and rework how a string of (essentially) letters gets translated into a single value from 0-1. I'm not going to bother posting what I have, as I'd rather not poison the well, so to speak. I feel that it's not uniform enough and too unpredictable to be worth keeping. I am looking for something that produces a reasonably unbiased result (if seeded randomly) and allows crossbreeding without distorting the values too much if they're already similar: a 0.9 and a 0.8 shouldn't cross and produce a 0.2, it defeats the whole point.

Speaking generically, what I'm looking for would be a system that looks like this:

The first class (GeneticIndividual) is pretty easy and is included for completeness. The tricky part is the Chromosome.Value() function.

(I suppose I've named things badly: chromosomes should be genes and genes should be peptides, but for a simplistic model that computes only a handful of values, I suppose it doesn't matter)

The units at their core only have a handful of stats:

HP, Armor, Damage, Num-Shots, Armor Piercing, Reload, Speed, Range

And these values were derived utilizing five random numbers and a "point buy" system: The first random would pick how many of the (remaining) points went to hitpoints, the next to armor, and so on.

The last couple of stats were derived based on the five random values (speed was the number of points left over, with some penalties for high HP and high Armor). AP was on an inverse of damage: lower damage, more Armor Piercing. I forget the exact math at the moment, but around 10 or 12 damage-per-shot was about when AP hit 0 (1 point of AP reduced the target's Armor by 2).

The result was pretty good. Basically the thing produces a random unit as "current best", then produce 10 units and faces those 10 off against 10 copies of the "current best." When one of the new ships beats the old ship by a certain margin (at least X% health left, X ended up being like 10, too much higher and the statistical odds were too far against) it becomes the current best and it repeats until it has a list of 7 (the original random unit is discarded). Then it tries to find a triangle within that list of 7. "Unit3 beating Unit2 beating Unit1 beating Unit3" for example (the only test that needs to run is 1 vs. 3, as "3 vs. 2" and "2 vs. 1" are known due to list order).

Usually takes around 10 to 15 seconds (although there are still some outliers I never managed to eliminate, so if it runs more than that without seeming to make progress, just refresh it and start over).

Last week I thought I'd revisit trying to do this using a genetic algorithm, rather than simply creating 10 unrelated units every time, each one making 5 calls to Math.random(). Or at least, try and work out what the underlying genetics system would be such that it would be possible to use the resulting values for said units. And while I've manage to cobble together a "DNA-like" object that will spit out a decently random number (there's quite a bias, but it was as close as I could get) the real problem is that it's almost impossible to breed for specific traits: the sequence by which the DNA string is translated down into a single 0-1 value is too unpredictable. A high-value crossed with a high-value has a very large statistical probability of swinging wildly. E.g. a 0.98 crossed with a 0.93 can result in a 0.47, even before mutations are considered!

Here's a few example fitness values which seem to just fluctuate rather than actually improve over time (all of these are compared against the same benchmark):

**Spoiler:**

So the question is:

I want to go all the way back down into my genetic sequences and rework how a string of (essentially) letters gets translated into a single value from 0-1. I'm not going to bother posting what I have, as I'd rather not poison the well, so to speak. I feel that it's not uniform enough and too unpredictable to be worth keeping. I am looking for something that produces a reasonably unbiased result (if seeded randomly) and allows crossbreeding without distorting the values too much if they're already similar: a 0.9 and a 0.8 shouldn't cross and produce a 0.2, it defeats the whole point.

Speaking generically, what I'm looking for would be a system that looks like this:

**Spoiler:**

The first class (GeneticIndividual) is pretty easy and is included for completeness. The tricky part is the Chromosome.Value() function.

(I suppose I've named things badly: chromosomes should be genes and genes should be peptides, but for a simplistic model that computes only a handful of values, I suppose it doesn't matter)