Results from an Even Simpler Corewar Evolver

Over the last week I've been removing as much as possible from TEV, the Tiny Corewar Evolver. The latest version is down to 1.2K and produced a mad mad bomber which entered SAL's nano hill in 7th place:

;redcode-nano
;name wrath of the machines
;author John Metcalf
;strategy evolved mad mad bomber
;strategy 28 hours with TEV 1.2K
;assert CORESIZE==80

spl.b #76, {32
mov.i >11, {49
mov.i }79, {76
mov.i <64, {29
djn.f $-3, {58
end

Corewar Tiny Evolver TEV v0

The Corewar Tiny Evolver is a small (< 1.5K) program written in GWBasic. After a couple of hours evolving, TEV is capable of producing programs able to compete with hand-written progams and enter the Corewar nano hill.

Instructions

Place TEV0.BAS, TEV0.BAT and a selection of benchmark warriors in the same directory. The parameters in line 10-20 are set up for the nano hill but can be adjusted if required.

Run TEV0.BAT. Evolution will continue until you decide to terminate the program. Throughout the process, the best warrior can always be found in the file BEST.WAR.

Program Layout

• batch file: generate a list of benchmark warriors, run the evolver
• 10-20: set evolution parameters (see Parameters)
• 30-50: initialise the evolver
• 60-110: mutate current warrior based on how well it performs
• 120-130: write current warrior to file
• 140-180: benchmark current warrior, abort if poor performance
• 190: if benchmark warrior is best to date, save a copy
• 200-220: replace a lower scoring warrior with current warrior
• 230-250: if score below threshold, discard warrior and select another
• repeat from 60

Parameters

The evolution parameters are set in lines 10-20

• K: coresize
• L: maximum warrior length
• P: number of warriors in the evolution pool
• R: number of rounds per benchmark battle
• M$: addressing modes to be used
• O$: opcode/modifier combinations to be used
• P$: pMARS command line

TEV0.BAT

@dir /b /o-d *.red >w.evo
@echo END >>w.evo
@gwbasic tev0
@erase ?.evo

TEV0.BAS

10 P$="pmars -s 80 -p 80 -c 800 -l 5 -b -k -P":R=142:L=5:P=20:K=80
20 O$="mov.ispl.bdjn.f;xxxx":M$="<@>{*}$#"
30 DIM W$(500),A$(L,P),B$(L,P),C(L,P),D$(L,P),E(L,P),S(P):RANDOMIZE TIMER
40 W=0:OPEN "w.evo" FOR INPUT AS #1:M=LEN(M$):H=80
50 INPUT #1,W$(W+1):IF W$(W+1)<>"END" THEN W=W+1:GOTO 50 ELSE CLOSE #1
60 FOR I=1 TO L:IF RND*S(1)/H<.6/L THEN C(I,1)=(C(I,1)+INT((RND-RND)*K))MOD K
70 IF RND*S(1)/H<.7/L THEN E(I,1)=(E(I,1)+INT((RND-RND)*K))MOD K
80 IF RND*S(1)/H<.3/L THEN B$(I,1)=MID$(M$,INT(RND*M)+1,1)
90 IF RND*S(1)/H<.4/L THEN D$(I,1)=MID$(M$,INT(RND*M)+1,1)
100 IF RND*S(1)/H<.3/L THEN A$(I,1)=MID$(O$,INT(RND*LEN(O$)/5)*5+1,5)
110 NEXT I
120 OPEN "w.evo" FOR OUTPUT AS #1:FOR I=1 TO L
130 PRINT #1,A$(I,1)+" "+B$(I,1);C(I,1);","+D$(I,1);E(I,1):NEXT I:CLOSE #1
140 S(1)=0:FOR I=1 TO W:SHELL P$+" w.evo "+W$(I)+" >s.evo"
150 OPEN "s.evo" FOR INPUT AS #1:INPUT #1,Z$:CLOSE #1:Z=1
160 IF MID$(Z$,Z,1)<>" " THEN Z=Z+1:GOTO 160
170 S(1)=S(1)+3*VAL(LEFT$(Z$,Z))+VAL(RIGHT$(Z$,LEN(Z$)-Z))
180 IF I>W/5 AND S(1)*150/H<I*R THEN 240 ELSE NEXT I
190 S(1)=100*S(1)/(W*R):IF S(1)>H THEN H=S(1):SHELL "copy w.evo best.war"
200 FOR J=2 TO P:IF S(J)>S(1) THEN NEXT J:GOTO 230
210 FOR I=1 TO L:A$(I,J)=A$(I,1):B$(I,J)=B$(I,1):C(I,J)=C(I,1)
220 D$(I,J)=D$(I,1):E(I,J)=E(I,1):NEXT I:S(J)=S(1)
230 IF S(1)>H*.9 THEN 60
240 Z=INT(RND*(P-1))+2:FOR I=1 TO L:A$(I,1)=A$(I,Z):B$(I,1)=B$(I,Z)
250 C(I,1)=C(I,Z):D$(I,1)=D$(I,Z):E(I,1)=E(I,Z):NEXT I:S(1)=S(Z):GOTO 60

The Incredible! Corewar Secret

Towards the end of 2002 a five line warrior entered the KOTH.org '94 Draft hill in fifth place, later becoming King of the Hill. Although I've often been asked about Incredible, so far I've kept its secret quiet:

Program "Incredible!" (length 5) by "John Metcalf"
;strategy tweaked away one instruction

Last battle concluded at : Sun Dec 1 17:26:58 EST 2002

 #  %W/ %L/ %T               Name              Author   Score     Age
 1  40/ 42/ 18     Herbal Avenger     Michal Janeczek     139      18
 2  39/ 42/ 19           Combatra         David Moore     136       7
 3  24/ 11/ 65            Blowrag     Metcalf/Schmidt     136      62
 4  35/ 35/ 30     Mantrap Arcade         Dave Hillis     136       2
 5  24/ 13/ 64        Incredible!        John Metcalf     135       1
 6  28/ 22/ 51         Reepicheep      Grabun/Metcalf     133     135
 7  27/ 22/ 52        Son of Vain     Oversby/Pihlaja     132     106
 8  33/ 34/ 33     Cyanide Excuse         Dave Hillis     131       8
 9  25/ 22/ 53          Paperazor   Christian Schmidt     129      79
10  28/ 27/ 45          Uninvited        John Metcalf     129     125

Incredible is a standard paper/imp using an exploit to hide its true length from the KOTH script. The script has two sections. The front-end checks a warrior compiles correctly and extracts the name, author, strategy and length for the reports. The back-end runs the actual battle.

Incredible takes advantage of the fact the front-end calls pMARS with a different number of rounds to the back-end. This is used to present different code to the front-end:

;redcode-94
;name length exploit
;author John Metcalf
;strategy demonstrate how to hide a program's true length
;assert CORESIZE == 8000

    for ROUNDS < 5
        ;the front-end sees this code
        for 5
            dat 0, 0
        rof
    rof

    for ROUNDS > 4
        ;the back-end sees this code
        ;insert warrior code here
    rof
end

I couldn't reveal the secret earlier because the KOTH script crashes if the code for the back-end contains errors. The script also crashes if the exploit is used to send '94 code to the '88 hill or p-space code to the no p-space hill. Unfortunately KOTH.org will be closing in a few days so it should be safe to share this now.

First Results from a New Corewar Evolver

Over the last few days I've been working on a short program written in GWBasic to evolve Corewar programs. After a test run earlier today, plateau entered SAL's nano hill:

;redcode-nano
;name plateau
;author John Metcalf
;strategy evolved mad mad bomber
;strategy hit a plateau after 4 hours
;assert CORESIZE==80

spl.b #16,  <28
mov.i <-15, {-35
mov.i {-1,  {-3
mov.i <-28, <25
djn.f $-3,  <33
end

The evolver creates warriors through pure evolution. The soup is seeded with random instructions and evolution is guided only by performance against the 2007 Nano Benchmark. If a benchmark test is scoring below a certain threshold, the test breaks out early.

Evolution is by mutation only. Crossover, insertion and deletion are not implemented. The lower a warrior scores, the more it is changed by mutation. After each round, a high scoring program replaces a randomly chosen low scoring program.

Here are the plans for the next version:

• keep a checksum of warriors to prevent duplicates in the pool
• add a hint mode, but to keep it pure it'll hint what we don't want
• implement crossover
• think of a decent name (I think revolver is already taken)

Any suggestions would be greatly appreciated.