Small Evolver With Automatic Extraction (SEWAX) =============================================== SEWAX is a small (<5K) corewar evolver that uses a conventional algorithm (pick 2 warriors, battle them, replace loser with mutated winner) and includes a method of saving warriors that score well against a benchmark set. This also provides the ability to re-insert the good-scoring warriors back into the soup to guide the evolution process towards producing warriors that score well, without the overhead of typical bench-driven evolvers that test each warrior. The evolution engine uses a ring topology with configurable range (the maximum separation between warriors selected for battle) with mutation operations that randomly change base instructions, instruction modifiers, address modes and values. To reduce disk impact the soup is kept in memory arrays so only the two battle warriors and the score file have to be written continuously, when saving the soup is written to a single file. Various initialization options are provided for seeding the soup, or a previous run can be reloaded. This program is an experiment to discover effective methods that can possibly be incorporated into larger evolvers. SEWAX v0.7 re-inserted the top-scoring warrior at each benchmark cycle but this was limiting, v0.8 permits setting the benchmark and re-insertion rates separately. After a defined number of soup battles a benchmark is performed on the current winner, if it scores more than the current top score it is written to a "best" warrior file and saved to arrays to permit re-inserting back into the soup. After another defined number of soup battles one copy of the saved warrior is added back to the soup to either a fixed or random location. All new top-scoring warriors over a certain score are saved to individual warrior files. SEWAX is written to be run using the Blassic interpreter (http://blassic.org) on Windows and Linux systems, and requires the pmars program for performing the battles and collecting scores (http://corewar.co.uk/pmars/). The SDL version (pmars-server.exe) should work well for Windows systems (rename the binary to pmars.exe or edit the pmars command line in the SEWAX source). For Linux get the pmars source and compile a suitable binary, the source and x86 Linux binaries I use are linked from: http://newton.freehostia.com/cw/ Usual evolver precautions apply... don't run SEWAX on a solid-state disk, avoid running on a critical file system, best to run from a ram disk and make sure the computer can handle continuous 100% CPU usage. Usage: copy sewax.bas to a file, get blassic and pmars and put in a path dir (for Windows the current dir is OK), edit sewax.bas and on line 150 set DO=0 if Linux or DO=1 if Windows and make sure the pmars command line on line 140 matches the pmars binary name, make a directory named "bench" and copy the benchmark warriors there (edit line 150 to specify another directory and alter BM$ if files besides warriors are present), drop to a command line, cd to the directory SEWAX is in and run: blassic sewax.bas If benchmark warriors are misconfigured an error message may show, cancel by pressing control-C and fix. At the soup load prompt enter n for a new run or y to reload a saved soup (when reloading the next save sequence number and top score is printed). While evolving if a warrior scores greater than the current best the score is printed and the warrior saved to (by default) "1.war" and if over the save score also saved to a sequence file such as "save1.war" "save2.war" etc. Press Esc to quit, enter y to save the soup to "sf.txt". If desired scripts can be used to avoid having to open a command prompt and remove the temp files, presented after the program listing along with more usage and setup information. The settings in the listed version are for guided evolution and typically produce warriors that are strong against the provided benchmark warriors but often not against warriors not in the test set. Using a large test set (and possibly using RM=1 rather than RM=2) seems to counter this effect, changing the test set during a run may help. The idea is to somehow get the evolved warriors to develop strategies that are strong in general rather than exploiting weaknesses in specific warriors. For unguided evolution change RM=0. BF can also be lowered, also play around with the R setting - lower numbers usually result in more diversity. Unguided evolution tends to produces warriors that are naturally strong rather than learning techniques to defeat specific warriors, although the process takes longer, is more sensitive to the evolving parameters, and may not reach as high of benchmark scores as can be achieved using guided methods. This is experimental software, the stock settings may not be optimal. ------- begin sewax.bas -------------------------------------------------- 100 REM Small Evolver With Automatic Extraction 6/22/09 WTN (mod 6/24/09) 110 REM Requires Blassic and pMARS 0.9.2+ with permutate option 120 REM This code is public domain, provided as-is, no warranty. 130 REM ----- setup (see docs) ----- 140 L=5:N=1000:R=20:C=80:U=2:P$="pmars -b -k -s 80 -p 80 -c 800 -l 5" 150 DO=0:ER$=" -r 100 ":BR$=" -P ":BR=142:BF=500:BD$="bench":BM$="*.*" 160 I$="spl spl mov mov mov djn":M$=".i .i .i .a .b .f .x ":N$="$#@*<>{}" 170 IM=3:RM=2:RF=2000:MA=.02:MB=.03:MC=.03:MD=.06:ME=.03:MF=.06:MG=.01 180 SF$="sf.txt":O$="1.war":ST=135:SP$="save":SE$=".war":SN=1 190 REM ----- initialize ----------- 200 PRINT "=== SEWAX 0.8 ===" 210 NI=INT((LEN(I$)+1)/4):NM=INT(LEN(M$)/3):NN=LEN(N$) 220 IF DO THEN SHELL "dir /b "+BD$+"\"+BM$+" >c":BP$=BD$+"\" 230 IF DO=0 THEN SHELL "ls -1 "+BD$+"/"+BM$+" >c":BP$="" 240 DIM A$(N,L),B$(N,L),C$(N,L),D(N,L),E$(N,L),F(N,L):RANDOMIZE 'TIMER 250 DIM VA$(L),VB$(L),VC$(L),VD(L),VE$(L),VF(L) 260 REM ----- set initial arrays --- 270 FOR W=1 TO N:FOR I=1 TO L:A$(W,I)="nop":IF IM=0 THEN 330 280 IF IM=1 OR IM=3 THEN A$(W,I)=MID$(I$,INT(RND*NI)*4+1,3) 290 IF (IM=2 OR IM=4) AND I<=NI THEN A$(W,I)=MID$(I$,(I-1)*4+1,3) 300 IF IM<3 THEN 330 ELSE B$(W,I)=MID$(M$,INT(RND*NM)*3+1,3) 310 C$(W,I)=MID$(N$,INT(RND*NN+1),1):D(W,I)=INT((RND^U-RND^U)*C) 320 E$(W,I)=MID$(N$,INT(RND*NN+1),1):F(W,I)=INT((RND^U-RND^U)*C) 330 NEXT I:NEXT W:FOR I=1 TO L:VA$(I)="nop":NEXT I:H=0:B=0:RC=0 340 REM ----- restore best vars and soup --- 350 INPUT "Load soup";Z$:Z$=LEFT$(Z$,1):IF Z$<>"Y" AND Z$<>"y" THEN 430 360 PRINT "Loading...":OPEN SF$ FOR INPUT AS #1:INPUT #1,Z$ 370 Z=INSTR(Z$,"next save:"):IF Z THEN SN=VAL(MID$(Z$,Z+10)):PRINT SN 380 Z=INSTR(Z$,"top score:"):IF Z THEN H=VAL(MID$(Z$,Z+10))+1E-8:PRINT H 390 FOR I=1 TO L:INPUT #1,VA$(I),VB$(I),VC$(I),VD(I),VE$(I),VF(I):NEXT I 400 FOR W=1 TO N:INPUT #1,Z$:IF LEFT$(Z$,3)<>"===" THEN CLOSE #1:GOTO 430 410 FOR I=1 TO L:INPUT #1,A$(W,I),B$(W,I),C$(W,I),D(W,I),E$(W,I),F(W,I) 420 NEXT I:NEXT W:CLOSE #1 430 PRINT "Evolving, press Esc to quit" 440 REM ----- main loop ------------ 450 WHILE INKEY$<>CHR$(27):B=B+1:RC=RC+1:X=INT(RND*N+1) 460 Y=(X+(INT(RND*2)*2-1)*INT(RND*R+1))MOD N:IF Y<1 THEN Y=Y+N 470 W=X:F$="a":GOSUB 890:W=Y:F$="b":GOSUB 890:SHELL P$+ER$+" a b>s" 480 OPEN "s" FOR INPUT AS #1:INPUT #1,Z$:S1=VAL(Z$) 490 INPUT #1,Z$:S2=VAL(Z$):CLOSE #1:IF S2>=S1 THEN Z=W:W=X:X=Z 500 REM ----- mutate winner over loser ----- 510 FOR I=1 TO L:A$(W,I)=A$(X,I):B$(W,I)=B$(X,I):C$(W,I)=C$(X,I) 520 D(W,I)=D(X,I):E$(W,I)=E$(X,I):F(W,I)=F(X,I) 530 IF RNDMG OR I=1 THEN 640 600 Z$=A$(W,I):A$(W,I)=A$(W,I-1):A$(W,I-1)=Z$:Z$=B$(W,I):B$(W,I)=B$(W,I-1) 610 B$(W,I-1)=Z$:Z$=C$(W,I):C$(W,I)=C$(W,I-1):C$(W,I-1)=Z$:Z=D(W,I) 620 D(W,I)=D(W,I-1):D(W,I-1)=Z:Z$=E$(W,I):E$(W,I)=E$(W,I-1):E$(W,I-1)=Z$ 630 Z=F(W,I):F(W,I)=F(W,I-1):F(W,I-1)=Z 640 NEXT I:IF Bs":OPEN "s" FOR INPUT AS #1:INPUT #1,Z$ 680 CLOSE #1:Z=INSTR(Z$," "):S=S+VAL(LEFT$(Z$,Z))*3+VAL(MID$(Z$,Z)):WEND 690 CLOSE #2:S=(S/V)*(100/BR):IF S<=H THEN 760 ELSE H=S:PRINT S 700 REM ----- if better save to V arrays and file(s) --- 710 FOR I=1 TO L:VA$(I)=A$(X,I):VB$(I)=B$(X,I):VC$(I)=C$(X,I) 720 VD(I)=D(X,I):VE$(I)=E$(X,I):VF(I)=F(X,I):NEXT I 730 W=X:F$=O$:GOSUB 890:IF S"Y" AND Z$<>"y" THEN 870 810 PRINT "Saving...":OPEN SF$ FOR OUTPUT AS #1 820 PRINT #1,"=== next save:";SN;" top score:";H:FOR I=1 TO L 830 PRINT #1,VA$(I);",";VB$(I);",";VC$(I);",";VD(I);",";VE$(I);",";VF(I) 840 NEXT I:FOR W=1 TO N:PRINT #1,"===";W:FOR I=1 TO L:PRINT #1,A$(W,I); 850 PRINT #1,",";B$(W,I);",";C$(W,I);",";D(W,I);",";E$(W,I);",";F(W,I) 860 NEXT I:NEXT W:PRINT #1,"*END*":CLOSE #1 870 SYSTEM 880 REM ----- warrior write sub ----- 890 OPEN F$ FOR OUTPUT AS #1:PRINT #1,";assert 1":FOR I=1 TO L 900 PRINT #1,A$(W,I);B$(W,I);" ";C$(W,I);D(W,I);",";E$(W,I);F(W,I) 910 NEXT I:PRINT #1,";soup loc ";W:PRINT #1,";score ";S:CLOSE #1:RETURN ------- end sewax.bas ---------------------------------------------------- The following bash script runs SEWAX in xterm under Linux... ------- begin run_sewax.sh ------------ #!/bin/bash cd `dirname $0` xterm -e blassic sewax.bas rm a rm b rm c rm s ------- end run_sewax.sh -------------- Make sure it's in "unix" format and executeable, and there are no spaces in the SEWAX directory path. The following batch file runs SEWAX under Windows... ------- begin run_sewax.bat ----------- @echo off blassic sewax.bas for %%f in (a b c s) do del %%f > nul ------- end run_sewax.bat ------------- Make sure sewax.bas has been edited to specify DO=1. Also if new to this sort of stuff be sure to quote filenames when saving from Notepad to keep it from adding .txt to the name. By default output warriors have the extension ".war", edit line 180 to use another extension such as ".red" etc. Especially with Windows associate the output extension to at least a text editor (Notepad) to view the output. On my systems I also associate common warrior extensions (.red .war .rc) to various benchmark tools and scripts that run in pmarsv with the proper options for various coresizes. Setup... SEWAX is designed to evolve nano warriors for coresize 80. It might be useful for other coresizes, not tested. Bigger coresizes require changing the length and coresize settings in variables and on the pmars command line, and need a different instruction mix to generate semi-effective warriors. Typically only evolved nano warriors can effectively compete against hand-coded warriors, purely-evolved tiny and standard warriors are almost always weak and usually only compare to other evolved warriors. Also keep in mind that evolving usually is not repeatable and can take a long time to produce results, or may produce no good results at all. It usually takes me several tries to produce strong code, sometimes only after changing parameters in the middle of a run. Settings can be changed by editing lines 140-180... 140 L=5:N=1000:R=20:C=80:U=2:P$="pmars -b -k -s 80 -p 80 -c 800 -l 5" 150 DO=0:ER$=" -r 100 ":BR$=" -P ":BR=142:BF=500:BD$="bench":BM$="*.*" 160 I$="spl spl mov mov mov djn":M$=".i .i .i .a .b .f .x ":N$="$#@*<>{}" 170 IM=3:RM=2:RF=2000:MA=.02:MB=.03:MC=.03:MD=.06:ME=.03:MF=.06:MG=.01 180 SF$="sf.txt":O$="1.war":ST=135:SP$="save":SE$=".war":SN=1 L = warrior length N = soup size R = warrior selection range C = coresize for selecting A/B field values U = small number weighting, 1 = flat, >1 weight towards smaller values P$ = pmars command line specifying size, processes, cycles and length DO = dos enable, 1 for Dos/Windows, 0 for Linux ER$ = pmars rounds string when evolving BR$ = pmars rounds string when benchmarking (-P for permutate) BR = number of benchmark rounds for scoring (nano permutate is 142 rounds) BF = benchmark frequency, the number of soup battles between benchmarks BD$ = benchmark directory, BM$ = benchmark warrior filemask (*.* for all) I$ = list of base instructions M$ = list of instruction modifiers (each a 3-char field, space-pad) N$ = list of address mode symbols IM = soup initialize method... 0 = all nops, no modes, 0 values 1 = random instructions, no modes, 0 values 2 = sequence of I$, no modes, 0 values 3 = random instructions, modes and values 4 = sequence of I$, random modes and values 5 = nops with random modes and values RM = re-insertion method... 0 = none (unguided evolution) 1 = re-insert top warrior at location 1 2 = re-insert top warrior at random location RF = re-insertion frequency, the number of soup battles between re-insertions MA = chance per line of changing base instruction MB = chance per line of changing instruction modifier MC = chance per line of changing A-field address mode MD = chance per line of changing A-field value ME = chance per line of changing B-field address mode MF = chance per line of changing B-field value MG = chance per line (after line 1) of swapping line with previous line SF$ = soup filename, optionally saved when exiting. O$ = top-score warrior output filename ST = save threshold, warriors scoring at least this saved to separate files SP$ = prefix for saved warriors SE$ = extension for saved warriors SN = starting number for saved warriors Things... Previously (fairly) strong results were obtained by an earlier version of this program where BF(and IF) was 200, using 20 top warriors from Koenigstuhl (1/09) for the bench set. One of the ".i " modifiers was replaced by " ". This produced (that time) scores over 150 but the warriors tended to score fairly low on nanobm07 (about 143). This is a mild form of the "focus" effect usually seen with guided evolvers. To try to correct I re-evolved the soup with BF (and IF) set 1000 using a composite set of 63 warriors from nanobm07 and Koenigstuhl. After an overnight run it made this (dressed for the hill)... ;redcode-nano ;name Warm Coffee ;author Terry Newton ;strategy who knows, evolved using a mixture of random soup battles ;strategy and benchmarking, re-inserting the current top-scoring warrior ;strategy sequence: SPL MOV MOV DJN SPL (tried for different, wouldn't) ;strategy Top-20 Koenigstuhl (1/09) score = 155, NanoBM07 score = 148 ;assert CORESIZE==80 spl.a #-31,>18 mov.i #-3,>-13 mov.i *8,{-2 djn.i $-1,$-3 spl.i #27,{11 end Got 10th place with a hill score of 147.1 - retested with the current (6/23/09) Koenigstuhl top-20 and got 148 so it wasn't as strong as my older 1/09 test set suggested. Now that it preserves the high-scoring warrior in the sf.txt file, if changing bench sets during a run edit sf.txt and change the top score value to reflect the approximate benchmark score against the new set. A bit less than is OK, or set to 0 to ignore and find a new top warrior. Otherwise higher-scoring warriors might not be be saved and re-inserted into the soup. I made the change because without preserving the top warrior sometimes after restarting it did not achieve the previous top score, weaker warriors found before finding the good warriors were being added back to the soup and lowering the scores. It doesn't do that now, restarting should resume where stopped. Another run was performed on my Asus using v0.7 with BF/IF=200 and IM=1 and a composite set of 63 warriors from NanoBM07 and older warriors from Koenigstuhl, after an extended run produced a warrior that scored 152 against the composite set, 156 against the NanoBM07 set but only 142 against the top-20 Koenigstuhl warriors from Jan '09. After updating the test set to the current top-20 the top-20 score is 141. Here's the warrior... ;assert 1 mov.i {52,$15 spl.i #-38,<-53 mov.i <-1,{-2 mov.i {-3,{-16 djn.x $-2,{-7 ;soup loc 236 ;score 152.112676056338 After reconfiguring the bench set to 74 warriors (bm07 plus previous and new Koenigstuhl and published nano hill warriors) the situation has improved, the trick seems to use a fairly large bench set (maybe). Continuing with the same soup (after lowering the top score in the soup file to 145) I'm now getting... ;assert 1 mov.i <-39,$-12 spl.b #-15,>-53 mov.i <79,{-2 mov.i {-3,{-2 djn.i $-2,$-3 ;soup loc 984 ;score 152.398172820708 NanoBM07 score = 152, Top-20 Koenigstuhl score = 151. That's more like it. This was with v0.7 where bench and re-insertion frequency were the same, but that was proving to be a problem - sometimes I want to bench more to avoid missing something but without affecting the re-insertion frequency, and other times I wanted to re-insert more often to make many copies of a top form in hopes that one might mutate to become stronger. So made a few minor mods to add a RF variable to control re-insertion separately. If RF = BF then it's equivalent to the previous code. If RF = soup size then on average one re-insertion is performed per generation. The run evolving against the 74-warrior set eventually got up to a score of 153 against both bm07 and the Koenigstuhl test sets, hard to say what the precise parameters were because I kept messing with the RF variable and some of the time the setting method was different but (maybe) equivalent to RF settings of 2000-5000. Once it reached the peak even setting for very high re-insertion rate (RF=50) to saturate the soup with copies didn't produce anything stronger, so here is the final results of the run... ;redcode-nano ;name Hot Soup ;author Terry Newton ;strategy Evolved using SEWAX 0.8X using a 74-warrior composite test set ;strategy Scores 153 against both Nanobm07 and 6/23/09 Koenigstuhl top-20 ;assert CORESIZE==80 mov.i <-39,$-12 spl.i #-16,>-53 mov.i <79,{-2 mov.i {-3,{-2 djn.i $-2,$-3 end ;soup loc 58 ;score 153.483060525314 The 74-warrior test set is at: http://newton.freehostia.com/cw/bench74.zip I made another change to the code to permit viewing all bench results to better see what's going on. If not a high score it doesn't advance the line so the next bench result will overwrite. This might interfere with scrolling on some terminals so not making it part of the stock code, here's the changes: ..... 690 CLOSE #2:S=(S/V)*(100/BR):PRINT S;" ";CHR$(13); 692 IF S<=H THEN 760 ELSE H=S:PRINT S;" " ..... 792 PRINT " ";CHR$(13); ..... I performed another run using the 74-warrior benchmark and the following settings... (the only difference from stock is U=1) 140 L=5:N=1000:R=20:C=80:U=1:P$="pmars -b -k -s 80 -p 80 -c 800 -l 5" 150 DO=0:ER$=" -r 100 ":BR$=" -P ":BR=142:BF=500:BD$="bench":BM$="*.*" 160 I$="spl spl mov mov mov djn":M$=".i .i .i .a .b .f .x ":N$="$#@*<>{}" 170 IM=3:RM=2:RF=2000:MA=.02:MB=.03:MC=.03:MD=.06:ME=.03:MF=.06:MG=.01 180 SF$="sf.txt":O$="1.war":ST=135:SP$="save":SE$=".war":SN=1 The following warrior was produced after an overnight run... ;assert 1 spl.i #44,<-47 mov.i <-41,<-3 mov.i {-1,<-22 mov.i <57,<-50 djn.i $-3,<-18 ;soup loc 775 ;score 156.7472401979444 NanoBM07 score is 159.5, score against the top-20 Koenigstuhl warriors (from 6/23/09) is 148.8, both benchmarks performed at 1000 rounds fixed sequence. The setting of RF=2000 might be too low, for less focusing and closer scores between different benchmarks maybe try RF=5000. Another run on my Asus with the same parameters produced a warrior (MOV SPL MOV MOV DJN) scoring about 150 against the composite 74-warrior set, about 144 against the top-20 set and about 148 against the NanoBM07 set. Tried again, using the stock v0.8 settings (RF=2000, U=2) and the 74-warrior test set, this time I got much stronger results... ;redcode-nano ;name SWT2-21 ;author Terry Newton ;strategy Evolved using SEWAX 0.8 (6/28/09) guided by ;strategy a 74-warrior testset, composite score = 154 ;strategy NanoBM07 score = 153, Koenigstuhl-20 = 155 ;assert CORESIZE==80 spl.b #-14,<-39 mov.i >24,{-4 mov.i >13,{-2 mov.i {-3,<-42 djn.x $-2,{-4 ;soup loc 202 ;score 154.3585839360487 end ;redcode-nano ;name SWT2-28 ;author Terry Newton ;strategy Evolved using SEWAX 0.8 (6/28/09) guided by ;strategy a 74-warrior testset, composite score = 156 ;strategy NanoBM07 score = 162, Koenigstuhl-20 = 148 ;assert CORESIZE==80 spl.b #59,<-39 mov.i <26,{-3 mov.i >-66,{-2 mov.i {-3,<-42 djn.i $-2,<-16 ;soup loc 532 ;score 156.8328892272554 end ------------------------------------ Terry Newton (wtn90125@yahoo.com)