ZedSquared?/Developer Journal

March 25 2003. Nothing to see here, move along please people

Well I finally got a devjournal page up, expect to see much rambling and thinking aloud as I work over some of the knottier bumps in that steep slipperly slope that is the Uscript learning curve. (expect also much outrageous metaphorism and neologistic shennanigins as I warp the english language in a carefree manner :rolleyes: )

Actually, expect to see patchy updates as work, leisure, and Significant Other vie for my time.

Adventures in Genetic programming

Right, having lowered your expectations to a comfortable level, I'll reveal a tantalising glimpse into my current activities (like you care anyway ) I'm currently coding for [UTRon] the tron mod and am looking into the AI for the lightcycle game ATM, I remembered stumbling upon [This Site] a while back where you can play (ordinary, boring, top down, 2D) lightcycles against opponnents that are controlled using [Genetic Programming] techniques... go there now and give those bots some more training... go on! there's a high score table and everything

The more I read about it the more it seemed like a cool thing to try out... evolve an AI by randomly generating loads of controlling programs and playing them off against each other and humans, the best performing ones get creamed off the top and allowed to 'interbreed' with a little mutation thrown in for good measure thus producing a new generation to be tested and so on until eventually (maybe) AI is evolved that plays a decent game.

Now it strikes me that UT could be quite a good environment for this sort of thing, the large number of trials needed to evolve from 'random nonsense' to 'random seeming nonsense that somehow just *works*' can be carried out on many pcs in parrallel all talking to a central server that keeps track of the gene pool (think SETI@Home with a moebius twist). Uscript already has some TCP link classes that I need to get to grips with anyway so what the hell.. let's go!

Rewind a fortnight or two... I'm sitting on my own in a hotel in Milton Keynes (work... don't ask!) with a laptop loaded up with UT, WOTGreal and winCVS, fired by the inspirational knowlege that Bletchly Park (where this whole computing thing was kick started by Alan Turing waaay back when) is only a few miles down the road I decide that the time has come to turn this whim into a reality, I start to scribble, realise I have no pen, borrow one from reception and *really* start to scribble, strange blobby tree diagrams cover the paper, occasionally the distinctive crack of lightly chewed Bic casing is heard, all falls quiet for a second, my hands hover over the keyboard for a contemplative second or so and kapow! An edifice of code starts to take shape, it's turning as recursive as a very recursive thing (but that's OK), seems nicely modular, and might, just might... actually work! I missed out on the best thing about hotel life ( huge breakfast! ) next morning due to oversleeping a little

Fast forward to the present and that core has been expanded upon and is approaching something workable... having a full on breeding program is close, just got the tcpip stuff to work on really.

Here's some code and stuff to be lightly refactored into a tutorial later with any luck:

First off, go look at the animated tutorial at [www.genetic-programming.com/gpanimatedtutorial.html] or all of this is all going to be nonsense

OK, by now you should know that GP uses a tree structure of linked objects to do its 'thinking' these objects are either 'Terminals' (i.e. 'leaves' at the end of the tree branches which return either sensor input or constant values) or 'Functions' which take one or more values and return another.

In my implimentation all nodes take and return floats as arguments so it doesn't matter how much you mix things up, no node gets presented with data it can't cope with.

Here's a simple node that adds together its two inputs:

//-----------------------------------------------------------
// arithmetic addition function
//-----------------------------------------------------------
class GPFplus extends GPnode;


function float evaluate()
{
  return( children[0].evaluate() + children[1].evaluate());
}

function string makemytoken()
{
  return("+");
}


DefaultProperties
{
 childcount=2
}

It extends GPnode which is the base class of all the nodes and includes lots of baggage to be explained later, for now just notice that the nodes below it in the parse tree are referenced by the children[] array and that the evaluate method is called on these children in order to get the values that need to be added together. This is the basic magic, all the objects in the tree are linked together and control flows down the branches until something that actually returns a value is evaluated. Some nodes are conditional and branches get evaluated or not depending on conditions... in this way we can produce a program that actually varies its behavior according to conditions, unlike any of the simple examples in the tutorial linked to above which are more like equations than anything we'd call 'code'.

As an example here's evaluate for the 'less than' node:

function float evaluate()
{
  local float arg1,arg2;
  arg1=children[0].evaluate();
  arg2=children[1].evaluate();
  if(arg1<arg2) return(children[2].evaluate());
  else
    return(children[3].evaluate());
}

Notice how sometimes children[2] gets evaluated and other times it's children[3] that gets to see some action.

Now in order to get any of this to work we need a way of storing the tree so it can be passed around and manipulated, this is where makemytoken() comes in, its job is to return the string representation of that node... pretty simple here but nodes which hold values need something more... here's evaluate and makemytoken for the 'constant' terminal node:

var float val;

function float evaluate()
{
    return(val);
}

function string makemytoken()
{
  return("K"$val);
}

As you can see I use the character K to flag a constant and then append the value to is using uscripts really rather useful built in type conversions.

