SEVO - a small corewar evolver ============================== This is a small Blassic program that evolves warriors for the game of corewar. Although it is less than 2K code, it has features similar to bigger evolvers.. * Grid-based soup with adjacent-warrior battles * Separate evolution of instruction, modifier, address modes and data fields * Separate operations for randomizing and incrementing/decrementing data * Line duplicate, delete and swap operations * Individually adjustable odds for each operation * Every element can mutate, new warriors can have no change or many changes * Adjustable weighting for instruction and data selection * Can stop and restart at any time to monitor progress Of course being small imposes a few limits and quirks... * No record of generations or other comments in the warriors * No end line so warriors always start at the first instruction * Warriors must remain in a strict format with no extra lines * Must halt the evolver cleanly or corruption may result * Moderately file-intensive, best to run it on a ram disk * Line delete is not performed on the first two lines * Line dup is not performed on the last two lines * Does not perform random line insertion The evolving algorithm is very simple... If 0.red doesn't exist then create a new random soup of warriors Repeat until stopped... Choose two adjacent soup warriors Battle the two warriors using the pmars program If the 1st warrior wins or ties against the 2nd warrior then winner = 1st warrior, loser = 2nd warrior Otherwise winner = 2nd warrior, loser = 1st warrior Copy the winner over the loser while making random changes Here's the SEVO program... ----- sevo.bas --- 1712 bytes --- Fri 16 Dec 2011 08:21:06 AM CST ---------- #!/usr/local/bin/blassic p$="pmars -bkl 5 -s 80 -p 80 -c 800 -r 70 ":n=2000:d=50:l=5:c=41 i$="mov.spl.djn.dat.jmz.seq.sne.add.jmp.":k=9 m$="a b f i x abba":t=7:n$="$#@<>*{}":q=8:randomize shell "dir /b 0.red>_":cls:open "_" for input as #3:if eof(3) then gosub i close #3:while inkey$="":x=int(rnd*n):y=x:while y=x or y<0 or y>=n y=x+int(rnd*3-1)+(int(rnd*3-1)*d):wend:x$=str$(x)+".red":y$=str$(y)+".red" shell p$+x$+" "+y$+">_":open "_" for input as #3:input #3,z$:a=val(z$) input #3,z$:b=val(z$):close #3:s$=x$:d$=y$:if a0 then if not eof(1) then line input #1,z$ if rnd<.01 and i_" to "ls -1 0.red>_". The "_" file is a temp file used to hold the directory list and pmars scores, doesn't bother to remove. The program produces a fair amount of file activity, nothing too crazy but with most OS's will cause a write every second or so. Do not run the program on a cheap solid-state disk or it can wear it out. Should be fine with modern hard drives but if running for long periods of time best to run it from a ram disk - there are various ways to make a ram disk, search for it. The sevo.bas program can be run from a command line using: blassic sevo.bas Under Linux, can be run directly - make sure sevo.bas is in "unix" line-end format (use flip -u sevo.bas), set properties to executable, then can double-click and select run in terminal (don't select just run or you'll have to kill the task to stop it, and that might corrupt the soup). If 0.red does not exist a soup of 2000 warriors (or whatever n is set to) named 0.red to 1999.red will be created before starting evolution. The user interface is very simple - a blank screen. Press any key to stop. To monitor progress I wrote a program that dumps a map of the soup, benchmarks warriors and lists the stronger specimens... ----- dumpsevo.bas --- 5060 bytes --- Sun 18 Dec 2011 12:58:06 PM CST ------ #!/usr/local/bin/blassic 'This Blassic program is for use with the SEVO evolver program. 'Outputs a file containing a symbolic representation of the soup and a 'sample warrior of each type, as determined by a hash of the first few 'characters of each line of each warrior (default ins.mod). If no bench set 'is specified then randomly selects the sample, otherwise selects the 'highest-scoring warrior for each type, followed by the top-scoring warrior. 'Finally outputs a list of warriors for each hash (disable if not needed). usewin=0 'set to 1 if running under windows n=2000:d=50:f$="soup.txt" benchbase$="/usr/local/share/cw/" 'location of bench sets (use \ if win) bench$="nanob2" 'the following 2 lines must match the warriors and benchmark... pmars$="pmars -bkl 5 -d 5 -s 80 -p 80 -c 800 -P" rounds=142 '-r parm or 142 if nano -P chars$=".:?~@#$%^&*-=+OX" 'characters used for the soup display hashwidth=6 'how much of each warrior line is used to compute the hash nchars=len(chars$) 'comment next 4 lines for no entry with defaults 'print "number of warriors (n) "; : input n 'print "width (d) "; : input d 'print "output file "; : input f$ 'print "bench set (none to skip) "; : input bench$ print "processing..." dim hashes(n,2),wlist(n,n),wnum(n,2) if bench$="" then goto skipbenchlist if usewin then ls$="dir /b ":ps$="\" else ls$="ls -1 ":ps$="/" shell ls$+benchbase$+bench$+ps$+"*.red > bench.lst" label skipbenchlist: nwlist=0:topscore=-1:topwar$="":lc=0:accscore=0:randomize open f$ for output as #2 for i=0 to n-1 w$=str$(i)+".red" open w$ for input as #1 hash=0:linenumber=0 while not eof(1) line input #1,a$:linenumber=linenumber+1 if left$(a$,1)<>";" then gosub addhash wend close #1 chrhash=(hash mod nchars)+1 print #2,mid$(chars$,chrhash,1); lc=lc+1 : if lc>=d then print #2,"":lc=0 hashes(i+1,1)=hash:hashes(i+1,2)=chrhash next i print #2,"" for i=0 to n-1 hash=hashes(i+1,1):skip=0 if i<1 then goto skiphashcheck for j=1 to nwlist if hash<>wnum(j,1) or skip then goto nextlist wnum(j,2)=wnum(j,2)+1 wlist(j,wnum(j,2))=i:skip=1 label nextlist: next j label skiphashcheck: if skip then goto alreadyadded nwlist=nwlist+1:wnum(nwlist,1)=hash wnum(nwlist,2)=1:wlist(nwlist,1)=i label alreadyadded: next i print print "Detected ";nwlist;" types out of ";n;" warriors" print #2,"Detected ";nwlist;" types out of ";n;" warriors" if bench$<>"" then print "Using ";bench$;" benchmark" if bench$<>"" then print #2,"Using ";bench$;" benchmark" print #2,"" for j=1 to nwlist members=wnum(j,2) if bench$="" then i=wlist(j,int(rnd*members)+1):goto skipbench print "Testing ";members;" members with hash=";wnum(j,1) 'for nano list the instructions.. z=instr(pmars$,"-s 80 "):if z=0 then goto dontlistinstructions w$=str$(wlist(j,1))+".red" open w$ for input as #5:line input #5,a$ print "|"; while not eof(5) line input #5,a$:print left$(a$,6);"|"; wend:close #5:print label dontlistinstructions: topmscore=-1:i=-1 for k=1 to members warnum=wlist(j,k):war$=str$(warnum)+".red" gosub benchmarkwar print "Warrior ";war$;" scores ";left$(str$(score)+" ",6) if score>topmscore then topmscore=score:i=warnum if score>topscore then topscore=score:topwar$=war$ accscore=accscore+score next k label skipbench: w$=str$(i)+".red" print #2,"Warrior ";w$; if bench$<>"" then print #2, " score=";left$(str$(topmscore)+" ",6); print #2," symbol ";mid$(chars$,hashes(i+1,2),1); print #2," (";members; if members > 1 then print #2," members)" else print #2," member)" open w$ for input as #1 while not eof(1):line input #1,a$:print #2,a$:wend close #1:print #2,"" next j if bench$="" then goto skiptopscore print "Average score = ";left$(str$(accscore/n)+" ",6) print "Top-scoring warrior is ";topwar$; print " score=";left$(str$(topscore)+" ",6) print #2,"Average score = ";left$(str$(accscore/n)+" ",6) print #2,"Top-scoring warrior is ";topwar$; print #2," score=";left$(str$(topscore)+" ",6) open topwar$ for input as #1 while not eof(1) line input #1,a$:print #2,a$:print a$ wend close #1:print #2,"" label skiptopscore: 'uncomment next line to skip hash list... 'goto skiphashlist print #2,"Hash list..." for j=1 to nwlist a$=str$(wnum(j,1))+":":llen=len(a$) print #2,a$; for k=1 to wnum(j,2) a$=str$(wlist(j,k))+" ":ilen=len(a$) if llen+ilen>79 then print #2,"":print #2," ";:llen=1 print #2,a$;:llen=llen+ilen next k print #2,"" next j label skiphashlist: close #2 end label addhash: linehash=0 for z=1 to hashwidth linehash=linehash+asc(mid$(a$,z,1))*z next z linehash=linehash*linenumber hash=hash+linehash return label benchmarkwar: nitems=0:score=0 open "bench.lst" for input as #3 while not eof(3) line input #3, opp$ if usewin then opp$=benchbase$+bench$+ps$+opp$ shell pmars$+" "+war$+" "+opp$+" > _scores.tmp" open "_scores.tmp" for input as #4 line input #4,a$:close #4:kill "_scores.tmp" z=instr(a$," "):w=val(left$(a$,z)):t=val(mid$(a$,z)) score=score+(w*3+t)*(100/rounds):nitems=nitems+1 wend:close #3:score=score/nitems return ----- end dumpsevo.bas ----------------------------------------------------- To use you'll need a benchmark set, by default the nanob2 test set placed in the /usr/local/share/cw/nanob2 directory. Benchmark sets and other scripts for testing warriors are at: http://newton.freehostia.com/cw/cwscripts.tar.gz The dumpsevo program is configured to just run using the same soup parameters as the default sevo evolver and output to soup.txt, edit to reconfigure or uncomment the input statements to specify the soup size, width, output file and benchmark set. Usage Results and Mods ---------------------- To use SEVO I make a work directory on a ram disk, copy the sevo.bas and dumpsevo.bas programs to it, then run sevo.bas to start evolving. Periodically I stop the evolver and run dumpsevo.bas to see if anything interesting is going on, renaming the soup.txt to soup1.txt soup2.txt etc. If not getting scores > 140 or so after a few hours then I discard the soup and try again. Once scores become strong, I'll make a copy of dumpsevo.bas and edit it to use the nanoht2 benchset to test against both nanob2 and nanoht2 (not at the same time - soup.txt, bench.lst and _scores.tmp would have to be changed to avoid conflict) for a more complete record of the run. For a deeper inspection I use the bench80 program (from cwscripts.tar.gz) to produce a sorted benchmark of all of the soup warriors - I thought about making that functionality a part of dumpsevo.bas but decided against it for now, since dumpsevo is designed to produce a stand-alone soup report and bench scores for warriors not listed is useless information. Besides I already have bench80 for that. I also use the pmv* and cwb* scripts from cwscripts.tar.gz to "run" warriors and benchmark individual warriors. Evolving and finding strong warriors that score > 150 is often a matter of luck.. there is no evolutionary pressure to evolve warriors that are strong against human-written code, the soup warriors are only exposed to strategies that happen to evolve. Sometimes papers evolve but scanners almost never evolve since they lose to stones, the most common type of evolved warrior. Here's a warrior (549.red) that was produced using the stock settings... ;assert 1 spl.a #-32 ,>10 mov.i {-1 ,>-1 mov.i >-2 ,{-2 mov.i *18 ,{-4 djn.x $-1 ,{-17 Benchmark against the nanob2 test set... 8c09fc1a-4799259f-174724 171.12 79 6 ***************** c82f15b5-85011fd8-5a969d 124.64 58 3 ************ Chiki Chiki 144.36 63 16 ************** eerie glow 154.92 69 13 *************** Foggy Maus (beta) 180.98 83 8 ****************** glowing embers 168.30 74 17 **************** hemlock 164.08 68 29 **************** Old Lamplights Blink 147.88 68 6 ************** Left Alone 133.09 62 3 ************* Man&Machine 147.18 68 5 ************** a slice of moonbeam pie 213.38 98 9 ********************* Muddy Mouse (RBv1.6r1.1. 133.80 61 7 ************* 01_62 137.32 61 12 ************* 02_08 150 68 9 ************** Pacler Deux 148.59 63 22 ************** Red Moon 141.54 64 9 ************** ripples 22 141.54 62 15 ************** Shutting Down Evolver No 151.40 69 8 *************** the spiders crept 180.28 80 16 ****************** White Moon 133.80 60 10 ************* Score = 153.41 Benchmark against the nanoht2 test set... 02_08.red 150 68 9 ************** 0535.red 164.78 73 15 **************** Another MEVO Thing 167.60 79 1 **************** Cosmic Uncertainity 161.26 75 4 **************** Creamed Corn 136.61 62 8 ************* Crimson Climber 152.11 69 9 *************** Dodecadence 123.94 55 11 ************ eerie glow 154.92 69 13 *************** e6843-5724-xt430-4-nano- 148.59 61 28 ************** Fragor Calx 160.56 74 6 **************** Frothering Foam 143.66 65 9 ************** Furry Critter 157.04 73 4 *************** girl from the underworld 107.04 50 2 ********** hemlock 164.08 68 29 **************** Hot Soup 117.60 53 8 *********** JB268 171.12 79 6 ***************** Left Alone 133.09 62 3 ************* Man&Machine 147.18 68 5 ************** medusa's mirror 164.08 77 2 **************** Military Grade Nano 123.23 58 1 ************ a slice of moonbeam pie 213.38 98 9 ********************* Muddy Mouse (RBv1.6r1.1. 133.80 61 7 ************* NanoWorms 153.52 66 20 *************** Obsidian peasoup 137.32 64 3 ************* Pacler Deux 148.59 63 22 ************** Red Moon 141.54 64 9 ************** Little Red Rat 154.92 72 4 *************** ripples in space-time 140.14 60 19 ************** Science Abuse 170.42 78 8 ***************** Shutting Down Evolver No 151.40 69 8 *************** Sleepy Lepus 138.02 59 19 ************* rdrc: Snapback Sprite 152.11 71 3 *************** the spiders crept 180.28 80 16 ****************** Steaming Pebbles 139.43 63 9 ************* Stegodon Aurorae 117.60 52 11 *********** Transfer Function 117.60 53 8 *********** White Moon 133.80 60 10 ************* wrath of the machines 156.33 73 3 *************** Score = 148.12 Sometimes tweaking some of the evolving settings helps. The number of rounds in the pmars command line (the number after -r) can make a big difference, a lower number of rounds improves diversity and helps to avoid settling into a "local maximum", a higher number of rounds improves the peak scores but usually only if relatively strong warriors are already present. One trick is to evolve with a lower number of rounds or the default of 70, then once strong code is present run for a short time with the rounds increased to 100 or even 200. But don't run it that way for too long or a warrior form that beats other soup warriors (but doesn't necessarily bench well) might take over the soup. With other evolvers, evolving with a lower number of rounds sometimes produces more paper-type warriors but producing strong nano papers using only pure unguided evolving methods is tricky stuff, at the time of this writing I haven't seen any good papers from SEVO. The soup size and width are specified by n=2000 and d=50, n should be a multiple of d to make the soup dump look right. Smaller soups evolve faster but have less diversity, the algorithm tends to produce islands of similar warriors that evolve semi-independently so a larger soup tends to increase the odds of a strong form arising. The pmars command line specifies the core parameters and thus what class of warriors are produced. The l variable setting specifies the maximum number of warrior lines and must be equal to or greater than the pmars -l setting. Data numbers are chosen to be less than the c variable setting, since the numbers are plus and minus, c should be set to coresize/2+1. The -d setting to specify minimum warrior separation is omitted, this might work better... p$="pmars -bkl 5 -d 5 -s 80 -p 80 -c 800 -r 70 ":n=2000:d=50:l=5:c=41 Generally only competitive nano warriors can be evolved but here are settings for coresize 800... p$="pmars -bkl 20 -d 20 -s 800 -p 800 -c 8000 -r 50 ":n=2000:d=50:l=20:c=401 ...and for coresize 8000... p$="pmars -bkl 200 -d 200 -s 8000 -p 8000 -c 80000 -r 30 " n=2000:d=50:l=30:c=4001 [split to 2 lines for formatting] The i$ line specifies the base instruction choices, k specifies the number of instructions in the list. Instruction choices are weighted so that instructions towards the beginning of the list are chosen more frequently, the amount of weighting is determined by the number after the ^ in line 24, default is 1.8. Remove the ^1.8 part for even selection to permit manually weighting instructions by duplicates in the i$ list. For example... i$="mov.mov.mov.djn.spl.":k=5 label a:z$=mid$(i$,int(rnd*k)*4+1,4)+mid$(z$,5):return The m$ and n$ strings specify the instruction modifiers and address modes, with t and q set to the number of items in the strings. Usually these don't need adjusting unless you want to constrain the selections. The numbers after rnd< in lines 12-22 determine the chances for each evolving operation.. line swap, line delete, line dup, instruction change, modifier change, A-field address mode change, A-field data change, B-field address mode change, B-field data change, A-field data increment or decrement, and B-field data increment or decrement. Random data numbers are weighted to prefer smaller numbers, the amount of weighting is determined by the number after the ^ in line 27. The parameters aren't all that optimized other than playing around somewhat with the instruction mix and numbers until it tended to favor the superior spl mov mov mov djn form over the weaker spl mov mov djn form. Most nano warriors use only spl mov and djn instructions but added other instructions that occasionally are used by existing nano warriors to increase diversity and just in case the evolving process finds them useful. --------------------------------------- This software is presented as-is and without warranty of any kind. This software is public domain, do whatever you want with it. Last modified December 19, 2011 Terry Newton (wtn90125@yahoo.com)