LCE8 is a small warrior evolver written in QBasic with the following
features...
It does not have crossover or starting location mutation, and
doesn't have a user interface other than editing an INI, printing
battle results and exiting if a key is pressed. LCE8 warriors are very
simple, just an assert line followed by redcode. The INI file format is
crude, raw data values are placed on
specific lines.
Here's the "LCE8qb.bas" file...
n=256:l=20:ra=0:spl=0:cs=8000:pmars$="pmars -s 8000 -p 8000 -c 80000 -l 100 -d 100 -b -r 20" |
Here's the "LCE8.ini" file...
256 |
Here's the "LCE8.txt" file with usage notes...
Notes for the Little Corewar Evolver version 0.8... |
LCE8 is the latest iteration of a series of small evolvers written
to explore various techniques without the distraction and bloat of a
big evolver, where changing one little thing potentially affects code
on multiple pages. Originally the goal was (and still is) to see how
small a functional corewar evolver could be, but once it began
functioning rather well it became a serious tool for trying out new
ideas. Although the code is highly compacted, I learned to program on
the ZX81, Coco, C64 and 8-bit Atari (and a Wang mainframe) and back
then this sort of code was the norm, not the exception, doesn't bother
me and it's rather fun reducing complex IF/THEN logic to linear
mathematical expressions - in BASIC when computed (a < b) or (c$ =
"string") returns -1 if true or 0 if false. When applied to a
relatively small program such as this one, I found it easier to write
and debug code when the entire program can be seen at once without
paging back and forth to check variable names, side effects etc.
If you actually want to run LCE8, it should be compatible with most
Windows and x86 Linux systems but heed the notes about running
from a ram disk and using 100% CPU. This is a fairly file-intensive
program that runs fine on a proper setup but can cause issues for some
consumer-grade "high-performance" PC's and laptops that aren't actually
capable of sustaining the advertised speed (shocking but quite common
these days). Setting up a ram disk is quite easy for WinXP and Linux -
for the former look for "A R ram disk", for the latter the ability is
built-in, just have to write scripts to enable it - see the RedMixer
docs for solutions I've use.
I had trouble copying text from this page using Internet Explorer so
here's a zip version of LCE containing the above
files, plus the FreeBasic
version of the source and a readme.txt containing the psuedocode. To
compile for
Linux requires a patched
libfb.a library, and requires a Linux version of pMARS such as the
one of the binaries included in this archive.
LCE can be run interpreted in QBasic under versions of Windows that
support dos such as XP and 95/98, or compiled using the Windows version
of FreeBasic (it's not necessary to install all the extra libraries to
compile plain console programs like this). I use the SDL version
of pMARS on my XP systems.
A bit of history... the first 3 versions were variations of a
concept where a number of warriors fought at once - that concept didn't
work so well. Version 4 implemented a "fuzzy ring" topology where
battling warriors were selected to be more or less near each other in
the soup, wrapping on the ends to form a ring, and also had an INI file
for changing the settings without editing code. Version 5 added
sanity-checking to the INI, fixed bugs, and added an option to generate
instructions without modifiers (88-style). Version 6 added a mutation
option to randomly increment or decrement existing values, as a
separate mutation chance rather than a proportion as in some of my
other evolving programs. Version 7 adds support for battling
neighboring warriors on a grid, or using the fuzzy ring topology.
Version 8 adds code for 88-standard rules provided the instruction and
mode strings are correctly specified. That was tricky! Added 4 lines to
the program, and over 25 lines to the psuedocode listing.
LCE8 is a pure evolver - it creates code from random beginnings with
nothing to guide the process except for the warriors in the soup
battling each other and replacing the losers with mutated copies of the
winners. The closest it comes to incorporating hand-specified code is
an optional hint mode that starts the initial warriors with an SPL
instruction. It supports string weighting by specifying duplicates,
which can influence the type of code produced, but order is not
specified, and combinations are specified only as needed to produce
88-compatible code when set for that. There is an option to insert
duplicate lines but it doesn't say what or when, the dup chance helps
build SPL and MOV blocks for larger warriors and is often found in
other evolvers. LCE8 isn't quite as strong as RedMixer but it's roughly
on par with REBS, Fizzle, RedMaker, and readily generates papers for
coresize 8000, even using '88 rules. They're not that strong but it's
all relative, coresize 8000 is quite difficult
to
evolve for without invoking "special" methods. My evolvers are more
focused on discovering and applying GA methods for evolving warriors
for corewar, absolute strength is nice but isn't the primary goal. For
more competitive results from this evolver set it for a smaller
coresize (such as nano) but often warriors that do well on the SAL Nano
hill are "mad bombers", exciting when they place near the top of the
hill but kind of boring to study. If expecting warriors that can
compete with hand-coded warriors for coresize 8000 then look elsewhere
- this one would be doing well to exceed 100 Wilkies.
How the LCE8 program works
Like most of my evolvers, the basic idea is...
Pick two warriors and battle them, collecting the
scores
Copy the winner over the loser while making random
changes
Keep doing that until stopped
This one is a bit different in that it creates a soup of random
warriors first (if it doesn't already exist) then enters the evolving
loop, rather than creating a random warrior for any selected warrior
that doesn't exist. The nature of "pick two warriors" determines the
topology of the soup, and the nature of the "random changes" determines
the overall effectiveness of the evolution process. In this evolver, a
tie is considered the same as a loss, only clear winners are replicated.
Here's a psuedo-code representation of the LCE8
program, with most of the nitty-gritty details...
Set default parameters...
SoupSize - how many warriors in the soup
MaxLen - maximum evolved size of a warrior
Range - maximum soup distance for battle pairs
Hint - true to begin initial warriors with SPL, false for all random
Coresize - size of core for choosing big numbers
pmars command line - passed to the OS to run warrior battles
instruction string and count - base instructions
modifier string and count - instruction modifiers
mode string and count - address mode symbols
insert chance - chance of inserting a random or duplicate line
delete chance - chance of deleting a line
instruction chance - chance of changing the instruction
nodifier chance - chance of changing the modifier
address chance - chance of changing an A or B address mode
data chance - chance of randomly changing a A or B value
incdec chance - chance of incrementing or decrementing an A or B value
dup line chance - if line insert, chance of being a duplicate line
small number chance - if random data, chance of choosing a small offset
Randomize the random number generator using the system timer as a seed
If the INI file exists Then
Read replacement parameters from the INI file
If modifier string = "88" Then
modifier string = " "
modifier count = 1
88mode = true
If SoupSize>5000 Or MaxLen>500 Or Left(pmars,2) <> "pm" Then exit program
gridoffset = INT(SquareRoot(SoupSize))
temploops = INT((Sine(system timer) + 2) * 100)
Call Rnd temploops times to further randomize the random number generator
If warrior 1.red doesn't exist create a random soup...
For warrior = 1 to SoupSize
Open Str(warrior)+".red" for output
Write ";assert 1" to output file
If hint Then write "spl $ 0,$ 0" to output file
Number of lines = INT(Rnd * MaxLen + 1)
If hint Then Start line = 2 Else Start line = 1
For line = Start line to Number of lines (only if more lines to add)
Call Random line sub
Write redcode line to output file
Next line
Close file
Next warrior
Loop
warrior1number = INT(Rnd * SoupSize + 1)
If Range > 0 Then (ring topology)
warrior2offset = INT(Rnd * Range + 1)
If Rnd < .5 Then
warrior2number = warrior1number + warrior2offset
Else
warrior2number = warrior1number - warrior2offset
Else (select by grid topology)
Loop
warrior2number = warrior1number + INT(Rnd * 3 - 1)
warrior2number = warrior2number + INT(Rnd * 3 - 1) * gridoffset
Keep looping until warrior2number <> warrior1number
warrior2number = warrior2number MOD SoupSize
If warrior2number < 1 Then warrior2number = warrior2number + SoupSize
Print warrior1number " vs " warrior2number (tab) (no crlf)
warrior1 = Str(warrior1number)+".red"
warrior2 = Str(warrior2number)+".red"
Battle warrior1 and warrior2 in pmars writing to temp file
Open temp file for input
Read line from input file
score1 = value of text after "scores " in line
Read line from input file
score2 = value of text after "scores " in line
Close file
Print score1 " " score2 (tab) (no crlf)
If score1 > score2 Then
source = warrior1
destination = warrior2
Else
source = warrior2
destination = warrior1
Print source " --> " destination (crlf)
Open source for input
Open destination for output
Read first line from input and write to output
Length = 0
Loop
Read redcode line from input file
Saved line = redcode line
If Rnd < delete chance Then
If not end-of-file Then
read redcode line from input file
Saved line = redcode line
If Rnd < insert chance Then
Save redcode line
Call write sub (randomizes redcode line)
If Rnd < dup line chance Then restore redcode line
If Rnd < instruction chance Then
Replace instruction with a random instruction from instruction string
If Rnd < modifier chance Then
Replace modifier with a random modifier from modifier string
If Rnd < address chance Then
Replace A mode with a random mode from mode string
If Rnd < data chance Then
If Rnd < small number chance Then
Replace A data with INT(Rnd * MaxLen * 2 - MaxLen)
Else
Replace A data with INT(Rnd * Coresize)
If Rnd < incdec chance Then
If Rnd < .5 Then
A data = A data + 1
Else
A data = A data - 1
If Rnd < address chance Then
Replace B mode with a random mode from mode string
If Rnd < data chance Then
If Rnd < small number chance Then
Replace B data with INT(Rnd * MaxLen * 2 - MaxLen)
Else
Replace B data with INT(Rnd * Coresize)
If Rnd < incdec chance Then
If Rnd < .5 Then
B data = B data + 1
Else
B data = B data - 1
If 88mode Then
Call Check88 sub
If Bad88 Then redcodeline = Saved line
Call write sub
Keep looping until end of input file is reached
Close files
Keep looping until "q" is pressed
Exit program
Write sub:
If Length < MaxLen Then
Write redcode line to output file
Length = Length + 1
Call Random line sub (actually just drops through to it)
Return
Random line sub:
Loop
Randomly pick an instruction from the instruction string
Randomly pick a modifier from the modifier string
Randomly pick an address mode for the A field from the mode string
If Rnd < small number chance Then
A data = INT(Rnd * MaxLen * 2 - MaxLen)
Else
A data = INT(Rnd * Coresize)
Randomly pick an address mode for the B field from the mode string
If Rnd < small number chance Then
B data = INT(Rnd * MaxLen * 2 - MaxLen)
Else
B data = INT(Rnd * Coresize)
Call Check88 sub
Keep looping while Bad88 = true
Return
Check88 sub:
Bad88 = false
If 88mode Then
preInstr = first two chars of redcode line
Amode = character that's A-mode of redcode line
Bmode = character that's B-mode of redcode line
jumpinstr = false
If preInstr = "jm" Or
preInstr = "dj" Or
preInstr = "sp" Then
jumpinstr = true
If (jumpinstr And Amode = "#") Or
(jumpinstr = false And Bmode = "#") Or
((Amode = "@" Or Amode = "$" Or
Bmode = "@" Or Bmode = "$") And preinstr = "da") Or
(Bmode = "#" And (preInstr = "cm" Or preInstr = "sl")) Then
Bad88=true
Return
This isn't exactly how the code operates (moved things
for structure) but operationally it should be close. BASIC
error-handling is essentially a GOTO which usually interferes with
structuring the code even if I wanted to, not that I want to... things
like "keep looping", "loop until" etc are disguised GOTO's anyway so
might as well cut to the chase when it makes more sense to just jump.
String processing is left out of the psuedocode except where necessary,
a fixed-field warrior format is used to make it easy to apply the
mutations with fairly simple code.
Evolved results
Typical early output using the stock settings (grid of 256
warriors)...
;assert 1
spl.b # 3860,$ 3
spl.i $ 2342,* -20
mov.i > -6,} -1
djn.i } 953,@ 3886
djn.a { 1876,< -7
djn.ba @ 6,* -10
This warrior scores about 70 Wilkies.
In the same amount of time the '88 settings (a ring of 100 warriors)
produced this...
;assert 1
mov $ 4973,$ 3904
mov < 7624,$ 12
spl $ 7274,$ 6929
add $ 5409,< 10
sub $ -13,$ 5639
spl $ 3884,$ -19
mov $ 6,$ 16
spl $ 4705,# 15
spl < 1010,# 2
mov < 14,$ 1990
sub $ -4,< -5
spl $ -2,$ -17
spl < -3,# 5267
spl < 12,# 14
mov $ 2598,$ 17
jmz $ 6,@ 6550
spl $ 2,@ 5
slt $ -2,@ -14
A bit messy, scores about 60 Wilkies. At least it replicates.
Both of these are very early results, after the equivalent of about
an hour of evolving. Stronger results typically requires many hours to
days of evolving, and may require setting for a larger number of
warriors in the soup for more genetic diversity. The 88 run got up to
70+ Wilkies at one point but increased the number of rounds and they
all turned to stone... wasn't expecting that, didn't save any while
still paper...
Eventually the 88 run (continued from a soup saved before the stone
incident) produced this...
;assert 1
mov $ 5661,$ 7405
mov < 11,$ 7723
mov $ -2,< 4845
spl $ -2,# 6005
djn < -3,$ -5
djn $ 7924,< 6653
spl $ 1411,$ 6411
A bit more optimized, scores 72 Wilkies, but still too weak to even
make the "mixed" hill. Previous versions of LCE produced replicating
warriors scoring over 80 Wilkies, this one is presently 6th place on
the mixed hill...
;redcode
;name Confused Paper
;author TEV5/WTN
;evolved 58.red 5/25/09
;assert CORESIZE==8000
slt.x $ 1554,} 4041
spl.a $ -4,< -5
mov.b @ -5,} 16
seq.x $ -5,# 15
spl.f # 6370,{ -16
spl.i $ 5007,$ 17
mov.i * 1475,{ 1127
mov.i { 5488,> 9
mov.i < 13,{ -3
mov.i < 2356,{ -3
djn.i $ -2,{ 5681
div.x } 3451,{ 1762
sne.i * 4378,$ 3412
djn.i $ -16,@ 8
jmn.x # -4,} 4876
mov.i } 7736,* 5702
mov.ba $ 3353,* 2159
djn.ba > -14,$ 1
Note that the "TEV5" in the warrior comments has nothing to do with
J.M.'s truly tiny TEV0
(TEV is an obvious name to call a tiny/trivial evolver), here is the
v0.5 version of my "trivial" series...
soupsize=100:maxlen=20:range=3:spl=1:cs=8000:pmars$="pmars -s 8000 -p 8000 -c 80000 -l 100 -d 100 -b -r 50" |
The INI file format is different than the current LCE8, order of the
data is in the INPUT on the fifth code line - the dup-line rate
parameter was placed after delete line rate and there was no inc/dec
mutation in this version. Tests seemed to indicate that incrementing
and decrementing existing values to fine-tune algorithms could lead to
cleaner code, but not necessarily stronger warriors and if the inc/dec
rate was set too high seemed to hurt performance. In the present LCE8
defaults, about 28% of the number mutations are inc/dec operations but
keep in mind it is extremely difficult to determine optimum parameters
for an unguided evolver - every run is different and it requires many
time-consuming runs for each parameter set before any conclusions can
be drawn about the parameters. Also the final outcome heavily depends
on the makeup of random code generated during the initial phases of
evolution, once one of the seeds evolves to become the dominant soup
form it tends to inhibit the evolution of new forms. Larger soups (1000
warriors or more) tend to increase the odds of a good seed form being
created or evolving in the early stages before any one form becomes
dominant. Large soups also increase diversity by providing more room
for islands of different "species" of warriors to develop and compete
with each other, driving up the overall strength. Of course large soups
also take longer to evolve and test so it's a tradeoff, so sometimes I
instead use a smaller soup of 100-200 warriors and if I don't like what
I see early on I start over.
For serious evolving, an evolver such as RedMixer permits better
monitoring of the process and better tracking of what parameters
produced what code at what generation, however small programs like LCE
and other "tiny" evolvers make it easier to try new things (like
88-rules evolving) without the weight of dozens of kilobytes of code.
Although they lack the features of larger evolvers occasionally can
perform at close to the same level, especially when evolving nano-size
warriors where it is possible for a sub-2K program to produce quite
acceptable results. BTW the nano parameters listed in the LCE8 docs
probably are not optimal - maybe try spl mov mov djn or spl mov mov mov
djn with no weighting of the address modes. I have also noticed with
varients of TEV0, my JB evolver and others that
evolving using a fixed instruction.modifier list can be as effective
and faster than evolving the modifier separately. There is still much
research to do when it comes to evolving warriors.
Terry Newton (wtn90125@yahoo.com)