Enough specifics, I hope that conveys the gist, here's the core GPnode code in it's glory:

//-----------------------------------------------------------
// Genetic Programming parse tree node root class
//-----------------------------------------------------------
class GPnode extends Actor;


Var int Childcount;
var GPnode children[4], parent;
var int childnum, depth; // self = parent.chilren[childnum]
var string mytoken;
var actor mypawn;            // might not be always be a pawn, hence type = actor for now
var const string terminators, functions;
var const string alltypes;


function float evaluate()
{
  return(children[0].evaluate());
}

Variables and a very empty evaluate method.

Now more recursion: this is how the tree gets written out as a string: the node writes it's own token to the string then calls writetostring on its children, those children in turn get their children to write a token to the string and so on... somehow satisfyingly cool to someone like myself who's never been beyond a simple recursive factiorial function before

function WriteToString( out string genome )
{
 local int i;
 genome = genome$MakeMyToken();
 if(childcount == 0) return;
 else
  {
    for(i=0;i<childcount;i++)
     {
       children[i].WriteToString(genome);
     }
  }
}

function string makemytoken()
{
//log("makemytoken called on "$self);
// null token for base class, make this return the string that represents
// any subclass (mostly one char but constant terminators need to write out
// their value forinstance)
return("");
}

Notice also cunning use of an 'out' declaration there so all that needs to be done to create the genome string is simply call WriteToString(s) on the root node of the tree and as if by magic, S gets an encoded version of the object tree written to it.. by now I'm really starting to grock recursion properly and feel like I'm on a run, the elegence of these objects all describing themselves is appealing but in the background I can't help wondering if it all might fall apart somehow...

Doubts or not, this is how most of the functionality has shaped up, simply call a method on the root node and all else follows for various tree manipulation tasks.

Now having written this string we neeed a way of reading it back in and creating an object tree out of it... so let's go all recursive again and we have the imaginatively named:

Function ReadFromString( out string genome)
{
  local int i;
  local string char;
  local GPnode node;
  for ( i =0; i<childcount;i++)
  {
    // eat and analyse first (leftmost) char of string
    
    char = left(genome,1);
    genome = right(genome,len(genome)-1);
    node = addchild( char,i);
    node.ReadFromString(genome);
 }
}

So basically you start by spawning a gpnode as the root, feed it the string of gobbledegook generated by writetostring and it reads (and discards) the first character, spawns the appropriate node actor, makes that its first child and passes the rest of the string to it so it can make any children it might need in turn... and so it goes on down the tree.

Addchild is a big switch that takes care of spawning the right sort of node type according to the character token that has been read in:

function gpnode addchild(string childtype, int i)
{
  local class<actor>  childclass;
  local gpnode node;

   switch(childtype)
   {
    // functions first
      case "+":
          childclass = class'GPFplus';
          break;
      case "-":
          childclass = class'GPFminus';
          break;
      case "*":
          childclass = class'GPFmultiply';
          break;
      case "%":
          childclass = class'GPFsafeDivide';
          break;
      case "<":
          childclass = class'GPFlessThan';
          break;
      case "Q":
          childclass = class'GPFSqrt';
          break;
      case "N":
          childclass = class'GPFMin';
          break;
      case "X":
          childclass = class'GPFMax';
          break;
      // then the terminators
      case "R":
          childclass = class'GPFrightTurn';
          break;
      case "L":
          childclass = class'GPFleftTurn';
          break;
      case "K":
          childclass = class'GPTconstant';
          break;
      case "A":
          childclass = class'GPTlookAhead';
          break;
      case "B":
          childclass = class'GPTlookAheadRight';
          break;
      case "C":
          childclass = class'GPTlookRight';
          break;
      case "D":
          childclass = class'GPTlookBackRight';
          break;
      case "E":
          childclass = class'GPTlookBack';
          break;
      case "F":
          childclass = class'GPTlookBackLeft';
          break;
      case "G":
          childclass = class'GPTlookLeft';
          break;
      case "H":
          childclass = class'GPTlookAheadLeft';
          break;
      default:
          log( " *gennode* Uh Oh! unknown token! "$childtype);
          break;
    }
   // log(" childclass = "$childclass);
    node = gpnode( spawn(childclass));
    children[i]=node;
    node.mypawn = mypawn;
    node.parent=self;
    node.childnum=i;
    node.depth=depth+1;
    return(node);
}

... and the sands of time draw a close to the first session editing this page... things are already a lot clearer in my head thanks to explaining a little to you, dear reader... till the next time I leave you with the remainder of the gpnode class which deals with things like growing random sub trees and other housekeeping. You can view the rest of the classes so far on CVS at the home of UTron on sourcefore here: [14] click on 'browse CVS' and look for classes in the package 'UTron' with names beginning with GP.

