
  MEVO - a Multi-threaded Evolver
  ===============================

MEVO is a program that evolves warriors for the game of corewar.
If new to the game check out www.corewar.co.uk or www.koth.org for more
information. In a nutshell, corewar is a game where warrior programs written
in a simple language called "redcode" battle each other in a simulated memory
"core". Warrior programs attempt to cause the other warrior(s) in the core to
perform an invalid operation. A control program, called the MARS (for memory
array redcode simulator) directs the battles by alternating execution between
the competing warriors until only one warrior is still running, or a limit
of execution cycles is reached. Usually many battle rounds are performed
with the opponents separated by different distances, giving 3 points for
each win and 1 point for each tie, and normalizing the results to a 0-300
scale for easy comparison, whether battling a single opponent or averaging
the results of battles against many warriors. Although many warriors can
fight at once, usually battles are between a pair of warriors. There are
different corewar environments based on the size of the core, each with
various public "hills" where players can email submissions. Most hills
have a limited number of positions, although there are also infinite
archive hills where warriors always place and are preserved indefinitely.
The most popular coresizes are 80 (nano), 800 (tiny) and 8000 (standard).
With these, the number of processes each warrior can launch (using SPL)
is the same as the coresize, and the total number of cycles before declaring
a tie is 10 times the coresize. The maximum number of instructions a warrior
can start with is limited by the hill rules, typically nano warriors are
limited to 5 instructions, tiny warriors are limited to 20 instructions,
and standard warriors are limited to 100 instructions. Typically the minimum
separation when loading warriors for battle is the same as the maximum size.

This can be expressed in table form as follows...

            nano     tiny      standard
coresize    80       800       8000
processes   80       800       8000
cycles      800      8000      80000
maxlen      5        20        100
mindist     5        20        100

These numbers correspond with MEVO settings and are passed to the MARS
simulator, typically the pmars program. Other environments exist, including
coresize 8192 and coresize 55440.


About evolving
--------------

For many years warriors were only hand-written, but today's powerful PC's
permit using genetic algorithms (GA) to "evolve" warriors. Successfulness
of evolving techniques depend on the coresize environment, it's fairly
easy to evolve competitive nano warriors, it is difficult but possible
to evolve good tiny warriors, and it is very difficult to evolve warriors
for coresize 8000 that can compete with strong hand-coded specimens. One
reason for this is as search space increases, so does the advantage of
writing the programs using a thinking brain. Another reason is thinking
brains have a hard time writing code where each instruction element is
interdependent on the other elements to produce a sum effect (as opposed
to discrete actions), so in size-limited environments like nano the
advantage often goes to evolved warriors.

I have written several evolvers over the years, each testing various ideas
and building off of previous efforts to learn about some of the finer details
of the "art of evolving". Art means different things to different people, so
some of my ideas are subjective. I prefer to practice "pure" evolving, where
warriors are produced with a minimum of "special" knowlege of corewar.
I'm impressed when useful warrior algorithms arise on their own, without
specifying how the code should be written. There are other evolvers that
use hints or other sophisticated methods to determine what instructions
follow others, what addressing modes to use with certain instructions,
or even directly assimilate existing redcode. These evolvers can produce
stronger results in larger coresize environments compared to pure evolvers,
however I still prefer the pure approach for its simplicity and resemblence
to natural evolution. In particular, for nano often extremely simple
evolving techniques can prevail over much more sophisticated methods, in
fact there seems to be an inverse relationship between the simplicity of
the evolving code and the quality of the nano warriors produced by it.
To a degree... the goal of this evolving "game" is to try to find the
optimum balance between simplicity and success.

There are other factors that have nothing to do with actual evolving
but greatly inflate the size of the evolver code, in fact most of the
code in most evolvers is for mundane tasks like reading/writing INI files,
displaying results, providing a user interface, benchmarking, etc.
Simplicity matters here too but only for making the program easy to
operate yet still provide enough options to experiment with and help
produce stronger results. It is possible to make a "bare-bones" evolver
that's as strong as MEVO and other pure evolvers, particularly for nano,
using less than 5K bytes of primitive line-numbered BASIC. They just
don't have nice features to help operate them and analyse the results.

The key algorithm present in almost all of my successful evolvers is:

