Tinywarrior Issue 4

The fourth issue of Tinywarrior has just been published, the newsletter which reports the latest events and techniques for the tiny hill. Here's what you can expect to find in this issue:

Flux and the SPL/DIV Clear by John Metcalf examines a SPL/DIV clear inspired by G2.

Larger Than Infinity by Zul Nadzri reveals the results of Zul's experiments with White Noise.

Any feedback would be greatly appreciated.

Maezumo, Evolving for the Corewar Tiny Hill with a Twist

At the beginning of August, Christian Schmidt released version 1.04 of Maezumo, his corewar evolver. If you're familiar with the old version the biggest difference you'll notice are the additions to the progress report.

Maezumo evolves warriors using traditional mutation, keeping a hill of the top warriors. Hill warriors are then injected back into the soup. Where Maezumo offers something innovative is in the hint modes.

If the hint modes are enabled, Maezumo generates warriors from inbuilt templates. These challenge the hill and if successful enter the soup for further enhancement by the mutation algorithm.

Maezumo is supplied with a Windows binary, Basic source code and all the necessary support files. To evolve for the tiny hill, I simply extracted the archived, changed the settings in maezumo.ini and double clicked maezumo.exe. I selected the scanner/paper hint mode to cover the two most successful tiny strategies.

After a 13 hour run, the top warrior on Maezumo's hill is an evolved style paper which scores 75 against SAL's tiny hill. I think it would be realistic to expect a strong tiny warrior after a 3 or 4 day run.

Have you tried Maezumo yet? If so, let me know your thoughts :-)

TEV Hints and Another Evolved Bomber

Recently I've been experimenting with different hints in TEV0 and TEV12 hoping to guide the evolution of Redcode programs. TEV is a small program written in Basic and uses the principles of random mutation and survival of the fittest to create a Redcode program over a number of generations.

Redcode is the language of Corewar, a game in which two or more programs battle to control the memory of a virtual computer. Here's a quick introduction to Corewar. Traditionally programs are coded by hand, but a number of players have risen to the challenge of writing a program to evolve good contenders.

The purpose of a hint is to control the direction of evolution by issuing a score penalty for certain types of code. Here are the hints I've been experimenting with:

• a penalty for three consecutive opcodes the same
• a penalty for the first opcode being a SPL
• a penalty for the a-mode of a SPL being #

This produced some really weird programs to begin with, but after relaxing the penalties stronger programs emerged. Unfortunately TEV still hasn't produced a decent replicator so instead here's the code for the most successful bomber of the latest run, medusa's mirror:

;redcode-nano
;name medusa's mirror
;author John Metcalf
;strategy evolved using TEV12 with hints
;assert CORESIZE==80

mov.i <46, $11
spl.i #-4, {56
mov.i <36, {79
mov.i {79, {54
djn.f $78, {59
end

Next I'm hoping to divide the pool into different regions and implement a different hint in each region. If you have any suggestions for hints, please let me know.

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

The Corewar DynaHill

Christian Schmidt has announced the opening of a new Corewar hill with a ranking system similar to Japanese Sumo. The Corewar DynaHill is of unlimited size. New warriors enter at the bottom and at certain time intervals each warrior fights 15 neighbours.

Depending on the number of wins / losses, each warrior moves either up or down a number of positions. Eventually, the warrior will be unable to climb higher, possibly becoming King of the DynaHill!

'94draft and limited process warriors co-exist on the hill. If a '94draft warrior battles against a limited process warrior, a random number of processes is chosen between 40 and 120.

The use of PIN and MAXPROCESSES is forbidden. The maximum length is 200.

For more information, take a look at The Corewar DynaHill FAQ.

nanoWarrior Issue 3

The third issue of nanoWarrior has just been published, thanks to the hard work of S. Fernandes and Germán Labarga.  In this issue:

Exploring the Dynamics of the Corewar Nano Hill looks how the balance of power has changed and examines the interaction between different strategies.

Paper/Clear on the Nano Hill by Germán Labarga investigates the history and effectiveness of paper on the nano hill.

Optimizing Ripples in Space-Time by S.Fernandes describes the optimization process of a successful nano paper.

Enjoy the issue.  Any feedback would be greatly appreciated.

Mini Challenge #7 - Results

Neo's Corewar Mini Challenge #7 is over and the results are in.

Mini Challenge #7 - Part 1

In part 1, 6 players discovered a 1 line solution with 100% ties. In all of the entered solutions, the imp overwrites the wimp and the wimp's process becomes an imp.

Roy van Rijn and Rashnok found the following solution:

    mov.i #1, }1

Neogryzor and S. Fernandes discovered the following:

    mov }0, }1

And finally, Ilmari Karonen and I entered the following:

    mov.i #1, *1

Mini Challenge #7 - Part 2

In part 2, 5 players found a 2 line, 1 process solution with 100% ties.

Ilmari Karonen was first to submit an optimal solution. Ilmari's imp stops when it reaches the wimp and the process enters the DJN loop:

    mov.i }0, *1
    mov.i }1, *1

