| Home Page | Recent Changes | Preferences

# Adventures In GP Episode III

... continuing on from Adventures in GP Episode II

The mutation genetic operation is used fairly sparingly in the breeding process and works by chosing a node at random then replacing the tree below it by new randomly generated code. It's pretty straightforeward:

    function gene mutate( gene g1)
    {
     // chose a node at random and replace with new random subtree

     local int numnodes, nodenum,i;
     local gpnode root1,target;
     local gene result;
     Local string s1;

     initfitstats(result);

     // grow tree from gene
     root1=spawn(class'gpnode');
     root1.ReadFromString(g1.code);

     // find out how many nodes are in the tree we're mutating
     root1.countnodes(numnodes);

     // pick one at random
     nodenum=rand(numnodes-1)+2;

     // get reference to target node
     target=root1.findnode(nodenum);

     // clear subtree below target node
     target.prune();

     // grow new subtree
     target.RandomGrow(target.depth,maxdepth);

     // write out new tree
     root1.WriteToString(result.code);

     // clean up
     root1.prune();
     root1.Destroy();

     return(result);
    }

So, having coded up routines to mangle GP trees in various ways there's a need for something to actually organise the planned orgy of interbreeding. Sorting the array in order of performance sounds like a good idea to start with so why not break out a good old bubblesort, I know there are quicker ways but this only gets done fairly rarely and our array isn't that huge so what the heck:

    function sortgenes()
    {
      local int i,j;

      for(i=0;i<599;i++)
        for(j=0;j<(599-i);J++)
            if(eval(pool[i+1]) > eval(pool[i])) swap(i,i+1);

    }

    function float eval( gene g1)
    {
    // evaluate fitness of gene
    // submitted.
    // define in subclass

    local float result;
    local  float playedVhumans, playedVbots;

    playedVhumans = g1.stats.GameswonVhumans + g1.stats.GameslostVhumans;
    playedvbots = g1.stats.gameswonVbots + g1.stats.gameslostVbots;

    if( playedVhumans ==0 ) playedVHumans=1;   // to avoid divide by zeros
    if( playedVbots ==0) playedVbots=1;

    result = (g1.stats.gameswonVbots / playedvbots) + 2 * (g1.stats.gameswonVhumans / playedVhumans) ;

    return(result);
    }

    function swap( int idx1, int idx2)
    {
     // swap over two genes in pool
     // define in subclass
     local gene temp;

     temp=pool[idx1];
     pool[idx1]=pool[idx2];
     pool[idx2]=temp;
     pool[idx1].PoolIdx=idx1;
     pool[idx2].PoolIdx=idx2;
    }

That takes care if the sorting, now to code up the routine that makes actual *evolution* happen, so far all we've been doing is randomising everything, now we select our stud stock and breed the next generation of AI... it's a nested loop fest, it's:

    function breednewpool()
    {
      local gene breeders[16];
      local int i,j;
      // take the top performers and breed a new generation from them
      // first sort them in order of performance
      sortgenes();
      // keep top fifteen performers
      for(i=0;i<16;i++) breeders[i]=pool[i];

      // breed (crossover) the top sixteen against each other in all perms... twice
      for(i=0;i<16;i++)
        for(j=0;j<16;j+=2)
            crossover(breeders[i],breeders[j],pool[16+j+i*16],pool[j+17+i*16]);
      for(i=0;i<15;i++)
        for(j=0;j<15;j+=2)
            crossover(breeders[i],breeders[j],pool[272+j+i*16],pool[273+j+i*16]);

      // throw in a few mutations  each too
      for(i=1;i<16;i++)
        {
         pool[512+i]=mutate(breeders[i]);
         pool[528+i]=mutate(breeders[i]);
         pool[544+i]=mutate(breeders[i]);
         pool[560+i]=mutate(breeders[i]);
        }
    //  that makes 576 by my reckoning... blank the code of the lowest performers so they
    // get new random code next time
        for(i=576;i<600;i++)
          {
            pool[i].code="";
            initfitstats(pool[i]);
          }

        generations ++;
        saveconfig();
    }

... to be continued ...

Foxpaw: I didn't see the crossover function listed, I'm curious as to how it works on that tree. Have you written it yet?

Zedsquared: Yep, it's back a page on Adventures in GP Episode II I hope to be getting back in the saddle with this stuff soon, watch this space

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

Mapping Topics

Mapping Lessons

UnrealEd Interface

Questions&Answers

Scripting Topics

Scripting Lessons

Making Mods

Class Tree

Questions&Answers

Modeling Topics

Questions&Answers

Log In