Professional PHP

PHP Programming, Web Development, PHP Advocacy and PHP Best Practices.
« Friendster wrapup: does MySQL scale
Commercial Zend versus Open Source PHP »

Happy 20th B-day Corewars

July 15th, 2004

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.

Filed Under

  • Misc

Related Posts

  • Sarah Snow Stever
  • php|architect Test Pattern
  • Looking forward to 2007
You can leave a response, or trackback from your own site.

4 Responses to “Happy 20th B-day Corewars”

  1. David Moore says:
    7/16/2004 at 4:36 pm

    Don’t waste your time on Core War. You can do better.

  2. Harry Fuecks says:
    8/13/2004 at 12:50 am

    From this blog – a clever idea from IBM, on the same tack, to get people to learn Java;

    RoboCode – programmable (with Java) robots that beat each other up (articles here and here)

    Code Ruler – a spin on “Warcraft” where you program the kingdoms ruler

  3. Barkley Vowk says:
    9/23/2004 at 10:54 am

    Bah. Don’t listen to David. Corewar Evolution can use all the help it can get, you might want to peek at http://www.evil-empire.info/files/ccai-1.0.tgz It is a distributed system for evolving corewars programs, I’ve got a better version I’m almost ready to turn loose (with a warrior I hope will do well on 94nop).

  4. John Metcalf says:
    9/28/2004 at 9:50 am

    Players continue to waste their time on Corewar just as other players waste their time on Quake, CounterStrike or what-ever happens to be the hot game of the moment. Clearly there must be something to hold their attention? Some impressive advances have been made in evolution frameworks over the last few years… In some environments the machine written warriors are giving us humans a tough time :-)

Leave a Reply

Click here to cancel reply.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

code: use [code=php][/code].

Comment Preview

    Subscribe Feed
    Share Subscribe to this blog…
    Share Bookmark or share this page…
  • About

    My name is Jeff Moore. I'm a PHP programmer living in San Francico and working for a startup.

    More about me…

  • Categories (Home)

    • Agile Methods (14)
    • Mac (14)
    • Misc (17)
    • Open Source (14)
    • PHP (98)
    • Software Design (29)
    • Usability (14)
    • Web Design (20)
  • Recent Comments

    • Programming Language Trends via Google  19
      Craigslist pva, jessica, Scott [...]
    • Looking Towards the Cloud  35
      bentonville multiple listing, cosmetic dental, Sam Brodish [...]
    • PHP versus ASP  8
      Marhta Blight, Ravi, Ryan Brooks [...]
    • How to Transfer Mac OS X Application Data between Computers  59
      Website Migration, harry the computer support guy, Dotty Salvage [...]
    • Working with PHP 5 in Mac OS X 10.5 (Leopard)  157
      lehuuphuc, Robert Parthemer, Lingerie Intimate [...]
    • PHP Games  25
      jessica, Tennille Cranor at Chilli Plants, Lucas Ortell [...]
    • un-PEAR-ing  5
      jessica, Eugene Panin, Arnaud [...]
    • The Legality of Republishing RSS Feeds  23
      kevinxiao, Marissa Miscovich, Quick Student Loans [...]
    • Faster Page Loading  4
      jessica, angular cheilitis, Aaron Rosenfeld [...]
    • PDO versus MDB2  15
      jessica, kevinxiao, Gavin [...]
  • Recent Posts

    • ZendCon: Writing Maintainable PHP Code
    • Looking Towards the Cloud
    • Holiday Tech Support
    • Closures are coming to PHP
    • php | tek Wrapup
    • php | tek 2008
    • Sarah Snow Stever
    • Benchmarking PHP’s Magic Methods
    • The Endpoints of the Scale of Stupidity on Video
    • Working with PHP 5 in Mac OS X 10.5 (Leopard)
  • Site

    • Archives
    • Log in
  • Search