Species - A Corewars Evolver

by Will 'Varfar', 2003

Introduction
How it works
Where it is going
Todo list New!
Download
Datafiles
Editing Parameters New!
Links to recommended reading

^ results of a recent test-run

Introduction

Species is a corewars evolver. It is a program to generates corewars warriors using genetic algorithms. This is the program which generated the best evolved warrior in the recent Multi-Manics corewars competition. Contemporaries include YACE, RedRace, Red Maker and CCAI.

Species is definitely the most over-engineered, complicated and buggy Corewars Evolver on the freeware market today!

Species was inspired by HiEv's reply at r.g.c. where he outlined the problem of "mules". That whole thread might be worth a read btw. Anyway, Species is a big experiment in whether 'specieisation' would help evolve better warriors.

How it works:

The world is divided into timesteps called generations. Each generation all warriors fight and are scored. These are then selected (favouring those that score well) for breeding and the subsequent generation are generated. Some warriors might survive to fight the next generation

Taxonomic terms are used to describe the world inside Species. These are kingdom, genus, species and chromosome, largest first.

The kingdom has many genera.

Each genus has many species.

Species come in two flavours: evolving species contain chromosomes that are breed each generation (or survive from the previous generation); benchmark species contain fixed warriors that are supplied by whoever runs this program. Benchmark species do not breed.

A chromosome is an individual warrior.

The order that genera are specified in the configuration file is important. A genus fights the species infront and defends against the genus behind. You should have at least three genera. Genera can be visualised as being arranged in a cycle. A genus does not fight itself. Fights won attacking the genus infront are generally weighed heavier than those fights won defending.

It loads the definition of the world from an ini file. Almost all aspects of the program are fully configurable from this ini file.

Some things you can customise (on a by-genus or by-species level) in the ini file:

The probability of various opcodes being tried.
The length of the generated chromosomes.
The distribution of generated operands (e.g. favouring addresses close to the warrior).
The level of mutation and crossover when breeding new chromosomes.
The weighting of wins, ties and loses.
The weight of a battle overall.

Each generation is saved to disk. When run in a directory containing generation files, it can load the last saved generation and continue. This means you don't have to leave your computer switched on for fear of losing your progress.

The full sourcecode is released under the GPL. It uses Exhaust, which is licensed seperately.
It uses C++ and is very object-oriented. You can easily 'plug-in' your own implementations of key things.

The idea of genera being ordered and fighting at most two other is to favour the popular 'paper-scissors-rock' analogy. The idea is that each genus evolves to be the anti-genus of the genus it is fighting.

Benchmark species serve to direct evolution. No actual genetic material is ever borrowed from these benchmark warriors. Because warriors fighting benchmark warriors are still scored, this will incourage evolved warriors to evolve traits that are effective against this type of benchmark warrior. This will in turn indirectly influence the type of warrior in the same genus as the benchmark warrior even though the two never meet in battle. I hope.

Where it is going:

Where is it going? Here is where I want to take it:

Evolving using meta-instruction genes. I hope this will make a major breakthrough in the effectiveness of corewars evolvers.
Distributed processing. Corewars evolvers are an excellent candidate for distributed processing. I envisage nodes coordinating via IRC or Jabber chatrooms. A fuller study of the impact of latency and the bounds of chromosomes/generation and rounds/generation make this feasible. But my curiousity might push this area...
A faster MARS? In truth Exhaust is tried, tested and plenty fast enough. But my curiousity might get the better of me...
Whereever you want to take it! I am always open to suggestions.

Markovs and stats

2003-06-13 Meta-instruction genes didn't really make much difference. However, Barkley Vowk has had some success with evolved papers (hand-massaged as a last-step) being used on hills. And Martin Ankerl (YACE,QMars) has described his mutation rates etc in the wiki. Rumour has it that Martin has prepared an optimised Exhaust that is twice as fast, too!

Barkley says that he uses markovs to suggest instructions when building warriors. And both Martin and Barkley say they only use mutation, not crossover. So I take both these ideas on board and try them out. I also merge a top tip from John Metcalf: the distribution of operands has a very different 'character' for different opcodes. I combine all these ideas, and hey presto! Take a look at the test chart at the top of the page.. (This run is one species evolving only against the standard wilfiz benchmark. Now wilfiz isn't very 94nop-like, so that doesn't mean I am evolving a potential KOTH :-/ But it does prove the techniques in a very measurable way.)

Meta-instruction genes; kluging it

