Evolution

With our requirements stated, our language defined and our interpreter built, we are ready to start the evolutionary process.

In the beginning, we create a population of random programs, and by random I mean truly random. Trees are initially built by creating a root node and then randomly attaching child nodes to it, until - randomly - a terminal node is selected, at which point the branch terminates. As you would expect, these random programs aren't particularly good at anything, and early generations fail miserably at finding their goal.

Programs that actually are good at finding the goal are found by combining the best programs in the population to create child programs. The idea is that children may inherit the best parts of their parents, and thus later generations become more fit than previous generations. To do this, new generations are constructed using reproduction, crossover and mutation.

Reproduction is simply a means of ensuring that the most fit member(s) of the previous generation survive into the next. When constructing the new generation, we simply copy over one or two of the lowest scoring programs and allow them to continue to compete.

Crossover is the operation that actually takes its inspiration from biology. In crossover, we create new programs by combining parts of two programs to create two new programs. Hampton does this by swapping random subtrees of the two lowest scoring (i.e. most-fit) programs. By doing this, we are hoping that two programs which each perform well in unique circumstances can combine to form a child program that performs well in both.

Mutation, the final operator, helps to prevent our population from falling into a rut. Mutation is done by selecting a random node in the program tree, deleting it (and its subtree) and replacing it with the root node of a new random tree. This effectively introduces new genes into the pool. This is most important if we are running steady-state, which means that in each generation programs not affected by the genetic operators remain in the population. If we are not running steady-state, then the population is repopulated with random programs on each generation, flushing the population with new genes and making mutation less important.

All of these operations occur with a certain probability, which should be adjusted until good results are found. High probability of crossover, low probability of mutation and near-certain reproduction seem to be the most effective in a non-steady-state system.

Adaptation

A final consideration is adaptation. As the project has been described, we have set up a system which will evolve programs that are well suited to a particular map, when in fact we probably want programs that will perform well no matter what map we throw at them. One way to do this is to cycle the map at regular intervals, causing programs that are too specific to fail on the map change, and be dropped out of the population. Over time, we should end up with programs that perform well from one map to the next - programs that survive drastic changes in the environment, just as successful species do in the animal kingdom.

One thing to keep in mind is that the process of adaptation is probably the one that will be the most time consuming. In a system where natural selection is determining which genes in a population survive into the next generation, evolving a population that performs well against a static challenge can occur fairly rapidly. Evolving anything that can not only survive the current environment, but is ready for possibly cataclysmic changes, will demand much more time in the process.

To allow for highly adaptable programs, Hampton can generate random maps and cycle them every few generations.

Results

We've been told that evolution is an extremely slow process, with small changes occurring over hundreds of thousands of generations, but new science seems to indicate that these changes can occur much faster than we previously thought. So it might not come as much of a surprise that Hampton finds successful solution programs fairly quickly, even on very complex maps. Most-fit programs can reach their goal in as few as a hundred generations. This is stunning when you consider the minimum of information and ability we are giving our programs access to, and that our initial programs (as well as programs generated on repopulation) are completely random, nonsense jumbles of function and terminal nodes.

The real measure of success, however, is aesthetic. Our evolved programs are successful if you yourself see intelligence in their strategies. If so, then we have taken a step forward towards creating more realistic AI, and a less frustrating experience for the gamer.

Final Thoughts

If you plan to extend Hampton or create your own genetic programming experiments, there are a few other subjects that might be interesting to consider.

First, you might want to consider program size, and the impact large programs will have on the success of your project. By some miracle, Hampton tends not to create huge, deep trees, although there is no mechanism in place to prevent it from doing so. On the positive side, a larger program tree will have the potential to be much more complex than a shorter tree - a tree which is 100 nodes deep will naturally be capable of much more advanced decision making than a tree which is 5 nodes deep. On the other hand, however, large trees will take longer to parse, will consume more memory, and may use up all their complexity making horrible decisions. Whether or not some sort of pruning process would be beneficial or not would make an interesting study.

Another question we could ask is whether or not we should "correct" a program that is inefficient or redundant. Although a lot of genetic programming projects tend to stick rigidly to the biological model, I see no reason why a little creative hacking couldn't be applied to help the process along. It is possible that reducing redundancy and general stupidity in programs in the population before performing cross-over could result in much more rapid evolution and much more useful programs in the end. If further justification for messing with the basic idea of GP is required, we could consider whether the genotype (i.e. the makeup of the program) or the phenotype (what the program ultimately does) is more important to us.

I tend to think of ideas like genetic programming as jumping off points rather than sets of rigid rules which must be followed closely. Perhaps a combination of genetic programming, other techniques, and pure creativity can lead to a pathfinding algorithm that truly evokes awe in anyone who witnesses it. At the very least, we can hope for an algorithm which won't cause gamers to bang their heads into their desks.