Rashnok and I both found the following solution. Our imp overwrites the wimp and the wimp's process becomes an imp:

imp mov.i #3,*-1
    jmp imp,{0

I also entered a slight variation:

    mov {2, }0
imp mov.i #3,*-1

S. Fernandes discovered the following. The imp's process enters the DJN loop:

imp mov.i #4, *1
    djn.a imp, #0

Finally Roy van Rijn used his evolver to discover 58 solutions! Here are Roy's 58 entries.

Thanks to Neo for organising the challenge.

Roy's Modification to Mini Challenge #7

Roy suggested an interesting modification to Neo's Mini Challenge #7 in rec.games.corewar. Create an imp capable of passing through the following code:

djn.f #0, >-5

The aim is to tie as often as possible.  Lines of code and the number of processes should be kept to a minimum.

• Newbies should aim for >95% ties in 7 lines or less.
  
• Intermediate redcoders should be able to discover a solution with 100% ties in 5 lines.
  
• Corewar pros should aim for a solution with 100% ties in 4 lines or less!

Mini Challenge #7 - "Harmless Overrun"

Neo has proposed a mini challenge in which players have to create an imp capable of passing through a wimp with imp-gate.  Both warriors must survive the encounter.

jmp 0, <-5 

For more details, see the mini challenge homepage.

Replicate - My First Corewar Warrior

I've been searching through some ancient printouts recently and discovered my first ever Corewar program. I remember testing this on Stefan Strack's CoreWar Pro. I didn't have a clue whether or not it was any good, but at least it seemed to work! Can you remember your first warrior?

; -+REPLICATE+-
; *JAM* 1997
mov    7,    8
add    6,    6
mov   #8,   -3
mov  @-4,   <5
djn   -1,   -5
spl   -5
jmp   @2
dat  -10

An Improved '88 Quick-scanner

After reading how Paul Kline's slowQscan achieves extra scans, I wondered how well a similar technique would work in '88 Standard Redcode. Previously published '88 quick-scanners include:

• Quicksilver '88 - 24 scans in 36 instuctions
• Vala - 30 scans in 45 instuctions
• Matreshka Rulez! - 37 scans in 56 instructions
  

Using Kline's technique 36 scans are possible in 48 instructions:

qfirst equ (qp2+2*qstep)
qdist  equ qfirst+111
qstep  equ 222

qi  equ 7                       
qr  equ 7

qbomb   dat <qi/2-qi*qr,   <qi*qr-qi/2

qa  equ qstep*16
qb  equ qstep*5+2
qc  equ qstep*10
qd  equ qstep*2
qe  equ qstep*1

qgo     cmp qdist+qc,      qfirst+qc
jmp qfast,         <qa
cmp qdist+qe+qd,   qfirst+qe+qd
qp1     jmp <qfast,        <qc
qp2     cmp qdist,         qfirst
qp3     jmp qskip,         <qe

cmp qdist+qb,      qfirst+qb
q1      djn qfast,         #qp1

cmp qdist+qd+qc,   qfirst+qd+qc
jmp qslow,         <qfirst+qd+qc+4
cmp qdist+qd+qb,   qfirst+qd+qb
x1      jmp qslow,         <q1
cmp qdist+qc+qc,   qfirst+qc+qc
q2      djn qslow,         #qp2
cmp qdist+qd,      qfirst+qd
jmp qslow,         <qfast
cmp qdist+qa,      qfirst+qa
jmp q1,            <q1

cmp qdist+qa+qd,   qfirst+qa+qd
jmp x1,            <q1
cmp qdist+qc+qb,   qfirst+qc+qb
jmp q2,            <q1
cmp qdist+qe+qd+qc,qfirst+qe+qd+qc
jmp qslower,       <qfirst+qe+qd+qc+4
cmp qdist+qe+qd+qb,qfirst+qe+qd+qb
jmp qslower,       <q1
cmp qdist+qe+qc+qc,qfirst+qe+qc+qc
jmp qslower,       <q2
cmp qdist+qd+qd+qc,qfirst+qd+qd+qc
q3      djn qslower,       #qp3
cmp qdist+qe+qc,   qfirst+qe+qc
jmp <qfast,        <q2
cmp qdist+qd+qd,   qfirst+qd+qd
jmp <qfast,        <q3
cmp qdist+qd+qd+qb,qfirst+qd+qd+qb
slt <q3,           <q1

jmz pgo,           qdist+qe+qd+qc+10

qslower add @q3,           @qslow
qslow   add @q2,           qkil
qfast   add @q1,           @qslow

qskip   cmp <qdist+qstep+50, @qkil
jmp qloop,         <1234

add #qdist-qfirst, qkil
qloop   mov qbomb,         @qkil
qkil    mov <qfirst+qstep+50, <qfirst
sub #qi,           @qloop
djn qloop,         #qr+2

pgo
end qgo