Redcode Evolver Bash Script

REBS is a GNU/Linux bash script that uses pmars to evolve warriors for corewar.

REBS also runs under Windows using Cygwin.

Before attempting to run REBS, edit the script and make sure a non-graphics version of pmars is available using the command listed for the pmars variable. Specify the full path/name if pmars is not installed in a path directory. Edit the number of files and change the display variables as needed.

Now that solid state drives are more common - do not run REBS on a solid state drive! like most file-based evolvers it writes files constantly and will wear out a flash-based disk. Run from a ram disk instead and verify using iostat etc that no disk writes are taking place. Good idea even on a regular hard drive.

REBS does a lot of file reading and sometimes triggers a bash memory leak, this should now be fixed in REBS v1.4 running under bash versions 3.1 or 3.2 but when testing use a utility to monitor memory usage to ensure it doesn't clog up the system and/or terminate with a fork error. If leaking memory periodically stop and restart to reclaim the wasted buffer memory. This is more of an issue when evolving nano warriors. By default REBS uses a lot of CPU time, with v1.4 increase the sleeptime setting at the top of the script to reduce CPU usage.

Sample run...

The following screen shots show the early evolution of a soup of ~650 warriors, colored by origin...
(this was created with a previous version of REBS, now all of the warriors in a grid are plotted, status display looks a bit different in the 1.4 versions)

Unfortunately with only 15 colors there's a chance multiple species (warriors of different origins) will be colored the same, a different color mapping reveals two dominant species...

The best-performing warriors were found in the gray region, like this one...