2003-02-17 The CVS contains the beginnings of a kluge at meta-instruction genes. This basically scans a chromosome splitting it up into genes- small adjacent instructions that get executed in sequence. The algorithm categorises three types of gene:

Executable instructions. This is a sequence terminating on a branch instruction. There are two important flags: continues is when execution might flow onto the next instruction; skips is where execution might flow onto the instruction after next (e.g. gene ended on a SEQ)
DAT instructions. A run of one or more DAT instructions; marked as not executable
DAT Padding. A run of one or more DAT default core. This is recognised by the algorithm and not inheritable. However, when creating the child new DAT Padding genes might be added

The mother and father are scanned and the genes identified. The genes are randomly sequenced selecting randomly from mother and father until certain conditions the total length of the resulting chromosome is within bounds and that execution can't 'drop off' the end of gene. The resulting gene then is generated. It is during this writing stage that mutation then can play a part. As genes are reassembled the locations of the JMPs are resolved to other genes (or the same gene causing a loop, if the instruction isn't a JMP, unless there is only one gene). The ini file can specify a "whitespace prob%" that controls the chance of new DAT Padding genes being sequenced.

There are some obvious limitations in this algorithm. It basically doesn't grok the inter-relatedness of operands. An approach that truely understands how redcode instructions work is possible, but it is also very involved. I will tackle it when I have explored this avenue ;-) The hope of this kluge approach is that warriors that look more like human warriors might also score as well as human warriors :-)

Download

You can download "Species" from CVS or pickup the latest nightly CVS tarball. Or you can browse the source online. Here is a Species 1.2d (sourcecode + windows executables, 700KB) for Windows and Linux users and other l33t hackers. You'll need to edit the ini file though and reduce the number of species and the number of chromosomes per species, unless you have a monster machine.

Special note: resume is still pretty experimental. If you get an error / general protection fault / seg fault / something wrong then you can just delete *resume.dat and it will restart from the beginning of the generation

Datafiles

The first time Species is run (in a directory) it searches for species.ini. If this file is present, it is loaded. If Species finds datafiles, it does not examine the species.ini file again - it is not intended that you tweak the parameters while Species is in the middle of an experiment!

Species generates lots of datafiles as the experiment progresses. This table describes what the variously-named files contain:

species.dat This file is a parsed version of the original species.ini. It might be useful to compare this file with your original species.ini file to see if anything wasn't parsed properly

species-gen.dat This file contains the generation# and uid_sequence# for the experiment

species-name-generation#.dat These files store (in a compact internal binary format) the chromosomes of the named species for the specified generation

species-name-resume.dat These files store partial results from the current round. So if a round is interrupted (by Species being stopped), when restarted it can resume from whereever it got to. You should never lose much more than the last few seconds of work
name-generation#.red These files contain the best chromosome for the named species for the specified generation. This file is proper redcode, so can be loaded in pmars

name--uid#.red These files contain all warriors in the top n percent of the named species. The redcode file contains the benchmark score, and the greppable word CANDIDATE if the warrior scored notably well against the benchmark. You have to enable benchmarking to get these files generated

Species assumes the current directory is the best place to put files etc. If you want to have several experiments running, you can separate them by running them in separate directories.

To restart an experiment, you can simply delete species*.dat

Editing Parameters

Species loads an ini file 'species.ini' if it cannot find an underway experiment. You can edit this ini file in any text editor.

Visitool is the beginning of a new GUI for visualising, editing and monitoring Species experiments. It uses wxWindows for cross-platform stuff, so should work on Windows, Linux and virtually every other desktop/server operating system you can mention. Early work-in-progress is available in the zip and in the CVS store, but is very much work-in-progress. It'll be announced on r.g.c. when there is something fairly usuable there. A screenshot of progress is online here, as a taster ;-)

Visitool (to be renamed something like "species-gui", while the main "species" commandline version will be renamed "species-cmdline" or something descriptive) will be a full graphical front-end to live species experiments. It will be able to run an experiment (in it's own thread) and monitor it giving pleasing visual feedback (e.g. who is fighting who, updated live). It will also provide nice graphs of progress and let you visually trace a warrior/gene heritage. And every other neat feature I can think of!

Links to recommended reading

This is an inexhaustive list of sites and books I have read related to this project:

"On Random Numbers and the Performance of Genetic Algorithms" Erick Cantu-Paz
"Swarm Intelligence" - An Interview with Eric Bonabeau
"Virtual Organisms" Mark Ward 0333724828
"The Cambridge Quintet" John L. Casti 0738201383
"Evolution" Carl Zimmer 0099439824
"Distributed Computing Economics" a short article by Jim Gray