The Second ICPC

Christian Schmidt recently announced the Second International Corewar Programming Contest with a concept similar to the new DynaHill.

The hill will be initialised with a pool of 3800 published warriors. Entries will compete against programs in their neighbourhood and move up or down depending on their score.

An interesting twist is the chance to enter warriors in 8 different categories including '94, '88, LP and nano. For full details of the rules see the official tournament page.

The deadline is 15^th September. Good luck :-)

1.2K Tiny Corewar Evolver

Here's the latest version of the Tiny Corewar Evolver, a small (<1.2K) GWBasic program to evolve Redcode warriors against a benchmark. This version producted Wrath of the Machines after a 28 hour run.

The two biggest differences from TEV0 are as follows:

• no longer aborts a bad benchmark early
• replaces the lowest scoring warrior with the current warrior

TEV12.BAT

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

TEV12.BAS

10 P$="pmars -s 80 -p 80 -c 800 -l 5 -b -k -P":R=142:L=5:P=25:K=80
20 O$="mov.imov.ispl.bdjn.f;xxxx":M$="<@>{*}$#"
30 DIM W$(99),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$):q=0:h=1
50 INPUT #1,W$(W+1):IF W$(W+1)<>"END" THEN W=W+1:GOTO 50 ELSE CLOSE #1
60 q=(q mod p)+1:J=1:FOR I=2 TO P:IF S(I)<s(j) THEN j=i
70 NEXT i:FOR I=1 TO L:A$(I,J)=A$(I,q):B$(I,J)=B$(I,q):C(I,J)=C(I,q)
80 D$(I,J)=D$(I,q):E(I,J)=E(I,q):NEXT I:S(J)=s(q)
90 Z=S(Q)/H:FOR I=1 TO L:IF RND*Z<.3 THEN C(I,q)=INT(RND*K)
100 IF RND*Z<.3 THEN E(I,q)=INT(RND*K)
110 Z$=MID$(M$,INT(RND*M)+1,1):IF RND*Z<.3 THEN B$(I,q)=Z$
120 IF RND*Z<.3 THEN D$(I,q)=","+Z$
130 IF RND*Z<.1 THEN A$(I,q)=MID$(O$,INT(RND*LEN(O$)/5)*5+1,5)+" "
140 NEXT I:OPEN "w.evo" FOR OUTPUT AS #1:FOR I=1 TO L
150 PRINT #1,A$(I,q);B$(I,q);C(I,q);D$(I,q);E(I,q):NEXT I:CLOSE #1
160 s(q)=0:FOR I=1 TO W:SHELL P$+" w.evo "+W$(I)+" >s.evo"
170 OPEN "s.evo" FOR INPUT AS #1:INPUT #1,Z$:CLOSE #1:Z=1
180 IF MID$(Z$,Z,1)<>" " THEN Z=Z+1:GOTO 180
190 s(q)=s(q)+3*VAL(LEFT$(Z$,Z))+VAL(RIGHT$(Z$,LEN(Z$)-Z)):NEXT I
200 IF s(q)>H THEN H=s(q):SHELL "copy w.evo best.war"
210 goto 60

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.

Happy 25th Birthday Core War

When David Jones and A. K. Dewdney produced their Core War Guidelines in March 1984, they could hardly have imagined the success it would achieve. Core War is still going strong 25 years later and I'd like to wish everyone in the Core War community a very happy birthday.

Core War, a Short History:

Shortly after the guidelines were complete, an article in Dewdney's Computer Recreations column in Scientific American introduce the world to Core War. The wheels on the Core War machine had been put in motion.

The following year the ICWS was formed to standardise and promote Core War, with Mark Clarkson as director. The ICWS published The Core Wars Standard and organised the First International Core War Tournament at the Computer Museum in Boston, Mass.

William R. Buckley began publication of The Core War Newsletter in early 1987, providing a forum for Core War players. Early issues covered what we now consider the basic techniques of Core War. Later issues discussed advance topics, for example the holy grail of Core War: self-repairing programs.

Core War, 25 Years On:

Fast forward to 2009. Dozens of players are competing on the Core War hills and the possibilities seem endless. I can't help wondering what a Core War player from 1984 would make of our battle programs, or if they ever imagined how we'd be creating them 25 years later. Computer optimized constants and evolved code are the order of the day.

The ICWS has fallen by the wayside, as has TCWN. However, a number of irregular Core War journals have florished and the online Core War community organise the occasional tournament as an alternative to competing on the hill.

Let's hope Core War is still going strong in 2034, to celebrate it's 50th birthday! :-)

More About Core War:

Here are the top resources to discover more about Core War:

• Beginner's Guide to Redcode covers the basics of Redcode, the language of Core War
• pMARS is a portable Core War virtual machine, implemented in C
• The Core War Bibliography lists tutorials covering almost every aspect of Core War
• KOTH.org and KOTH@SAL organise the King of the Hill tournaments, played by email
• Koenigstuhl is a huge archive of published Core War battle programs
• #corewars is the Core War IRC channel, hosted on irc.freenode.net