;redcode
;name 359.red
;author rebs1.3
;parent 295.red
;origin 567.red
;generation 63
;assert 1
add.a  {  279 , >  111
spl.x  #  431 , $   -9
mov.i  #  465 , }    2
mov.i  #  465 , }    3
spl.f  <   43 , }  670
spl.f  #   22 , @   94
mov.f  <  230 , #   -7
mov.i  $  439 , }    8
mov.i  @  439 , }   -2
mov.a  #  192 , }    6
jmp.i  {   89 , @  377
dat.a  @  590 , {  -10
dat.a  @  590 , {  -10
end 1

...which scores a fairly low (~114 against the Franz test set) at this very early stage of development. This is a soup I'm running on my 133mhz Win95/Cygwin machine so results are slow in coming. My 1.4ghz AMD evolves hundreds of generations in an overnight run, sometimes producing warriors that score in the 130-150 range as of version 1.3b. Luck plays a huge role, as does the evolution parameters, in how strong a soup will grow. Unfortunately this means the results of a single run or even a few runs often doesn't mean anything but sometimes does, making parameter selection tricky. Another phenomena to watch out for is an unchanging environment may never produce particularly strong code, not enough challenge. Periodically altering the change rates and other variables may help encourage new strategies.

REBS Ramblings...

First code was posted 3/9/05, first relatively stable version was 1.0f posted 3/12/05. Page down for the most recent postings, out-of-date stuff is periodically purged when too much accumulates.

3/20/05 - Updated rebs.txt to version 1.1, added an option for circle topology and now writes parent, origin and generation count into the comments. Ok to use with soups from 1.0, adds the new comments upon evolving. So far the circle topology is working well for maintaining diversity long enough to allow weaker but more intelligent designs (like papers) to work themselves out before being exposed to other more direct forms (like stones).

3/21/05 - Added the evol_rd script for evolving on ramdisk, hopefully it's general enough now to adapt. I've been running the new code with circular topology for a couple of days now, no super-warriors have appeared but it seems to work better than plain random selection, at least it keeps one form from immediately taking over the soup. In the end though the maximum strength warriors attain in the runs I've made is about the same (~140 Franz) regardless of topology, so something else seems to be limiting things, I'd like to see at least the 160's. When I increased the change rates replicators appeared after only 30 or so generations but after 200+ generations nothing stronger than about 105 was in the soup and it didn't appear to be improving. I'm running an experiment with lower change rates to see if that makes a difference. I can tell things are on a slow track, at ~80 generations there were only a couple forms trying to replicate and doing a really bad job at it. There are many other things that might limit strength (or more accurately affect the odds of strong code appearing) including population size, instruction mix and lack of precision battles. Sometimes mutations happen that cause strong code to appear despite less than optimum parameters, only after many runs can trends be deduced and then not exactly.

3/23/05 - The slow change-rate run never went anywhere, back to the original chance numbers. Instead I'm trying other things for version 1.2... new vars datatweekchance and endtweekchance control how often an increment or decrement occur rather than replacing with a random number. Now has double-fixed battles which seems to produce more accurate battle results. Ring topology was interesting, added grid topology to the selections. Actually it's a skewed cylinder with wrap on the sides but no wrap from the top to bottom, this was the easiest to code. An xsize variable controls how many warriors are on each line. This number determines how fast code spreads by how much room there is for the strain to squeeze by competing forms. Eventually I'd like to program an inspection tool for browsing, battling and benchmarking the soup, hopefully something native but I've got a lot more to learn about Linux programming before I can tackle anything fancy like that. An evolver or a benchmarker is relatively easy... but making a highlight bar move around a dense display of warriors with list, run, bench and battle options for all neighbors is another matter, might have to invoke QBasic.

3/24/05 - 1.2a - fixed a couple of minor bugs.. added another condition to prevent warriors from growing too big under rare conditions, origin status display (O:number) now displays all the digits when more than 1000 warriors. This version has somewhat higher change rates, particularly in the data fields, and xsize is set to 3, an odd topology resembing a triangular spiral tower if visualized but it helps avoid early saturation while allowing some mixing.

3/27/05 - 1.2b - changed the way the random number generator (RNG) is seeded, now it prompts. The problem with most RNG's is they aren't really random, just an extremely long sequence of numbers that appears random. Because of this, the outcome is predetermined by the exact position in the RNG's sequence (the seed), the exact state of the variables and evolution code, and the state of the soup. Previously I was using the output of date to seed the RNG but that leaves huge regions unexplored, besides requiring a GNU date command, a potential compatibility problem for Windows since dos's date might get picked up instead. The present solution is don't seed at all (thus intruducing at least some uncertanity when a script is stopped then restarted) unless a key is pressed within 2 seconds of startup, then it prompts for the seed number (up to 9 digits on my system). I figure if anything is going to predetermine the outcome then let it be the user's imagination.

Version 1.2b also has somewhat different parms, the high change rates in 1.2a seemed to be too much, backed off, increased the number of warriors to 1000 and increased rounds to 250 double-fixed battles in an attempt to generate stronger code. The latest versions had only been reaching a max score of around 125, worse than before when the change rates were in the 200-500 range with 200 random battles with random or circle topology. Now the change rates are in the 400-500 range, but it may take days to see how the new parms perform due to the higher rounds and warriors... typically 200 generations or more are needed before one can tell where a soup is going and judging from past experience, sometimes thousands of generations are needed to produce warriors capable of placing a hill.

3/29/05 - turns out read -t n fails on some versions of bash (like the Cygwin 1.1/bash 2.04 I have under Win95), tired of trying to solve the RNG seed issue in a satisfactory way so for REBS 1.3 removed the seed code altogether, in the grand scheme of things it probably doesn't matter unless the random numbers printed on startup are the same every time, in which case system-specific RNG seed code can be put in another script.

REBS 1.3 now has a soup display! Uses columns to display long and narrow grids, not sure how system dependent the ANSI codes are but sure looks neat and gives a much better feel for what's going on in the soup. Since it would be difficult to add any kind of interactive interface to REBS itself I'm contemplating making a soup exploration program based on the same display but with cursor keys to select a warrior and keys for running in pmarsv and benchmarking.

3/30/05 - the big crash.... for about 10 minutes on 3/29 a broken 1.3 was posted (forgot a 10# in the colorizing code), got the fix uploaded and went to work and that was the last time my 900 mhz machine booted. Might be terminal, the processor fan clogged and likely the cpu got too hot. The good news is it looks like I'll be getting one of those speedy GHZ motherboards I keep hearing about and once fixed I'll be able to waste ~3x the cpu cycles. Until then I'm stuck testing the current 1.3 on my 133mhz Win95/Cygwin platform. So far it's working slowly but fine, presently running a soup of 650 warriors arranged in a 65 by 10 grid (warriors=650, xsize=65, ylines=10, statline=13, rounds=50, enablefixed=0) to get a screenshot.

4/2/05 - REBS 1.3a was developed on my 133mhz Cygwin machine and has the rounds set low to make it bearable, display is set to a single-column 65 by 10 grid (same parms used for the screenshot). Added an option to display the existing soup before evolving (making grabbing screenshots much easier). This may be the beginnings of an interactive user interface... my previous thinking was to make that a separate exploration program but it would make more sense if one script did it all, the display code is already there. Today I installed new guts in my fast machine, now it's a 1.75 ghz AMD Sempron 2500 running at 1.4 ghz with the motherboard defaults, barely gets warm.

4/4/05 - The new system is very fast, I ran REBS 1.3a for awhile to see what happens (this time) with the fast low-rounds parms, eventually warriors scoring ~125 appeared. Along the way I added a colormethod variable and a condition to color the warriors by origin or by length, to keep a color display after the soup saturates with one species.

4/6/05 - REBS 1.3b is set up to color by length. I'm noticing that high rounds and double-fixed battles don't necessarily produce stronger code, 50 rounds random works about as good as 400 or more fixed rounds and evolve warriors at a much faster rate. Or it's fooling me again... conclusions are hard to make with only a couple runs. I tried less bias on the SPL and MOV instructions but the results were not as strong over a couple of runs, for whatever it's worth.

4/7/05 - Trying a larger soup (~1300 warriors) with lower change rates, also replaced the 3 in the by-species colorizing code with $fndigits so it would catch all of the origin number when more than 1000 files. The generation readout in the status line is jumping back and forth in the status line, gotta fix that too... stupid bug. New version 1.3c uploaded.

4/8/05 - I finally fixed the roundoff problems causing REBS to not generate all of the specified files, new version 1.3d uploaded. Also should select all data elements when evolving 8000-sized warriors. I resisted this because I didn't want to complicate things but the missing warriors were getting to me, ended up being easy and very low impact. 1.3d is set up to generate 1617 files (21x77) and may have the change rate set too low (or I'm not being patient enough), best results scored in the 90-100 range. Trying again with the rates set to 300-500. [nothing good became of it]

4/10/05 - version 1.3e had change rates in the 200-500 range, with greater odds of duplicate lines. Rounds set to 50, trying double fixed again. So far these variables have produced slightly stronger code, max scores in the 140 range. Version 1.3f adds a couple of command line options for use when redirecting the screen output to an ANSI "movie" file which can be played back at high speed using the cat command. This almost worked with the previous rebs but stopping and starting produced glitches, bin-editing a 20 meg file to remove the glitches was not fun so added the -redir option to suppress extra text and -append option to suppress extra text and the frame/soup redraw. The -redir parm isn't strictly necessary when starting a redirected recording (the extra text gets cleared anyway) but in the future may be necessary to suppress any other interface elements that may get added - like an interactive interface I can use to cursor around the soup and examine warriors, manually calculating file numbers is getting old.

4/14/05 - I figured out how to partition the rest of my new 80 gig drive and now I don't have to worry about wasting gigs on huge ANSI files and such, but the raw output is way too large to post. I found code on the net for making animated gifs (ansi2gif by Vince Weaver) and modified it to skip a large number of characters between frames to make reasonably-sized animated graphics files, like this recording of a run (525k) which produced this replicator...

;redcode
;name 1586.red
;author rebs1.3f2
;parent 1585.red
;origin 0898.red
;generation 187
;assert 1
mov.f  @    8 , }   64
mov.ab $  421 , @  -10
spl.ba #  422 , }  568
mov.i  >   -4 , }   -2
mov.i  @   -5 , {  239
jmp.i  }   -3 , >    3
djn.i  {   -9 , <    8
sne.ab *  232 , @    4
mod.x  {   -5 , *    5
spl.i  }  639 , @    7
spl.b  *  -11 , $   -8
end 1

An interesting feature of this specimen is it replicates in 800 and 8000 sized cores, not all that strong though.

5/20/05 - after a long run of rebs 1.3f5...

The strongest members I found were 1158.red, 1315.red and 1392.red, all similar. These score ~155 against the Franz "tiny" warriors, about ~135 against the contents of the SF evolved hill, and a not so great ~110 against the SF tiny hill warriors. Rebs 1.3f5 has lower change rates and a slightly different instruction mix compared to Rebs 1.3f, and is set to 50 rounds random battles rather than double-fixed battles. The lower change rate probably helps but luck and timing seems to be major determining factors. When the soup is checked makes a big difference, at around 7K generations the top scores were ~120 against the SF evolved, at around 9200 generations I was getting ~125-130, at ~9600 generations I picked out the above warriors, at ~9900 generations the top scores are ~125 again and the code has changed significantly (but essentially does the same thing just not as well against benchmarks). The up and down nature of the scores makes sense for a closed system, there is no evolutionary pressure to do anything except survive. After 9900 generations and noticing declining performance I lowered the size change chance and the mode/data chances (rev 1.3f6), continuing evolution to see what effect these changes have on the population.

5/22/05 - I ran this soup to about 10600 generations, there was hope around 10400 generations but after that scores dropped again. Here's a comparison of five top-scoring warriors taken at different times...

                |                |                |;name 1547.red  |
                |;name 1207.red  |;name 1392.red  |;gen 9953       |
;name 1385.red  |;gen 9206       |;gen 9599       |seq.ba <227,@ -5|
;gen 7668       |seq.f  {  1,*535|mov.b  #216,<  1|seq.x  {775,@ -5|;name 0515.red
dat.a  < -9,#388|jmp.x  @700,<652|spl.a  }  0,< -8|mod.f  # -1,$307|;gen 10483
dat.ab >667,{711|dat.x  }695,#  3|dat.f  #603,#  2|dat.ba > -6,{  8|spl.f  # -2,>280
spl.i  #722,> -7|spl.i  #675,> -8|spl.ab #704,$  2|spl.i  #742,}529|spl.x  #732,>271
spl.i  # -9,{ -1|spl.i  #282,{ -1|spl.i  # 57,{ -1|spl.i  #  8,{ -1|spl.i  # -6,{ -1
mov.i  #-10,}  5|mov.i  # -8,}  6|mov.i  # -9,}  6|mov.i  # -8,}  6|mov.i  # -8,}  6
mov.i  }  4,{ -3|mov.i  }  5,{ -3|mov.i  }  5,{ -3|mov.i  }  5,{ -3|mov.i  }  5,{ -3
mov.i  <  6,{  2|mov.i  {  6,{  2|mov.i  <  6,{  2|mov.i  <  6,{  2|mov.i  <  5,{  2
mov.i  $ -6,< -5|mov.i  $  2,<  3|mov.i  $  2,<  3|mov.i  $  2,<  3|mov.i  $  2,<  3
djn.ab @450,}  1|djn.f  @444,{256|djn.i  @443,{258|djn.i  @440,{140|djn.i  @433,<157
mod.f  * 79,<627|dat.i  <688,<354|dat.i  @693,<355|dat.i  }515,< 99|dat.i  <296,$614
dat.f  }532,{185|dat.a  # 10,$777|dat.i  > 19,*780|dat.x  * 85,$776|mov.i  @  8,$778
spl.x  @482,>627|spl.i  { -9,<606|slt.a  *522,<-10|spl.b  >  8,# -3|mov.b  @557,$  1
end 2           |end 3           |end 3           |jmp.i  <  2,<  1|djn.i  }  7,# -9
                |                |                |spl.i  >  8,>272|mov.i  #508,{ -5
                |                |                |dat.ba } -5,<  3|jmp.i  #508,{ -5
                |                |                |dat.f  {-10,}605|jmn.f  $509,{ -7
                |                |                |end 4           |spl.x  <323,> -2
                |                |                |                |end 1
scores=151,122  |scores=146,132  |scores=156,133  |scores=142,126  |scores=141,131

Things that stayed the same are colored green, changes are colored red and tweeked data fields (within 10) are colored blue. The green areas show the parts that apparently matter to functionality, the red areas are likely code-garbage.

1/17/09 - I've been using REBS to evolve nano-size warriors for a coresize of 80 and a maximum length of 5 instructions. With nano parms REBS can perform hundreds of thousands or even millions of iterations in an overnight run, or hundreds to thousands of generations of the soup, which led to discovering a memory leak I never noticed before... every second it loses a few kilobytes, going through several hundred megabytes over the course of a few hours. When available user memory is exhausted it issues a fork error and stops, returning all the memory back to the system. Stopping the program normally by deleting DeleteMe also returns memory, some kind of internal buffer that accumulates cruft from something, trying to figure out what. In the mean time I just stop it every now and then, need to do that anyway to check the soup, or simply let it run out of memory and think of it as a feature to prevent overcooking the soup (not - got to at least figure out what's leaking).

The /dev/ram15 ramdisk method doesn't work on all systems as the size of the ramdisk is fixed and sometimes (like on my Eee PC 701SD) not big enough. An alternate method is to use ramfs which permits specifying a maximum size and only uses memory actually consumed by files. However free space is always 0 so causes issues with some GUI's like Gnome. KDE complains when copying files to a ramfs ramdrive but permits clicking "ignore" to continue. Here's the ramdisk script I use on my 701SD...

#!/bin/bash
if [ ! -e ~/rd/work ];then
 echo "Creating 25 meg (max) ramdisk with ~/rd/work directory"
 if [ ! -e ~/rd ];then
  mkdir ~/rd
 fi
 sudo mount -t ramfs none ~/rd -o maxsize=25000 && sudo mkdir ~/rd/work
 if [ -e ~/rd/work ];then
  sudo chmod 777 ~/rd/work
 else
  echo "Operation failed"
 fi
else
 echo "~/rd/work directory already exists"
fi

As currently posted REBS runs flat out consuming close to 100% of the CPU time. Typically that's what I want but sometimes (especially with nano warriors) it's useful to slow it down. Might also help with newer PC's that overheat with 100% CPU usage (especially laptops with more specs than cooling), or make the system more responsive to use while evolving. At the beginning of the script add a setting for sleeptime...

.....
version="1.3f"
sleeptime=.1     # time in seconds to sleep between iterations
# pmars configuration....
.....

...and towards the end of the script insert a SLEEP command between the status echo and plot call...

.....
   echo -n " O:${origin:0:$fndigits} L:${linecount:0:3}G:$generation   "
   sleep $sleeptime 
   if [ $enableplot -ne 0 ]; then
.....

[this is already present in the new v1.4 version of REBS]

1/18/09 - I think I'm honing in on the mem-leak bug, illustrated by this short script...

#!/bin/bash
# memory leak test - bash 3.1.17
function testread {
 read -r line
}
echo "test" > test.fil
while [ 1 ]; do
 testread < test.fil
done

...when run it eats memory rapidly, about a megabyte a second on my 701SD with bash 3.1.17, however it does not leak on my Ubuntu system running bash 3.2.39 so the leak there is something else, still losing about a megabyte every 2 minutes while evolving nano warriors. This varient does trigger a leak under Ubuntu...

#!/bin/bash
# mem leak test - bash 3.2.39
function testread {
 read -r line
}
echo "test test" > test.fil
while [ 1 ]; do
 testread < test.fil
done

The -r option simply suppresses interpreting backspace as an escape char, same results with just plain read line. Replacing the space in "test test" with x fixes the leak. Ouch. This varient doesn't leak...

#!/bin/bash
# mem leak test - bash 3.2.39 workaround
function testread {
 read -r word1 word2 word3 word4 word5 word6 word7 word8
 line="$word1 $word2 $word3 $word4 $word5 $word6 $word7 $word8"
}
echo "test test" > test.fil
while [ 1 ]; do
 testread < test.fil
done

Hmm... unfortunately it destroys the formatting of the original line, so that won't work unless other stuff is also modified, particularly the parsing functions that depend on the position of a string in the line.

1/19/09 - fixed the memory leak I think, at least with bash versions 3.1 and 3.2. Took quite a bit of code change so REBS is now v1.4 (and experimental, might need more tweaks). The warrior format changed slightly, should still be compatible with older REBS versions but haven't tested yet. The new REBS (version 1.4exp1-nano) is configured for nano warriors, for tiny warriors copy the settings from v1.3. I was suprised the fix worked on bash 3.1 too, the trick seems to be to supply more read variable targets than there are word in the input line. Odd, but I'll take it. Now I can get back to the fun stuff - trying to evolve competitive nano warriors. So far not having much luck but noticed most nano warriors use only SPL MOV and DJN with the occasional DAT and other instructions, and none in my test sets use P-space. So weighted the instruction set to heavily favor SPL and MOV and moderately favor DJN, that seems to help but still not producing all that strong of warriors. I think the problem might be that warriors that score well against members of its own kind don't score particularly well against other warriors, and might suppress the generation of replicators which tend to tie when playing against similar replicators - as soon as a scanner or lucky bomber comes along the paper form is consumed. Contemplating ways to counter this effect... one way is through manual intervention - selecting warriors that show promise and evolving only them, or perhaps even introducing "alien" warriors into the soup then watching it carefully to keep them from simply killing off all the other soup warriors. I don't really want to re-evolve existing warriors since once a particular form has been optimized it generally gets worse with further evolution - but that's OK for the purpose of training the other soup warriors to learn how to beat them. The new v1.4 mod makes this a bit easier since now spacing isn't important in the redcode so long as there are no labels or constants and there is at least one space between each element. Alien warriors must begin with 7 comments in the normal REBS format with an end line address and be in "unix" text format if using Linux.

1/21/09 - new version 1.4exp3-nano - modified the fixdata function to help resist invalid numbers, missing end lines etc, not quite as fragile now. REBS tends towards warriors of a single seed origin, partially because of statistics and partially because stronger forms tend to swamp weaker forms. Even though the soup might contain a lot of variation the display always becomes boring using the color by origin method. To better see what's really going on I added a new warrior comment for species which starts out the same as the origin, if the base instructions or starting location (end line) changes the species is set to the current warrior name. A new colormethod setting permits colorizing the soup by species so new forms that arise during the course of evolution can be seen in the display.

2/6/09 - new version 1.4a0 - Added a new parameter to specify the minimum size of randomly generated warriors but not sure how effective it is, defaults to 1 like previous versions. Modified grabscores so it doesn't require single-word author and name (more like v1.3 now) and added more dummy words to the readinputline sub in preparation to possibly add periodic benchmark testing - I feel like on long runs I'm missing out on strong code that may arise then go away. This would open up the possibility of periodically reintroducing strong code back into the soup, providing a way to gently guide the evolution process without too much forcing like would occur if the warriors were evaluated directly against test warriors - that usually results in warriors that are strong against a test set but nothing else. Went through the code and tweaked up enough to drop the "experimental" label (I hope, but good enough for an "a"). Among changes, warriors and warrior numbers now use a random multiplier of 1000 for better accuracy, had noticed when evolving with a large soup of 5250 warriors (150x35 grid) the last 7 soup positions were never chosen, probably was doing the same with coresize 8000 warriors but worse had a bug where it occasionally made a warrior that was too big, fixed that. The tar.gz archive now contains versions of REBS configured for nano, tiny and standard warriors. Don't expect much from the size 8000 version, parms are copied from the 800 version. I never had much luck evolving standard size warriors, the search space is vast and with all those instructions human coders practically always do better, hard to get a "Wilkies" score over 80 with a simplistic evolver like REBS. Nanos are another story!

I got a few REBS warriors (barely) on the SAL nano hill, here are a couple...

;redcode-nano
;name 0614.red
;author Terry Newton
;strategy Evolved by rebs1.4exp3-nano
;strategy Koen090112(20) score = 144.9
;strategy nanobm07 score = 141.1
;parent 0537.red
;origin 0020.red
;generation 3524
;assert CORESIZE == 80
spl.ab # 72   , > 9   
mov.i  { 0    , < 40  
mov.i  @ 25   , { -2  
mov.i  < 38   , { -1  
djn.i  $ -2   , $ 76  
end 0
;species 1285.red

Opponent         Scores    Results    Performance of 0614.red
--------         ------    -------    ---------=---------=---------=---------=
Nano'Powa        331 397   125 103 22 *********************
Black Sun III    399 321   97 123 30  *****************
8c09fc1a-479925  336 405   132 109 9  *********************
Chiki Chiki      333 375   111 97 42  ********************
Cosmic Horror    417 291   83 125 42  ***************
Dodecadence      369 339   99 109 42  ******************
eerie glow       336 372   110 98 42  *******************
flight           371 329   93 107 50  *****************
Foggy Maus (bet  355 385   125 115 10 ********************
glowing embers   349 364   109 104 37 *******************
hemlock          338 341   90 89 71   ******************
a slice of moon  403 340   111 132 7  ******************
c82f15b5-85011f  385 355   115 125 10 ******************
Pacler Deux      391 304   83 112 55  ****************
Red Moon         403 337   109 131 10 *****************
ripples in spac  330 369   106 93 51  *******************
ripples 22       267 444   135 76 39  ***********************
the spiders cre  345 354   101 98 51  ******************
Staphylococcus   326 410   132 104 14 *********************
White Moon       332 413   136 109 5  **********************
1046.red         302 434   140 96 14  ***********************
0614.red         345 399   131 113 6  *********************
Left Alone       370 358   112 116 22 *******************
Muddy Mouse (RB  365 377   123 119 8  ********************
--------         ------    -------    ---------=---------=---------=---------=
Adjusted Score: 146.8 

;redcode-nano
;name 1046.red
;author Terry Newton
;strategy Evolved by rebs1.4exp2-nano
;strategy Koen090112(20) score = 143.8
;strategy Nanobm07 score = 142.5
;parent 0970.red
;origin 0179.red       
;generation 739
;assert CORESIZE == 80
spl.b  # 0    , < 50  
mov.i  < -1   , { 71  
mov.i  $ 18   , < -2  
djn.i  $ -2   , { 58  
spl.f  } 47   , { 18  
end 0

Opponent         Scores    Results    Performance of 1046.red
--------         ------    -------    ---------=---------=---------=---------=
Nano'Powa        392 347   112 127 11 ******************
Black Sun III    359 356   107 108 35 ******************
8c09fc1a-479925  453 288   93 148 9   ***************
Chiki Chiki      466 262   80 148 22  *************
Cosmic Horror    395 308   87 116 47  ****************
Dodecadence      390 345   110 125 15 ******************
eerie glow       294 429   134 89 27  **********************
flight           342 387   122 107 21 ********************
Foggy Maus (bet  379 364   119 124 7  *******************
glowing embers   262 442   132 72 46  ***********************
hemlock          285 405   115 75 60  *********************
a slice of moon  334 412   136 110 4  *********************
c82f15b5-85011f  346 403   134 115 1  *********************
Pacler Deux      371 362   115 118 17 *******************
Red Moon         373 373   123 123 4  *******************
ripples in spac  430 304   96 138 16  ****************
ripples 22       443 293   93 143 14  ***************
the spiders cre  339 393   125 107 18 ********************
Staphylococcus   371 368   119 120 11 *******************
White Moon       391 349   113 127 10 ******************
1046.red         359 380   123 116 11 ********************
0614.red         359 380   123 116 11 ********************
Left Alone       398 344   112 130 8  ******************
Muddy Mouse (RB  407 335   109 133 8  *****************
--------         ------    -------    ---------=---------=---------=---------=
Adjusted Score: 143.8 

As of today 0614.red is in 38th place with a score of 142.8 and 1046.red is in 46th place with a score of 141.5. We'll see how long that lasts. Another one, 0413.red, is hanging on in 50th place, I don't expect it to last long. 0614.red is from the same soup as 0413.red, just chosen using a more optimised test set. These warriors have been edited to include benchmark scores in the comments, the "nanobm07" score refers to the score against the warriors in nanobm07.zip (from http://corewar.co.uk/nano.htm), the "Koen090112(20)" score is the score against the top 20 warriors from the Koenigstuhl nano hill which is a somewhat better predictor of performance. The test sets used in the performance charts above are a combination of this plus my 2 nano warriors plus 2 other warriors from the SAL nano hill, this set is slightly more accurate but most of the hill contents is not published so it's a guessing game.

The big question I'd like to answer... does all the fancy stuff like crossover etc really make an evolver better? Or does the increased performance come from other factors such as a larger population size, things that avoid settling into a "local maximum", better weighting of instructions, modifiers, modes and data, and other simple parameters that have nothing to do with esoteric techniques. In a random evolver like REBS I don't know how crossover could be implemented at all, cross with what? there'd have to be some tag which indicates an "attractive" warrior to combine with or the effort would probably be futile. I think the best technique for strengthening code is the method used by Barkley Vowk (bvowk), using "chain" tables based on existing warrior code to modify the odds of what the next instruction should be, at least when creating the initial population of warriors. Maybe crossover does in fact work better, but I'd be very interested in testing the theory with all the other parameters equalized. One possibility is a comment to track how many battles a warrior survives, then when a warrior wins a battle and gets to multiply it can look in its immediate vicinity for the "strongest" warrior to cross with. Something like that could be turned on and off to see if crossover really makes a difference.

2/7/09 - here is a more detailed algorithm showing how warrior crossover might work...

DO
 Pick a warrior at random
 Randomly select one of 8 neighbors
 (wrap on the sides but not the top and bottom, like a cylinder)
 If either warrior does not exist create a random warrior
 Battle the warriors and obtain scores
 Increment the win number of the warrior that won
 Examine the surrounding warriors and choose a warrior with the
  highest win number, excluding the warrior that lost and warriors
  not of the same origin (a tag maintained since initial creation)
  (or perhaps the same species, a tag changed whenever the instruction
   sequence changes but that might be too limiting)
 Switch = random 0 or 1
 Skip header comments of both winner and mate, write headers to loser
 DO
  Read one line from both the winner and from the mate
  If Switch = 0 evolve the winner's line to the loser
  If Switch = 1 evolve the mate's line to loser
  If random < switchrate, invert Switch (if 1 make 0 else make 1)
 UNTIL one or the other warriors runs out of instruction lines
 Evolve the end line (from winner or mate depending on Switch)
 Write the end tags (wins=0, change species if any instructions changed)
UNTIL the evolver is stopped

...but don't expect any such thing from REBS, which will likely always remain a simple mutation-only evolver. One reason is because it's a script that uses redirection to feed in a warrior and output an evolved warrior, and only one file can be redirected at a time. That pretty much disallows crossover unless each warrior was read into an array and I'm not getting into all that. Another reason is also because it's a script - bash can do cool things but a general-purpose programming language it is not. REBS began almost as a joke to see if it was possible to create an evolver in a scripting language, I learned a lot about bash and REBS has become my reference script when I can't remember how to do something, but I can't imagine doing anything beyond a trivial algorithm using just bash. Rather, REBS was an experiment to see how trivial an evolver could be.

2/9/09 - Got up this morning and discovered a particularly strong soup of nanos had evolved on my 701SD, previously I had weakened this soup by playing with the parms so went back to REBS 1.4a0 with stock parms, picked out a few warriors that scored the highest using my Koen090112(20) test set then picked 0535.red to mail to the SAL Nano Hill... 3rd place! Cool, that's progress. As a bonus it boosted 0614.red to 33rd place. I'm going to let that one sit for awhile before I reveal the code, but I think it's evidence that a simple mutation-only evolver can produce strong code without using esoteric techniques, at least for nano-size warriors.

2/10/09 - RedMixer lives. It's very similar to REBS but is written in QBasic and implements the crossover idea. The crossover operations can work on an item-by-item basis as well as line-by-line switching, and in addition to tracking wins also records average score. Now will try to see if crossover really works.