If you have comments or suggestions, email me at dbhillis@erols.com
Hits
Welcome to the Red Queen's race (RedRace for short)
where warriors must evolve as fast as they can just to stay in place. This
page holds the source code for a version of my program for evolving core
wars programs. It also has a windows executable intended to make it easy
for people to join in a distributed project.
RedRace is a program that uses a genetic algorithm
(GA) to evolve core wars programs, called
warriors, written in the Redcode language. A population of warriors
competes in a game of king of the hill (KOTH) modeled after the ones at
the KotH site where the fitness of a warrior (and hence it's chances of
survival and of reproduction) is based on its score against the warriors
currently on the hill. The fittest warrior of each generation is allowed
to challenge the hill and attempt to dislodge the weakest warrior and replace
it on the hill. The name is a reference to the race of the Red Queen in
"Through the Looking Glass" by Lewis Carroll.
source code
parameter file
Windows executable
Go to http://www.cs.helsinki.fi/~jpihlaja/exhaust/exhaust.html to find out more about exhaust.
RedRace is a C language program. I developed it by taking
the program ga_war.c, written by Jason Boer and gradually replacing
it. I think of ga_war.c as an ancestral form.
RedRace starts by randomly forming a population
of individuals, each of which is a redcode warrior. The program then generates
enough warriors to populate the hill (maximum of 50 warriors on the hill).
Every generation, every warrior in the population competes (using the “exhaust”
simulator) against each warrior on the hill and receives a fitness based
on its composite score. The fittest warrior challenges the hill (it almost
always gets on) and is immortalized - a copy is placed in Valhalla. Next
the population gets scored against the changed hill and on and on it goes.
The fittest warrior in the population will generally
be exterminated within several generations because new warriors will have
evolved specifically to defeat it and then made it onto the hill themselves.
But warriors sent to Valhalla have a chance at resurrection each generation.
A resurrected warrior may be able to thrive and reproduce again at some
later time. Or conditions may never be hospitable enough for it to survive
again.
Optionally, the fittest warrior also battles an
N
warrior benchmark and this score is recorded. (Warriors in the benchmark
must be named "b1_1.red",...,"b1_N.red" and be in a format that
RedRace can read. I usually use the Wilkies benchmark.) The GA's fitness
function is based on a hill whose members are constantly changing. Tracking
the Wilkies score of the fittest member of each population gives an objective,
(though of course, imperfect) measure of the progress (or lack of it) that
the population is making.
But watching the program run and waiting
for a high Wilkies score would be very slow and disappointing. It's much
more fun to follow the dynamics of what kind of warriors are getting onto
the hill and how the warriors are changing over the generations. Depending
on the settings, the file "temp.red" will hold a copy of the warrior that
the program is testing at the moment. By opening another window from time
to time and repeatedly running PMARS in graphical display mode with temp.red
vs. a "SPL #0, #0" you can see when a new kind of warrior emerges.
On my own system, I have this set up as a kind of screen saver.
Generally you'll see a bunch of core clears
take over in the first few generations. Eventually, you should get something
interesting: maybe replicators, maybe imp launchers, maybe scanners, ...
. It may take a few days. You'll need patience, but you'll also need to
decide when to pull the plug on a boring run and start over.
The Tiny hill serves as the central hub of a distributed GA. Evolving warriors can migrate from computer to computer and even from evolver program to evolver program. But they need computers to run in and they need humans to serve as vectors of transmission by running the programs and submitting the warriors to the hill. Join now. BE A VECTOR!
This warrior was recently on top of the Tiny hill.
;redcode-x verbose
;assert CORESIZE == 800
;name RedRace v1_163
;author Dave Hillis <dbhillis@erols.com>
;strat - Created using RedRace.c.
;strat - An evolving population playing KOTH.
;strat - Configured for the Tiny hill.
mov.i > 268, } -1
spl.i # -75, } -209
mov.i } -3, }
1
spl.i > 299, { 211
mov.i } -5, } -1
mov.i $ -5, } -375
mov.i { -279, { -6
mov.i # -215, } 59
mov.i # -215, } 3
spl.b # 19, < 275
mov.i * 55, } -4
mov.i } 136, } -3
mov.i # 358, } -2
mov.i > 260, } -4
mov.i } 397, } -4
mov.i > 361, } -5
mov.i } 268, } -5
seq.i } 267, > -8
mov.i > 358, < 371
end 0
Warrior for a standard size core - imps
;redcode-b verbose
;assert CORESIZE == 8000
;name redrace_6_08_00
;author Dave Hillis
;strat - Created using RedRace.c.
;strat - An evolving population
playing KOTH.
;wilkies = 128
;wilmoo = 102
spl.ba # -3737, @ 8
spl.i # 3823, { -2469
add.i # -3748, @ 1
mov.i # -2082, } 1
spl.i $ -4, * 1
jmp.x * -1, < -5
end 4
Paper for a standard sized core
;redcode-94
;assert CORESIZE == 8000
;name red_race/chl_382.red
;wrapped around once
;wilkies = 95
org S;
S;
mov.a } -499, > 8262
seq.i < -2781, > 11909
cmp.i @ 546, < 3885
sub.i > 10896, { 0
spl.i # 147, * -3
spl.b > 3251, } -1369
mov.i } 1611, < -1137
mov.i < -6, < 1306
spl.i # 2951, } 2
mov.i } -11, } -4
mov.i > 739, { -133
mov.i * -10, } -7
mov.i $ -2, { -4
djn.i > 2319, { 4178
end
I think that techniques for evolving core warriors also apply to many practical problems. I modified redrace to work on a battle planning problem and was pleased with the results. (I guess I should add the conference paper sometime...)
This is the second release of redrace. I'm sure that the program has bugs and that it's unnecessarily confusing. If you send me questions or comments about it, I'll be glad to know it's being looked at and try to help.
If you have comments or suggestions, email me at dbhillis@erols.com
Hits