Start with a population of warriors (random or otherwise)
DO
   Randomly pick two nearby warriors (arranged on a grid or ring)
   Battle them in a MARS program and collect the scores
   Replace the losing warrior with a mutated copy of the winning warrior
   (in the event of a tie it doesn't matter much, just pick a winner)
LOOP UNTIL the evolver is stopped.

This works. Other methods may work too, not saying this is the only
method, but it is perhaps the simplest method and is very close to how
evolution occurs in the natural world... competing for resources and
replication with mutations. Some mutations result in stronger code, able
to win battles and reproduce further, poor mutations result in weaker
code that eventually gets replaced with stronger code. A subtle but
very important aspect of this algorithm is it does not force strict
evaluation, a weak warrior might get paired with a weaker warrior
and win, replicating and possibly improving even though it might be
surrounded by much stronger warriors. It often takes many steps for
one warrior form to transform into a possibly better form, often
losing strength before fully developing a better strategy. If all
weak warriors are immediately killed off then there is no opportunity
for stepped transformation to happen, and unless one strategy happens
to change into another in a single step (very rare), no new strategies.
Instead, to more accurately model natural processes the evolver
should allow weaker members to "get away" from stronger predators.
At least for a time, if the mutation truly has no possibilities
then the bad code will be replaced. This need not be specifically
programmed, it is a consequence of using simple random pair battles.

Imparting topology (shape) to the "soup" (population of warriors) is
important because it permits different areas of the soup to evolve
semi-independently. Rings work (especially with smaller soups), battle
partners can be chosen to be within a certain number of positions of
each other, not too far but far enough to permit skipping over warriors
so forms can cross each other and weak code gets an opportunity to battle
other weak code to further evolve. Grids of warriors seem to work better
when there's a fairly large soup to provide sufficient separation, they're
exposed to other warriors on many sides thus can evolve to resist multiple
strategies at once. The difference isn't huge but grids lend themselves
to display on a computer screen so they're my favorite topology. Usually
in a grid-based evolver battles are between pairs of adjacent warriors,
as in pick a random warrior, then pick one of its eight surrounding
warriors to form the battle pair.

Mutations can be almost anything that randomly changes the code, it is
here that various degrees of "pure" can be applied as needed. A totally
pure evolver would mutate all elements equally with each element having
a flat chance of selecting any of the possible choices. While this produces
evolution, it typically results in weak code because some instructions and
other elements are more useful than other elements. An extreme example is
nano warriors are almost always composed of SPL MOV and DJN with the MOV
instruction occuring most often. Many strong nano warriors follow the
sequence SPL MOV MOV MOV DJN. Another strong form is SPL MOV SPL MOV DJN.
Other strong forms are MOV SPL MOV MOV DJN and SPL MOV MOV MOV MOV.
The top 20 nano warriors on the Koenigstuhl Nano Hill follow these
forms except for one SPL MOV MOV DJN SPL form. There's a pattern here,
in these examples there are 6 SPL's, 14 MOV's and 4 DJN's and none of
the other redcode instructions. Similar patterns appear in the modifiers,
address modes, and ratio of small to large numbers. So although it's
imparting some corewar knowledge to weight the code elements in similar
proportions, I still consider this "pure" since it in no way specifies
the order the instructions should appear or anything about how the code
should work. It is merely choosing more useful elements more often.
Also in the case of nano, often I include at least some of the other
instructions anyway as this produces a greater variety of code for the
warriors to encounter and learn how to defeat, even though evolution
always ends up choosing SPL MOV and DJN anyway. At least for nano.
Similar effects appear in other coresizes, but with different
instructions and proportions, but still MOV and SPL tend to occur
more often than the other instructions.

Another class of mutations are those that rearrange code. These often
include inserting lines (sometimes a duplicate of the previous line),
deleting lines, and swapping two lines. A more advanced class of
mutation is crossover where the code from two warriors is mixed
together to produce an offspring. Crossover is tricky with redcode,
if the two warriors aren't very similar to begin with then a high
proportion of broken warriors is produced, so some form of species
tracking is usually needed. Another consideration is it helps to
choose strong code to mix with rather than weak code, one way to
do this is to track of how many battles a warrior has won so that
the winning warrior can select the best similar warrior to cross with.
Redcode crossover is still a highly experimental thing - there seems
to be a benefit in previous evolving experiments but it is difficult
to tell if the benefit is actually from genetic crossover (actually
blending warrior strategies) or simply due to increased mutations of
a different kind (replacing lines with other pre-tested lines).

Mutation rates are fairly critical, a certain number of exact copies
is useful to avoid destroying strong warriors that happen to arise
before they can be extracted and used, but there should also be a
chance of making many changes at once to improve the chances of
making a useful transformation in a single step. Typically I use
separate mutation rates for the instructions, modifiers, address modes,
numbers, inserts, deletes and swaps, with additional settings controlling
the chance of duplicate lines, the chance of incrementing or decrementing
an existing number rather than choosing a random number (although it can
be a completely separate mutation and is somewhat dubious, be sure to
disable for comparison) and the chance of choosing a large random number
rather than a small random number (or using numerical methods to weight
the numbers to produce a useful proportion).


About MEVO
----------

The main reason I wrote MEVO was I wanted an evolver that could multitask
to improve performance on systems with dual-state or multi-core processors.
I also wanted a full-featured evolver that used an array-based soup, not only
to reduce disk access but also because it makes it much easier to implement
new mutations such as swap lines that are more difficult to program in a
streaming file-based approach. Finally, I wanted a more modern framework
in which to express my ideas, one that is more structured and more compatible
than previous evolvers I've written in QBasic, and not subject to dos memory
and environment constraints which prevent things like an in-memory soup and
cause compatibility issues. New ideas are nice when they work, but was not
a major goal for MEVO. Rather I wanted to combine previous ideas I've found
useful into a single program that I can further extend as needed. Presently
the only new things (for me) I'm trying in this program are using a grid soup
with no wraparound, a reinsertion option that randomly chooses from all
previously saved high-scoring warriors instead of only the top-scoring
warrior, a crossover implementation that allows controlling the proportion
of crossed code, and a logging feature to generate run statistics.

MEVO has these features...

* Variable-size grid soup with no wraparound on the sides
* Memory-based soup to reduce disk access and simplify mutation code
* Runs from 1 to 20 copies of pmars at once for multi-processing
* Uses mostly the same time-tested evolving methods I've used for years
* Configurable for different coresizes, processes, cycles, rounds, etc
* Compatible with pmars or exmars for performing battles
* User-specified instructions, modifiers and addressing modes
* Mutation rates for instructions, modifiers, modes and numbers
* Mutation rates for line insert, line delete and line swap
* Additional odds for duplicate line, increment/delete and big numbers
* Variable warrior sizes with a separate maximum evolved size
* Warriors always start execution at the 1st code line
* Tracks origin, species and generation of each warrior
* Counts instruction changes, changes species if over a specified percentage
* Optional crossover with separate rates for flipping to and from the mate
* Mate is a surrounding warrior with the same size/species and the most wins
* Optional periodic benchmarking and saving of strong warriors
* Optional periodic reinsertion of strong warriors
* Optional logging of start/stop times and benchmark results
* Optional separate benchmark set for manually testing individual warriors
* Separate rounds for benchmarking (for nano can use permutate)
* All settings controlled using a text-based INI file
* Soup display shows warrior lengths, colorized by species
* Soup explorer permits examining, running, battling and testing warriors
* On exit saves soup warriors to a soup.dat file and to individual files
* Reloads the soup.dat file when running to continue a run
* Written in the native FreeBasic language for Linux or Windows

Performance-wise, can make nano warriors with nanobm07 scores of over 155
(plenty good enough to compete on the SAL Nano Hill) and can make standard
warriors for coresize 8000 with wilkies scores of over 95. So far.
Here's an example paper-type warrior for coresize 8000...

;redcode
;name 60_13
;author mevo
;strategy evolved
;generation 189
;species 3220
;origin 49_13
;assert 1
mov.i  $-7,<17
mov.i  {2635,*-2075
spl.ba #3715,}-1561
spl.i  {-3134,>18
spl.i  >703,*1045
spl.ba #3089,>2322
mov.i  }-8,}-3
mov.i  >-9,}-3
div.i  #7,{2985
mov.i  $-2958,{580
end
;benchscore 95.75  (wilkies 100 rounds)


The mevo.ini file
-----------------

Here is an example INI file for evolving standard warriors...

----------- begin mevo.ini (for coresize 8000) ------------
;ini file for mevo
xsize:    77  ;width of soup
ysize:    21  ;height of soup
maxsize:  20  ;max evolved length
;pmars parameters...
coresize: 8000  ;size of core array
processes:8000  ;max processes
cycles:   80000  ;cycles before tie
maxlen:   100  ;maximum warrior length
mindist:  100  ;minimum separation
rounds:   40  ;# of battle rounds
pmarsbin: exmars  ;path/name of pmars binary
pmarsvbin: pmarsv  ;path/name of pmarsv binary
pmarsvopt: -v 014  ;pmarsv view options etc
;mutation parameters...
instrate: 0.015  ;chance of instruction change
modrate:  0.03  ;chance of modifier change
moderate: 0.03  ;chance of address mode change
datarate: 0.06  ;chance of field value change
insrate:  0.01  ;chance of line insert
delrate:  0.01  ;chance of line delete
swaprate: 0.01  ;chance of line swap
dupline:  0.1  ;if insert, chance of dup line
incdec:   0.3  ;if data, chance of inc or dec
bignum:   0.5  ;if data, chance of big number
;crossover parameters...
enablecross:  no  ;if yes then cross with surrounding warrior
flipmaterate: 0.3  ;chance of changing to mate
flipbackrate: 0.3  ;chance of flipping back
;code generation...
instructions: nop mov mov mov mov mov spl spl spl spl djn djn
instructions: add sub mul div mod jmp jmz jmn sne seq slt dat
modifiers: .i .i .i .a .b .f .x .ab.ba
modes: $$#@*<>{}
;bench parameters...
enablebench: yes  ;yes to enable these settings
benchrounds: 100  ;rounds used for benchmarking
savethresh: 92  ;percent of top score to save
reinsertmode: 2  ;0=none 1=top.red 2=from save
benchinterval: 1000  ;bench every n iterations (0=none)
reinsertinterval: 5000  ;re-insert every n iterations (0=none)
benchdir: wilkies  ;directory containing benchmark warriors
savedir: save  ;directory to save warriors to
testdir:   ;directory for single-test warriors (def.benchdir)
;other parameters...
initmode: 1  ;start warriors 0=first inst, 1=random
spthresh: 5  ;percent change before different color
infoline: evolved  ;added to strategy line
threads:  1  ;# of processing threads
threadsleep: 0  ;# ms to sleep between threads
enablelog: no  ;yes to log to mevo.log file
displayopts: 24,10,11  ;term height,text col,frame col,unicode
;end of ini file
----------- end mevo.ini ----------------------------------

Here is an example INI file for evolving tiny warriors...

----------- begin mevo.ini (for coresize 800) -------------
;ini file for mevo
xsize:    77  ;width of soup
ysize:    21  ;height of soup
maxsize:  20  ;max evolved length
;pmars parameters...
coresize: 800  ;size of core array
processes:800  ;max processes
cycles:   8000  ;cycles before tie
maxlen:   20  ;maximum warrior length
mindist:  20  ;minimum separation
rounds:   40  ;# of battle rounds
pmarsbin: pmars  ;path/name of pmars binary
pmarsvbin: pmarsv  ;path/name of pmarsv binary
pmarsvopt: -v 344  ;pmarsv view options etc
;mutation parameters...
instrate: 0.015  ;chance of instruction change
modrate:  0.02  ;chance of modifier change
moderate: 0.03  ;chance of address mode change
datarate: 0.07  ;chance of field value change
insrate:  0.007 ;chance of line insert
delrate:  0.01  ;chance of line delete
swaprate: 0     ;chance of line swap
dupline:  0.1  ;if insert, chance of dup line
incdec:   0.5  ;if data, chance of inc or dec
bignum:   0.6  ;if data, chance of big number
;crossover parameters...
enablecross:  yes  ;if yes then cross with surrounding warrior
flipmaterate: 0.3  ;chance of changing to mate
flipbackrate: 0.3  ;chance of flipping back
;code generation...
instructions: spl spl spl spl spl mov mov mov
instructions: mov dat dat dat jmp jmn jmz djn
instructions: sne seq slt add sub mul div mod
modifiers: .i .i .i .a .b .f .x .ab.ba
modes: $$#@*<>{}
;bench parameters...
enablebench: yes  ;yes to enable auto-bench/re-ins
benchrounds: 200  ;rounds used for benchmarking
savethresh: 93  ;percent of top score to save
reinsertmode: 2  ;0=none 1=top.red 2=from save
benchinterval: 1000  ;bench every n iterations (0=none)
reinsertinterval: 10000  ;re-insert every n iterations (0=none)
benchdir: franz  ;directory containing benchmark warriors
savedir: save  ;directory to save warriors to
testdir:   ;directory for single-test warriors (def.benchdir)
;other parameters...
initmode: 1  ;start warriors 0=first inst, 1=random
spthresh: 5  ;percent change before different color
infoline: evolved  ;added to strategy line
threads: 1  ;# of processing threads
threadsleep: 0  ;# ms to sleep between threads
enablelog: no  ;yes to log to mevo.log file
displayopts: 24,10,11  ;term height,text col,frame col,unicode
;end of ini file
----------- end mevo.ini ----------------------------------

Here is an example INI file for evolving nano warriors...

----------- begin mevo.ini (for coresize 80) --------------
;ini file for mevo
xsize:    77  ;width of soup
ysize:    21  ;height of soup
maxsize:  5  ;max evolved length
;pmars parameters...
coresize: 80  ;size of core array
processes:80  ;max processes
cycles:   800  ;cycles before tie
maxlen:   5  ;maximum warrior length
mindist:  5  ;minimum separation
rounds:   150  ;# of battle rounds
pmarsbin: pmars  ;path/name of pmars binary
pmarsvbin: pmarsv  ;path/name of pmarsv binary
pmarsvopt: -v 564  ;pmarsv view options etc
;mutation parameters...
instrate: 0.02  ;chance of instruction change
modrate:  0.03  ;chance of modifier change
moderate: 0.04  ;chance of address mode change
datarate: 0.06  ;chance of field value change
insrate:  0.01  ;chance of line insert
delrate:  0.01  ;chance of line delete
swaprate: 0.01  ;chance of line swap
dupline:  0  ;if insert, chance of dup line
incdec:   0.3  ;if data, chance of inc or dec
bignum:   0.5  ;if data, chance of big number
;crossover parameters...
enablecross:  no  ;if yes then cross with surrounding warrior
flipmaterate: 0.3  ;chance of changing to mate
flipbackrate: 0.3  ;chance of flipping back
;code generation...
instructions: mov mov mov mov mov spl spl spl djn djn
instructions: add sne seq slt jmn jmz mod
modifiers: .i    .i .a .b .f .x .ab.ba
modes: $$#@*<>{}
;bench parameters...
enablebench: yes  ;yes to enable auto-bench/re-ins
benchrounds: 142  ;rounds used for benchmarking
savethresh: 95  ;percent of top score to save
reinsertmode: 2  ;0=none 1=top.red 2=from save
benchinterval: 1000  ;bench every n iterations (0=none)
reinsertinterval: 5000  ;re-insert every n iterations (0=none)
benchdir: nanobm07  ;directory containing benchmark warriors
savedir: save  ;directory to save warriors to
testdir:   ;directory for single-test warriors (def.benchdir)
;other parameters...
initmode: 1  ;start warriors 0=first inst, 1=random
spthresh: 5  ;percent change before different color
infoline: evolved  ;added to strategy line
threads: 1  ;# of processing threads
threadsleep: 0  ;# ms to sleep between threads
enablelog: no  ;yes to log to mevo.log file
displayopts: 24,10,11  ;term height,text col,frame col,unicode
;end of ini file
----------- end mevo.ini ----------------------------------

If MEVO is run with no mevo.ini file present it creates an INI file
for coresize 800 (not optimized).

The following is a detailed explanation of the INI settings.

;ini file for mevo
xsize:    77  ;width of soup
ysize:    21  ;height of soup

These settings specify the size of the soup, the terminal window used to run
MEVO should be at least 3 positions larger in both the X and Y directions.
Maximum supported size is 130 by 100 (13,000 warriors), modify the code
to change the limits but a soup of this size is probably not practical
except on a very powerful PC with enough display area to display such a
large soup. For the Linux xterm program the -geometry option can be used
to specify the terminal size, i.e. if using a soup size of say 100 by 50
add -geometry 100x50 to the xterm command line in the run_mevo.sh file.
For Windows there's probably a clicky thing to set size properties.
Note... the file listing subroutine assumes a minimum terminal height
of 24 lines so don't use less than that. If ysize is more than 21 then
the terminal is assumed to have a height of at least ysize+3 lines.

maxsize:  5  ;max evolved length

This setting determines the maximum length of evolved warriors. For larger
sizes the initial warriors are created with 1 to maxsize instructions.
If maxsize is 5 or less then all warriors are initially maxsize long.

;pmars parameters...
coresize: 80  ;size of core array
processes:80  ;max processes
cycles:   800  ;cycles before tie
maxlen:   5  ;maximum warrior length
mindist:  5  ;minimum separation

These parameters specify the MARS environment. If using pmars the maxlen
setting must be the same or greater than the maxsize setting. If using the
stock exmars simulator then set maxlen to 0 to inhibit using the -l parm.

rounds:   150  ;# of battle rounds

This setting determines how many individual rounds are performed for
each battle. Higher number of rounds produces more accurate scoring and
potentially higher maximum soup strength, but requires more processing
time and in larger coresizes, tends to inhibit the production of
paper-type warriors.

pmarsbin: pmars  ;path/name of pmars binary
pmarsvbin: pmarsv  ;path/name of pmarsv binary

These set the binary names, they must contain the string "mars".
If the binaries are not in the current directory or in a path directory
then include the full path to the binary (i.e. c:\myprogs\pmars-server.exe
or for Linux something like ~/pmars if placed in the user home directory).

pmarsvopt: -v 564  ;pmarsv view options etc

These are options passed to pmarsv when running or battling warriors.
The -v specifies view parm with a 3-digit number afterwards to specify
speed (0=fastest, 9=slowest), graphics display (experiment) and
detail level (typically 4 for all). Older versions of pmarsv might
not be slow enough when running nano warriors, add [space]-r 10 to
run 10 rounds instead (also may be handy when using the battle function).

;mutation parameters...
instrate: 0.02  ;chance of instruction change
modrate:  0.03  ;chance of modifier change
moderate: 0.04  ;chance of address mode change
datarate: 0.06  ;chance of field value change

These determine the chances of performing different mutations, ranging
from 0 (never) to 1 (always, not a reasonable setting). The odds are applied
evenly to all items (or lines). Typically mutation rates are selected to be
low enough so that sometimes to often nothing at all changes, but high enough
to possibly change multiple things at once. Data (number) changes tend to be
most useful for adjusting existing forms without breaking the code so this
rate is usually set to be the highest, instruction changes often result in
broken code but are necessary to create new forms, so instrate is usually
set fairly low. The modrate and moderate settings usually fall somewhere
in between instrate and datarate.

insrate:  0.01  ;chance of line insert
delrate:  0.01  ;chance of line delete
swaprate: 0.01  ;chance of line swap

These settings perform major mutations by rearranging code, or in the
case of insrate, possibly creating new code. Lines are removed only if
the current warrior size is more than 1. Inserted lines move other code
lines forward, truncating lines if the warrior exceeds maxsize. Swaprate
is used only if on the 2nd or greater line, and swaps the line with the
previous line.

dupline:  0  ;if insert, chance of dup line

This setting determines the odds of an inserted line being a duplicate
of the previous line (assuming code line 2 or greater), otherwise a
random line of code is inserted.

incdec:   0.3  ;if data, chance of inc or dec

If a data change is triggered, this setting determines the odds of
performing an increment or decrement of the existing number rather
than choosing a new random number. This can be helpful for finding
loop points again after an insert or delete, but it is also a somewhat
dubious setting - in past experiments good results were obtained
even if set to 0 for no adjustments.

bignum:   0.5  ;if data, chance of big number

If a data change is triggered and a random number is selected, then
this setting determines the odds of choosing a large number that spans
the entire core rather than a small number that (approximately) spans
the size of the warrior.

;crossover parameters...
enablecross:  no  ;if yes then cross with surrounding warrior

If no then only mutation is performed. If yes, looks for a surrounding
warrior that's the same size and species, and with the most wins. If there
are multiple candidates with the same number of wins it randomly chooses one.
The warrior that just lost the battle is excluded from consideration.
If a mate is not found then uses just mutation. If a mate is found then
the first instruction(s) will randomly come from the winning warrior or
the mate. As the copy/mutation proceeds a "flip" flag determines if lines
are copied from the winning warrior or the crossover mate, the flip
settings determine how often the flip flag is changed.

flipmaterate: 0.3  ;chance of changing to mate

If the copy source is the winner, determines the odds of changing
the source to the crossover mate.

flipbackrate: 0.3  ;chance of flipping back

If the copy source is the mate, determines the odds of changing
the source to the winning warrior.

The flipmaterate and flipbackrate settings determine the average number
of lines in each chunk (1/setting), and the proportion of code from the
crossover mate. To include mostly the winning warrior code make the
flipmaterate setting smaller than the flipbackrate setting.

;code generation...
instructions: mov mov mov mov mov spl spl spl djn djn
instructions: add sne seq slt jmn jmz mod
modifiers: .i    .i .a .b .f .x .ab.ba
modes: $$#@*<>{}

These strings determine the code that is generated and must be correct
or a shower of errors will result when evolving. If soup.dat is present
then these settings are ignored. Each instruction must be 3 characters
long separated by a single space, additional instructions: lines add
to the internal string. Each modifier must be 3 characters long (including
padding space) with no padding between 3-character fields. Use 3 spaces to
include a no-modifier option but has to be surrounded by other entries.
Set modifiers: to a tab character to use no modifiers at all.
Addressing modes must be one after the other with no spaces.

;bench parameters...
enablebench: yes  ;yes to enable auto-bench/re-ins

Set this to yes to enable automatic benchmarking and/or re-insertion,
set to no to disable these features.

benchrounds: 142  ;rounds used for benchmarking

This setting determines how many rounds per battle are used when
benchmarking warriors, automatically or manually using the test function.
If coresize is 80 and benchrounds is 142, then the pmars -P parameter is used
to perform a "permutate" sequence for maximum accuracy and speed, this
requires pmars 0.9.2 or above. If using with exmars or an older pmars with
nano warriors then set benchrounds to 500 or so (1000 is more accurate).
Typically for coresize 800 a benchrounds setting of 200 or more is needed,
and for coresize 8000 a benchrounds setting of 100 or more is needed to
produce reasonably accurate benchmark results (+/- 5 points or less).

savethresh: 95  ;percent of top score to save

When automatically benchmarking warriors the program keeps track of the
highest score so far in the run, warriors are saved to the save directory
if they score within savethresh percent of the top score.

reinsertmode: 2  ;0=none 1=top.red 2=from save

Set to 0 to disable reinsertion, set to 1 to periodically reinsert the
top.red warrior back into the soup, or set to 2 to periodically reinsert
a randomly selected warrior from the save directory. This is a somewhat
dubious function but still a subject of study. Reinserted warriors might
further evolve and become stronger, or they may cause warriors around
the newly inserted warrior and its decendents to evolve to learn to
defeat the inserted warrior(s), and possibly produce lower benchmark
scores. Using option 2 minimizes this effect. Reinsertion can help drive
up benchmark scores by rewarding high-scoring warriors, but can also
cause the soup to evolve techniques that are "focused" on defeating the
benchmark warriors and not other warriors, resulting in lower scores
against other benchmark sets.

benchinterval: 1000  ;bench every n iterations (0=none)

Determines the frequency of benchmarking, set to 0 to disable
automatic benchmarking. Don't set too low or it'll spend most of the
time benchmarking and not evolving and may generate an excessive number
of saved warriors (warriors that score the same as previous tests are
not saved to avoid duplicates but only 500 previous scores are saved).

reinsertinterval: 5000  ;re-insert every n iterations (0=none)

Determines the frequency of re-insertion. Typically this should be
set to 3 times the total number of soup warriors (xsize * ysize * 3)
or higher to avoid excessive focusing effects.

benchdir: nanobm07  ;directory containing benchmark warriors

[path]name of a directory containing benchmark warriors, which must
be appropriate for the configured coresize. If enablebench is yes then
this directory must contain warriors or the program won't start.
Benchmark warriors must have .red, .war or .rc extensions, other
files present in the specified directory are ignored.

savedir: save  ;directory to save warriors to

This setting permits changing the name of the directory to save
warriors to. Useful if running on a ram disk but desirable to preserve
saved warriors in the event of a power failure etc.

testdir:   ;directory for single-test warriors (def.benchdir)

Permits using a different benchmark set for the test function, otherwise
the test function uses the warriors specified by benchdir.

;other parameters...
initmode: 1  ;start warriors 0=first inst, 1=random

If set to 0, new populations begin with the 1st instruction, modifier
and mode specified in the code settings, with 0 numbers. If set to 1
(the usual setting) new warriors start with random code. This setting
is ignored when continuing a run.

spthresh: 5  ;percent change before different color

This setting determines when warriors in the soup display change colors,
expressed as a percentage of maxsize. If the number of instruction
changes *exceeds* spthresh % of maxsize then a new color is selected.

infoline: evolved  ;added to strategy line

For convenience.

threads: 1  ;# of processing threads

This setting specifies the number of parallel threads to use to increase
performance on machines with multiple CPU's. For single-core processors
without HyperThreading set to 1. Maximum setting allowed is 20. Typically
for a HyperThreaded or (theoretically) a multi-core processor a setting
of 4 to 8 threads results in maximum performance. A new set of temp files
is written to in the temp directory for each additional thread.

threadsleep: 0  ;# ms to sleep between threads

How many milliseconds to sleep between launching each thread, or if a
single thread, after running pmars and the mutation process. To reduce
CPU usage and system load, set threads to 1 and set threadsleep to a number
from about 25 to 1000 or so (larger numbers for larger coresizes), relative
to how long pmars usually takes to complete a battle.

enablelog: no  ;yes to log to mevo.log file

If set too yes then start and stop times and iteration counts and the
results of all benchmark tests are appended to the mevo.log file.
This can be useful for determining evolution speed for optimizing
the threads setting, and generating data to use to analyse a run.
For benchmarks the following items are logged: bench score, top score,
generation, date, time, iteration count and if saved, filename saved to.

displayopts: 24,10,11  ;term height,text col,frame col,unicode

These options set display parameters. The first option is the minimum
number of lines used for displaying text files (if ysize+3 is larger then
increases). The 2nd and 3rd numbers are the colors used for text and the
soup border. A 4th option (not shown) specifies text or unicode border
(,0 for text or ,1 for unicode), unicode border only works under Linux.
Note that not all Linux terminals support unicode, add ,0 if problems.

;end of ini file

MEVO must be restarted for any INI changes to take effect.
Some settings should not be changed during a run, specifically the
soup size parameters, maxsize, the pmars coresize, and only change
the pmars processes cycles maxlen and mindist settings during a run
if you know what you're doing. Code generation settings (instructions,
modifiers, modes) are ignored when continuing a run so don't change them
to avoid confusion, if absolutely necessary edit the soup.dat file to
alter the code strings but don't alter existing items, only add new
items and make the same changes to the .ini file to document.
Avoid changing the benchdir setting unless the save directory is
also renamed or the scores produced by the new benchmark set are
very similar, different benchmarks often produce different scores
and this can throw off the extraction method.