function RandomGrow ( int depth, int maxdepth )
{
local int i,j,r;
local string char;
local GPnode node;
  //log(" random grow called on "$self@"depth = "$depth);
  for ( i =0; i<childcount;i++)
  {
   //log(" randomgrow on "$self$"choosing child"$i);
    if(depth == maxdepth) {
     // log("max depth reached");
      char = mid(terminators,rand(len(terminators)),1);
  //    log("char = "$char);
      node = addchild(char,i);
    //  log("new terminator node = "$node);
    }
    else
      {
       if(depth <4) char = mid(functions,rand(len(functions)),1); // add a bit of depth to start with for testing
        else char = mid(alltypes,rand(len(alltypes)),1);
      // log("char = "$char);
       node = addchild( char,i);
      // log("new node = "$node);
       if(node.Childcount >0)  node.RandomGrow(depth+1,maxdepth);
      }
  }

}

RandomGrow is the function that creates random trees for seeding the initial population and for use in the genetic 'mutation' operation too. Note the plentiful commented out log statments... no more than curious fossils now, they were useful in the extreme when debugging this stuff, a comment after every line is usually a sign that I was tracking down an accessed none... I really should get round to deleting them

Since there are currently quite a few more terminal nodes defined that there are functions the tree had a habit of being very small most of the time so you'll notice that I make sure that all nodes up to depth 4 are chosen from the set of functions in order to give it a bit of depth... strictly speaking this is biasing what should be a totally random process, the fitness selection and evolution should take care of any runts, so this will probably go once things are fully set up. For now though it's a handy feature for testing.

Sometimes we might need to prune off the branch of a tree before replacing it with something else (like a branch chosen randomly from a tree that performs well at our chosen task, or just another random growth when mutating ) so the prune function recursively destroys nodes below the one on which it is first called.

It still feels a little crufty, that first check on childcount should be redundant really as the parent of any nodes with childcount == 0 will destroy them so that will go soon methinks. In fact a more elegant system would have terminal nodes destroy themselves but at the time I wasn't confident that a function in a node that called that nodes destroy() function would actually return, so nodes destroy their children instead (after having called prune on child nodes to ensure that their children get destroyed in turn ).

function prune()    // remove objects below this node
{
  local int i;
  if(childcount == 0 ) return;
  else
    for(i=0;i<childcount;i++)
      if(children[i].Childcount==0) children[i].Destroy();
        else
           {
             children[i].prune();
             children[i].Destroy();
             children[i]=none;
           }
  return;
}

All of the tree manipulation functions used in creating new trees from an exisiting one need to chose a node at random and then do stuff to it. So the two functions below are used to:

Count the nodes in the tree so that correct range can be used when a random number is generated to pick a node.
Actually return a reference to that random node

function countnodes(out int nodecount)
{
 local int i;
 //recursively count nodes in tree below this one
 nodecount ++;
 for (i=0;i<childcount;i++)  children[i].countnodes(nodecount);
 return;
}

function gpnode findnode(out int nodenum) 
{
  local int i;
  local gpnode result;
  nodenum --;
  if(nodenum ==0) return(self);
  else
    {
       for (i=0;i<childcount;i++)
         {
           result = children[i].findnode(nodenum);
           if(result != none)
              return(result);
         }
       return(none);
    }
}

last but not least, cloneme() spawns a duplicate of a node and all the tree below it... yet more recursive majick

function gpnode cloneme()
{
  // clone this object, used recursively to duplicate subtrees
  local int i;
  local gpnode newnode;

  newnode = spawn(class);
  for(i=0;i<childcount;i++)
    newnode.children[i] = children[i].cloneme();
    newnode.mypawn=mypawn;
  return(newnode);
}

The most interesting things in the deafult properties are the strings which are used to hold lists of the tokens of the different types of nodes. Add to these when new nodes are made (my current one character per token scheme is nice and simple and I reckon if you find yourself running out of characters as node types undergo runaway expansion you need to think again about how much control you're willing to hand over to the evolution process... stick to minimal building blocks and let complexity sort itself out... another lesson from mr Turing )

DefaultProperties
{
DrawType=DT_none
bCollideWorld=false
bCollideActors=false
bProjtarget=false
childcount=1
Terminators="RLKABCDEFGH"
AllTypes="+-*%<RLKABCDEFGHQNX"
functions="+-*%<QNX"
}

So there you have it, the core node class. But for this to do any good we need a way of storing 'genes' and keeping track of which ones are doing well at our trials, as well as performing the actual 'breeding' and mutation of those high performers. Find the class that does this and further ramblings over at:

Adventures in GP episode II

Your Comments Welcome

DJPaul: Blimey.

Zedsquared heh! I'll take that as a good 'Blimey' then food for thought I hope?

Chazums: Strangely enough, just stumbled onto the idea of using this kind of thing for AI today. Nicely written walk through, makes things clearer in my mind too.

Zedsquared Cheers Chazums, glad my explanations make some sense to you, here's a good link to a page full of such goodies (the whole site is good for AI too) [GameAi.com]

Category Journal