Professional PHP

I ran across this blog entry wishing Core Wars a happy 20th Birthday. Its hard to believe that it has been 20 years. I was fascinated by the Scientific American articles when they came out.

Around the time it came out, I was interested in artificial life and evolution. I used to write colorful simulations of digital microbes drifting in simulated currents and eating each other. There was more artificial than life in my programs. At the time, Core War seemed to promise a way to make an ecosystem out of these toy programs.

I always had more interest in evolving core war programs, than in writing them, although doing so was beyond me in 1984. This is unlike my brother, David Moore, who is an accomplished writer of core war programs, and whos stasis warrior is the oldest surviving warrior on the hill.

A few years ago, one of my science teacher friends asked me to mentor a couple of high school kids in a science fair project using computers. I put together a proposal, but the scope was too large for them. I’ll put the proposal here for google food:

Project goal

Develop a genetic programming system that is capable of producing programs that can play the game Corewar at a level competitive with human players.

Previous attempts

Previous attempts to evolve corewar programs have not met with a great deal of success. This is due to the large search space of potential corewar programs and the tendency of previous attempts to fall into local maxima. This project will attempt to address both areas.

Addressing the problem of local maxima

Hypothesis 1: Evolution in a homogenous environment is likely to produce solutions that converge around a local maxima.

There may exist other solutions that are better suited to the environment, but they cannot be reached because the penalty incurred by straying from the local maxima is too great. Human written corewar programs are expected to perform well in a wide variety of environments. To evolve human competitive programs, a heterogeneous environment must be created. In a genetic programming situation, the environment is represented by the fitness function. Previous attempts to evolve corewar programs have evaluated the fitness of proposed solutions using a single fitness function. This project will attempt to use multiple fitness functions to determine survival, thus encouraging diversity in the genetic population.

Hypothesis 2: An evolutionary environment that relies on direct genetic manipulation of the proposed solutions is likely to produce solutions that converge around a local maxima.

Most direct genetic mutations result in rendering the proposed solution unviable. This is especially true in corewar, where there is a very large built in penalty for having programs with extraneous instructions or instructions that perform a harmful action. Previous attempts at evolving corewar programs have relied on the direct low level manipulation of the proposed solution. This project will attempt to introduce an intermediate representation that allows for the existence of interons which can hold inactive genetic material in a way that does not penalize proposed solutions while potential leaps from a local maxima are evolving.

Addressing the problem of search space size

Better representations
Not all possible corewar programs are viable. This project will attempt to choose intermediate representations of corewar programs that have a greater probability of being viable solutions. This will change the shape of the search space. Searchiing will tend to be directed away from certain possible solutions because of the nature of the intermediate representations and the genetic manipulation operations. Note that in addition to eliminating many bad solutions, this approach may also introduce new local maxima that prevent some possible good solutions from being discovered.

Parallel processing
Large search spaces can be overcome by the use of more computer resources. This project will use networked computers to increase the number of potential solutions that can be considered at one time.

I got the idea for an intermediate representation from my 9th grade geometry book. There was a one page sidebar on Doug Lenat’s AM program. Based on that little sidebar, I wrote a little toy program for generating geometry proofs which seemed to impress my teacher at the time. Later, when I was studying comp-sci at Michigan State, I looked up Doug Lenat’s literature and criticism of it. The idea that the representation of the problem could narrow the search space stuck with me.

Perhaps some day I will return to this problem.