Compiling MEVO from source
--------------------------

MEVO is written in the native FreeBasic language (http://www.freebasic.net/).
To compile from source, install FreeBasic for Windows or Linux. I use the
0.20.00b standalone Linux version, I simply copied the FreeBasic directory
tree to a directory (didn't run the install script) and make a symlink
to the fbc binary in /usr/local/bin. For producing a Windows binary I
installed FreeBasic into wine using the stock Windows installer, accepting
the defaults (which will be used for command line examples).

The mevo.bas source code must be edited under OS setup to match the platform.
Change the usewin setting to 0 to compile for Linux, or 1 for Windows.
Change the useuni setting to 0 to use an ascii soup border, or 1 to use
unicode graphics characters (note - Windows might not support unicode in
a console window). Change the textcolor and framecolor settings as preferred.
To distinguish versions I name the Windows-configured source to Mevo.bas
and use just mevo.bas for the Linux-configured source.

To compile for Windows, open a command prompt in the directory containing
the source (use CD if you don't have the "command prompt here" tool).
To compile enter: "c:\program files\freebasic\fbc" -mt Mevo.bas
(adjust the path if not in the default install location)

To compile for Linux, open a command prompt in the directory containing
the source (use CD if the file manager can't open a prompt in the directory,
for Gnome I usually add a gnome-terminal script to nautilus-scripts for this).
To compile enter: fbc -mt mevo.bas
(add a path before fbc if no symlink to it)

If debugging, add the -exx option (in addition to -mt) to enable
bounds-checking and reporting line numbers where errors occur.

The Linux binary cannot be just double-clicked to run, on many systems
that would run it "headless" with no user I/O so it checks for the
TERM variable to make sure it's running in a terminal, plus often the
OS does not set the current directory, causing it to run typically in
the user home directory instead. The mevo binary can be run from a
command prompt terminal but for double-click convenience usually
a shell script is used to change to the program directory and launch
in a terminal, setting it to a black background for the best look...

----------- begin run_mevo.sh -----------------------------
#!/bin/bash
cd `dirname $0`
PATH="$PATH:."
xterm -geometry 80x25 -bg black -fg green -e ./mevo
----------- end run_mevo.sh -------------------------------

The script should be in "unix" format (type it in using an editor
to ensure - make sure the ` characters in the cd command are correct,
these are the unshifted ~ key next to 1 on most keyboards). The properties
for the run_mevo.sh file need to be set to permit executing as a program.
Note that the cd command can only work if there are no spaces in the
directory name(s) in the path to the program directory. The current
directory is added to the PATH variable in case pmars/pmarsv is located
in the program directory. The xterm terminal is used because it's
common and has command line options for setting the colors.

Here is another run script that tries several terminals and allows putting
the binaries in a bin directory to avoid clutter in the main directory...

----------- begin run_mevo.sh -----------------------------
#!/bin/bash
cd `dirname $0`   # change to program directory
PATH=".:bin:$PATH"  # add current and bin directory to the path
# try running in the xterm terminal (permits setting size color etc)
xterm -geometry 80x24 -bg black -fg green -e mevo
# if that doesn't work try other terminals (using defaults)
if [ "$?" -ne 0 ];then
konsole -e mevo || terminal -e mevo || rxvt -e mevo || gnome-terminal -e mevo
fi
----------- end run_mevo.sh -------------------------------


Using MEVO
----------

Caution: On modern OS's MEVO produces less disk access than some evolvers
but some is much more than none, so DON'T run MEVO on a solid-state drive
(like those in some netbooks). To eliminate disk writes altogether use a
ram disk. If needed search the web for instructions specific to your OS.

Caution: MEVO uses a lot of CPU time, be careful when running it on a
system that is prone to overheating. The threadsleep option in the mevo.ini
file specifies how many milliseconds to sleep between running each instance
of pmars, set threads to 1 and increase threadsleep to use less CPU time.

MEVO requires a pmars-compatible simulator for running battles, for best
compatibility pmars 0.9.2 or above is recommended. For somewhat higher speed
the exmars program can be used, if using version 0.01 then the maxlen pmars
setting has to be set to 0 since it doesn't support the -l option (modified
versions of exmars included with Maezumo and OptiMax do support maxlen),
exmars does not support the permutate option for faster nano benchmarks.

MEVO requires pmarsv or equivalent for visually running or battling warriors,
this is actually the same program as pmars but compiled with display options.

The pmars source code is available from: http://www.koth.org/pmars/
It is also available from: http://www.corewar.co.uk/pmars/

For Windows the SDL-compiled binaries work well, available
from: http://www.cs.helsinki.fi/u/jpihlaja/cw/pmars-sdl/
Get pmars-server.exe, pmarsw.exe and the required DLL. Either rename
pmars-server.exe to pmars.exe and pmarsw.exe to pmarsv.exe, or edit the
mevo.ini file to specify the correct binary names. For best results put the
binaries in a path directory (C:\Windows or the default Windows directory
will work or use a separate directory added to the PATH environment var),
alternatively the binaries can be placed in the MEVO directory or put
anywhere and the mevo.ini file edited to specify the full path.

For Linux I use binaries I compiled myself, available (with source)
from: http://newton.freehostia.com/cw/pmars092N.tar.gz
Usually I use pmars92N1 renamed to pmars and pmarsv92N1 renamed to pmarsv.
The 'N2 variations are compiled with a newer compiler and are slightly
faster but require a run-time C library that isn't stock on older systems.
For best results put the binaries in a path directory (I use /usr/local/bin),
alternatively the binaries can be put in the MEVO directory (if using the
run_mevo.sh script) or put anywhere and the mevo.ini file edited to
specify the full path.

The benchmarking features requires benchmark warriors that match
the coresize being evolved for. Several popular benchmark sets are
available from: http://www.corewar.co.uk/bench.htm
Edit the mevo.ini file to specify the correct benchmark directory.

To start a new run make sure soup.dat and the save directory don't exist.
To continue a previous run make sure the mevo.ini settings match the
soup.dat file and any warriors in the save directory (including the
benchmark set, if changing benchmarks rename the save directory
to generate a new top score).

Run Mevo.exe (Windows) or run_mevo.sh (Linux) to start the program.

If a soup.dat file exists, it is loaded into the internal soup,
otherwise a random or fixed population of warriors is created.
If automatic benchmarking is enabled, the bench directory is checked
to make sure benchmark warriors exist and the save directory is scanned
to determine the current top score and the next warrior number to save.

When starting the program creates a temp directory for temp files, and
if auto-benchmarking is enabled creates a save directory for saved warriors
if it doesn't exist. Note - if the program is terminated without using Quit,
the mevolock file in the temp directory must be removed, or just remove
the entire temp directory.

Some critical error-checking is performed such as making sure the soup file
matches the INI file, the soup dimensions and warriors are of reasonable
sizes, the pmarsbin and pmarsvbin binary names contain the string "mars",
and a reasonable number of threads is specified, but most errors that
would merely result in malfunction are not checked for (in previous
evolvers the INI checking code was a source of bugs as testing requires
trying every possible option, something that just doesn't happen).
If no gross errors are detected the program displays the soup and menu.

From the menu the following options are available...
E) Evolve - starts evolution
L) List - lists the currently selected warrior to the screen
R) Run - runs the currently selected warrior in pmarsv
1-9) Battle - using the numlock key, battles the selected warriors in pmarsv
T) Test - tests the currently selected warrior to determine strength
Q) Quit - quits the program

While evolving soup warriors are battled and mutated according to the
evolving algorithm and settings. If auto-benchmarking is enabled then
messages are printed when a warrior is saved or a new top-scoring warrior
is found, or if a reinsertion operation is performed.
Press Esc to stop evolution and return to the menu.

When quitting, the soup is written to the soup.dat file, and all of the
soup warriors are saved to the soup directory. The soup warriors are saved
for convenience and to permit running external benchmark programs (especially
if not using auto-benchmarking). If the mevo.ini file, the soup.dat file and
the save directory remain intact, then re-running the program restarts a run
from where it was stopped.

Use the cursor keys to select the warrior for the other options.
When listing warriors or displaying test results, use the cursor up/down
keys to scroll and Esc to exit.

A run may take days to reach peak score, but if dead-end evolution is
noticed (for nano, the soup completely filling with a weak form, or if a
soup of papers all turn to stone) it may be desirable to terminate a run.

To archive a run for later study or restarting, save the mevo.ini file,
the soup.dat file, the save directory and optionally the top.red file
and soup warriors (the soup warriors can be recreated by running MEVO
with the mevo.ini file and soup.dat file then quitting). Alternatively
just zip up the entire work directory, which is more convenient when
restarting but requires more disk space.

To start over, remove the soup.dat file and save directory.
If the soup size was changed also remove the soup directory.


Legal/Protocol Stuff
--------------------

The MEVO program and its associated documentation are Copyright Terry Newton
under the terms of the GNU General Public License (GPL, version 3 or later).
The GPL license is at: http://www.gnu.org/licenses/gpl.html

The software is provided as-is and without warranty. The software may be
distributed as-is or modified, provided that the copyright notice remains
intact and that the source code is made available. See license for details.

If the software or documentation is modified (beyond normal configuration),
make a note of the change with attribution in the source or text so that it
may be distinguished from original versions. 

-----------------------------------------------------------
Last modified 10/3/09, for code version 10/2/09
Terry Newton (wtn90125@yahoo.com)
