Genetic Programming (GP)

GP is an automated programming technique developed by John Koza currently at Stanford University (More about GP) .  In 1994 I designed and built GeneCode a GP on a 68K Mac solving the "The Santa Fe Ant Trail" as described in John Koza's Genetic Programming I text.  The software built in "object" C was a GP success in that the ants could successfully traverse a 2D trail, but a software mistake; an example of disadvantage of object orientation (sub classing) without a compiler support.  My program was never ported to PPC Mac or other system.

I would like to start another project in Java, and have a particular stone based game in mind.  The first step will be to see what is available in Java for GP.  

Link to John Koza's site on genetic programming.


Santa Fe Trail

 The Santa Fe Trail is a simple problem where you attempt to train the computer through GP to simulate an ant foraging along a broken trail of sugar.  
The following is output from my GeneCode program.  The search for (or evolution of) a program was different every run because I would alter the size of the pool of individuals and because GP uses a randomized starting set.  Each run is different, and no run is guaranteed to score very well.  None of these runs exhibit perfect fitness, however multiple runs exhibit various approaches as you may expected in a living system.  Specifically, both close and narrow tracking, wide tracking, and more chaotic traversing were exhibited.

Color Key: Green indicates a space where the ant traveled to without finding food, blue a score - food that the ant found, and black food that was not discovered.  The ant always beginsin the upper left hand corner.  The graph in the bottom left is a the fitness measure of both the best and average of all ants in green and the best individual of a generation in red across the horizontal axis the generation number.  For these runs the individual pool was between 500 and 2000 individuals.

This run took the wide but non chaotic approach, but it cannot pass a gap in the trail of 4 down.
Wider Tracking Approach

This run depicts a frequent strategy, a very careful ant.  Probably this ant looks in every direction before moving and only travels in the direction that last scored it some food.  This approach works flawlessly until the end of the maze where it needs to circle around the last found food in widening circles to get the last two morsels.  With this program I have no way (outside of a debugger) of reading the "instructions" generated, but strongly suspect that it commonly follows well because it invariably travels left at the last food pixel.  The poor ant needs some more state information in its instruction set!
narrow approach
More chaotic approaches tended to be succeeded by a "good tracking" programs. Here's one that scores over 1/3 and has lasted to the 39th generation.
More random approach