DNA Modeled P.Random Numbers?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Draco18s
Posts: 84
Joined: Fri Oct 03, 2008 7:50 am UTC

DNA Modeled P.Random Numbers?

Postby Draco18s » 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):
Spoiler:
Best gen4 fitness: 2.325829719289967
Best gen5 fitness: 2.849749655503425
Best gen6 fitness: 1.8156386771185575
Best gen7 fitness: 2.4243942260722515
Best gen8 fitness: 2.618432234446802
Best gen9 fitness: 2.6300236619842394
Best gen10 fitness: 2.5538738996312236
Best gen11 fitness: 3.461977161114054
Best gen12 fitness: 2.9044328718347066
Best gen13 fitness: 2.5803676560635456
Best gen14 fitness: 2.7016055327333994
Best gen15 fitness: 2.3585239337369277
Best gen16 fitness: 2.4504740185933627
Best gen17 fitness: 2.5790694951817534
Best gen18 fitness: 2.4247207122059327
Best gen19 fitness: 2.550046341025232
Best gen20 fitness: 2.5837461225292833
Best gen21 fitness: 3.1275774110415187


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:

Code: Select all

//pseudocode
class GeneticIndividual {
    mother:Vector<Chromosome>;
    father:Vector<Chromosome>;
    public valueOfChromosome(c:int):float {
        //should determine which chromosome between is dominant (mother[c] or father[c]) and return its value
    }
    public static breed(a:GeneticIndividual, b:GeneticIndividual):GeneticIndividual {
        child:GeneticData = new GeneticData();
        //randomly pick chromosomes from parents (including crossovers)
        //a.mother[i] + a.father[i] -> child.mother[i] ; AABAACCABD + ACDDABCCAD => AABAABCCAD
        //b.mother[i] + b.father[i] -> child.father[i] ; DCABCCDAAA + BBABDCCABC => DCABCCCABC
        //perform mutations, if any
        //AABAABCCAD => AABAABCCAC (last letter)
        //DCABCCCABC => DCABCCCABC (none)
        return child;
    }
}

class Chromosome {
    genes:Vector<int>;//char, string, whatever.  Ints are simple though
   
    public function Value():float{ /*returns a value 0-1*/
        v:float = 0;
        foreach(gene in genes) {
            //modify v
        }
        return v;
    }
}


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)

User avatar
PM 2Ring
Posts: 3619
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: DNA Modeled P.Random Numbers?

Postby PM 2Ring » Fri Oct 10, 2014 1:30 am UTC

To reduce the unpredictability, rather than using a random source that essentially produces white noise perhaps you could use one that produces Brownian noise, or something in-between. </guess>

Draco18s
Posts: 84
Joined: Fri Oct 03, 2008 7:50 am UTC

Re: DNA Modeled P.Random Numbers?

Postby Draco18s » Fri Oct 10, 2014 11:38 pm UTC

Hrm. I'll try giving that a shot.

User avatar
phillip1882
Posts: 94
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: DNA Modeled P.Random Numbers?

Postby phillip1882 » Fri Oct 24, 2014 8:55 pm UTC

hmm. sounds difficult. let's say I have two ships call them, ship A and ship B. ship A wins against most high speed high damage ships, but is weak against high armor, high hit-points. whereas ship B is good against high range and high num-shot ships, but is weak against high armor piercing, high reload.
if i try to cross these two ships, i could easily get a horrible ship. i don't see any easy way to avoid this problem.
never the less, here would be my approach.

Code: Select all

import math

def chromosome(gene):
   k = []
   total = 0.0
   v = 1.0
   for i in range(0,len(gene)):
      k += [ord(gene[i])+128]
      total += k[i]
   for i in range(0,len(k)):
      v *= k[i]/total
   v = math.power(v,1.0/len(gene))
   return v
bitcoin address: 1B73mjAguoK9ATwVjGcy2LasyfG9xtLGsq

Draco18s
Posts: 84
Joined: Fri Oct 03, 2008 7:50 am UTC

Re: DNA Modeled P.Random Numbers?

Postby Draco18s » Tue Oct 28, 2014 7:05 pm UTC

*Circles back around to this again*
Still playing around with the brownian motion idea. I didn't get to trying that out until today. So far, so good. A purely random collection of genes end up with a pretty even distribution on the 0-1 spectrum, only 8% variance from an expected average (that is, out of 5000 results, there should be 250 in each 0.05 delta band, and the largest count is only 272 and the smallest 227). Compared to the prior example, this is fantastic.

Still need to see how they breed.

Faux edit:
Hrmm...after removing some code that was done to make fewer crossovers with the old genetic information so that it's back to "pick one at random, then at a random point, switch" the results are...worth considering. Two values close together have crossbreeds that are more clustered than two values that are far apart crossbreeds (that is, a result of 0.8 crossed with a result of 0.4 have a wide range of resulting crosses from 0.01 to 0.98, but a 0.62 and a 0.67 cross to have values clustered around 0.6 and between 0.5 and 0.7). Its hard to gather good data to be sure, but anecdotally it looks good.

phillip1882 wrote:hmm. sounds difficult. let's say I have two ships call them, ship A and ship B. ship A wins against most high speed high damage ships, but is weak against high armor, high hit-points. whereas ship B is good against high range and high num-shot ships, but is weak against high armor piercing, high reload.
if i try to cross these two ships, i could easily get a horrible ship. i don't see any easy way to avoid this problem.
never the less, here would be my approach.


Well. In that example, both of those ships are good against different things, so...I wouldn't expect them to breed well.

User avatar
PM 2Ring
Posts: 3619
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: DNA Modeled P.Random Numbers?

Postby PM 2Ring » Thu Oct 30, 2014 11:04 am UTC

Draco18s wrote:Still playing around with the brownian motion idea. [...] Compared to the prior example, this is fantastic.


Excellent!

Draco18s
Posts: 84
Joined: Fri Oct 03, 2008 7:50 am UTC

Re: DNA Modeled P.Random Numbers?

Postby Draco18s » Thu Oct 05, 2017 5:24 am UTC

Come my minion / Rise for your master / Let your evil shine!

Jebus Crhist its been 3 years since I started this thread, but I found something that works.

What I found probably won't work for the scenario I originally had, at least not in a clean 1:1 way, but it could probably be adapted.

A while back my Pathfinder GM saw this thread about using a Harrow Deck tarrot reading to generate attributes for Pathfinder characters. Pretty cool, our current campaign has such characters.* Anyway, on a 5 hour drive back home today I had some time for thinky thoughs and I realized I could represent a spread linearly and use that as a chromosome. Take two of them, do a crossover, read the results as a third spread (or a fourth, as a crossover has two results: A1+B2 / B1+A2).

It works

Parent 1 . . . Parent 2 . . . ChildA . . . ChildB
STR: 10 . . . .STR: 11 . . . STR: 9 . . . STR: 10
DEX: 14 . . . .DEX: 14 . . . DEX: 15 . . .DEX: 16
CON: 14 . . . CON: 16 . . . CON: 15 . . CON: 15
INT: 14 . . . .INT: 13 . . . .INT: 16 . . .INT: 9
WIS: 11 . . . WIS: 13 . . . .WIS: 11 . . WIS: 14
CHA: 13 . . . CHA: 13 . . . CHA: 11 . . CHA: 11

These numbers aren't a perfect 1:1 with the rules the guy came up with, as I wrote a C# program to handle things and I made things more symmetrical between the suits** and stuffed the unique cards into the same spots in each suit (ease of doing the read via code, rather than having to special-case every card). But the concept works. The INT-9 on ChildB is unusual, but not completely crazy. Wis got enhanced slightly above Parent 2's value, as did Dex, so there was bound to be a shortcoming somewhere and it turned up in Int.

I'll be fixing up the code some more tomorrow, I'm shy two suits worth of unique cards (I previously implemented the system for 4 stats and did a quick re-expansion to six and the unique cards require more than casual effort) as well as providing a UI to make it easier to generate and combine (currently I have to generate 2 random spreads, write down the values, and manually plug them back in).

*Except mine because my 6 hp kobold survived a literal party wipe. I did a spread anyway. Fate handed me the Survivor card.

**His cards are balanced, but asymmetrical (e.g. Suit-A/Val6 and Suit-B/Val6 don't necessarily match up, one could be +STR/-CON the other could be +CON/-INT). Whereas mine is symmetrical, (e.g. +STR/-CON ~= +CON/-DEX). My code also says "negative tokens? eh, sure" whereas the tabletop is "execute as best as you can, player's choice." My code can't make choices, so it just goes into debt. It means a stat of 4 can pop out, but as I plan to only be using the results as a guideline, that's not a problem.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests