Thoughts on Corewar...

Koenigstuhl Top 20: Where Are They Now

2011-10-22T18:43:00.001+01:00

This afternoon I stumbled across a status report from Koenigstuhl, 03 July 2001. Curious to see how the hill has changed over 10 years I compared the report to the current hill:

2001 Rank	Warrior	Author	2011 Rank
1	Pattel's Virus	Ben Ford	8
2	Recycled Bits	David Moore	12
3	Combatra	David Moore	4
4	Self-Modifying Code v0.11	Ben Ford	22
5	Self-Modifying Code v0.10	Ben Ford	25
6	Quicksilver	Michal Janeczek	76
7	Uninvited	John Metcalf	88
8	Recycled Bits--	David Moore	93
9	Tuesday Afternoon	John K W	139
10	Fire and Ice	David Moore	94
11	Recovery	Ian Oversby	97
12	Reindeer	Ian Oversby	141
13	Three Musketeers	Robert Macrae	157
14	The Stormbringer	Christian Schmidt	133
15	Am I alive?	Christian Schmidt	166
16	2 Crazy	Christian Schmidt	189
17	Digitalis 4	Christian Schmidt	198
18	Bigger Brother	Philip Kendall	58
19	Liquid Paper	Sean McDonald	109
20	Origami Harquebus	mjp	49

Only three warriors remain in the top 20 while the majority have fallen 50+ places. :-)

Whirl: '88 qscan -> oneshot

2011-09-27T19:31:00.000+01:00

Whirl is a qscan -> oneshot which recently entered the '88 hill.

;redcode
;name Whirl
;author John Metcalf
;strategy qscan -> oneshot
;assert CORESIZE==8000

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

        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     mov last,          boot+10
c       for 10
        mov last-c,        <pgo
        rof
        jmp boot+7


step    equ -12
first   equ (201*12-8)
boot    equ (pgo-first-100)

dbmb    dat <2667,         <-10

clear   spl 0,             <dbmb-sptr-8
cloop   mov @sloop,        <sptr
        mov @sloop,        <sptr
bomb    djn cloop,         <dbmb-4

steps   dat <step*3,       <step*3+1

sloop   add steps,         @cloop
        mov dbmb,          <sptr
sptr    cmp first+step*2,  @first+1
        jmp <sloop
last    jmp sloop

        end qgo

The Second ICPC

2011-08-11T19:09:00.002+01:00

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 :-)

A Brief Introduction to Core War

2011-07-01T22:51:00.002+01:00

What is Corewar?

Corewar is a programming game in which the aim is to eliminate all opponents from the memory of a virtual computer. Players write short battle programs to compete against each other.

Battle programs are written in Redcode, the assembly language of the MARS virtual processor. Redcode has 18 opcodes. Each Redcode instruction is made up of an opcode, a source pointer, a destination pointer, a source addressing mode and a destination addressing mode. For example, the mov instruction copies information from the source to the destination:

mov 10, 20

In the example, the source is 10 and the destination is 20. When the instruction is executed, it take the information in the cell 10 locations after the mov and copies it to the cell 20 locations after.

Here's another example, known as an imp:

mov 0, 1

When this executes, it copies the information from 0 locations ahead (i.e. itself) to 1 location ahead:

mov 0, 1
mov 0, 1 <--- the copy

Execution continues with the next instruction, so the program executes the copy it just made. Addresses in Corewar are relative to the cell they're stored in, so when the copy executes it makes a new copy one location ahead:

mov 0, 1
mov 0, 1 <--- the copy
mov 0, 1 <--- the second copy

The addressing mode affects how the address is interpreted. If no addressing mode is specified, direct addressing is used as in the examples above. The alternatives are immediate and indirect addressing.

Immediate addressing is indicated by an octothorpe (#). Instead of using data a number of cells away, it uses the data stored in the current instruction. For example:

add #10, 20

The # shows the data to be used is 10, not the value from the cell 10 locations away. add #10, 20 adds 10 to the value in the cell 20 locations ahead.

Indirect addressing is indicated by one of the following symbols, < @ > { * }. Instead of using data from a number of cells away, that data is used as a pointer to the actual data to be used. For example:

add #10, @1
dat 0,   19

When the add instruction executes, it adds 10 to the cell 20 locations ahead. @1 tells the Redcode processor to use the destination of the cell 1 location away as a pointer. This contains 19, so the destination is 19 locations after the dat, or 20 after the add.

Here's a quick run down of addressing modes. A-field is another name for the source pointer and b-field is for the destination pointer:

< use the b-field as a pointer after subtracting 1 from it
@ use the b-field as a pointer
> use the b-field as a pointer and afterwards add 1 to it
{ use the a-field as a pointer after subtracting 1 from it
* use the a-field as a pointer
} use the a-field as a pointer and afterwards add 1 to it
# use the data in the currently executing instruction

Here are the 18 opcodes supported by the Redcode processor:

mov - copy data from source to destination
add - add value from source to destination
sub - subtract value at source from destination
div - divide destination by source
mod - destination = destination MODULO source
mul - multiply destination by source
seq - skip next instruction if source equal to destination
sne - skip next instruction if source not equal to destination
slt - skip next instruction if source less than destination
jmp - jump to a-field
jmn - jump to a-field if b-field non-zero
jmz - jump to a-field if b-field zero
djn - subtract 1 from b-field. if result non-zero, jump to a-field
spl - start a new thread at a-field
dat - destroy thread when executed
stp - store source to private memory
ldp - load private memory to destination
nop - no operation

An Early Description of Core War

2011-02-10T20:44:00.006Z

Until I saw this description of Core War I assumed Dewdney and Jones were the first to use the term in the Core War Guidelines.

“Core war is a game surreptitiously played by systems programmers on large installations, where a player's goal in each fixed time slice of real time is to propagate his program elsewhere in memory, while doing as much “damage” (read: clearing to zero) as possible at random places in the hopes of causing the opponent's program to blow up. The game of core war is rarely mentioned with more than a whisper, and thus tends to be lost amid the din of easier and less abstract games such as Star Trek, Adventure or Dungeons and Dragons”

-- BYTE Magazine, July 1978, page 106-107

This brief description was published 6 years before A. K. Dewdney's first Core War article in Scientific American (May 1984, page 14-22).

Have you seen any other early mentions of Core War?

Revisiting the Dragon Curve

2011-01-17T14:11:00.002Z

A few days ago I published code to draw the Heighway Dragon Curve. Here's a variation that's 3 lines shorter and plots the curve in 655360 cycles. The pMARS command line is pmarsv -s 90000 -c 1000000.

;redcode-fractal
;name Dragon Curve 2
;author John Metcalf

        width  equ 315
        stack  equ dragon+100
        plot   equ direct+width+1
        first  equ 80*width+50

        mov    #first,   plot
dragon  mov.ab count,    <plot
test    mov.b  @plot,    #0
        add.ba @plot,    direct
        div    #2,       @plot
        mod    #2,       test
        jmz    test,     test
        mod.a  #4,       direct
direct  add.b  3,        width+1
count   sub.ba #65536,   #1+1
        jmp    dragon,   -width+1

Dragon Curve in Redcode

2011-01-09T19:59:00.000Z

The Heighway Dragon Curve is fractal line than goes through a series of 90° turns, creating a pattern which fills a 2 dimensional space. The program plots 32768 points in 458741 cycles. The pMARS command line is pmarsv -s 90000 -c 500000.

;redcode-fractal
;name Dragon Curve
;author John Metcalf

        width  equ 315
        stack  equ dragon+100

dragon  mov.x  paira,    <stack
recur   djn    dragon,   #15
        mod.a  #4,       direct
        add.b  *direct,  plot
plot    mov    >recur,   80*width+110
        mov.ba >stack,   ret
ret     jmp    0,        }stack
turn    add.a  @stack,   direct
        mov.x  pairb,    <stack
        jmp    recur

direct  dat    3,        width
paira   dat    turn-ret, -1
        dat    0,        -width
pairb   dat    plot-ret, 1

Corewar Programming Contest

2010-12-09T22:12:00.003Z

The First International Corewar Programming Contest has just been announced, with a first prize of $50 sponsored by www.corewar.info.

The competition takes place in the unexplored area between '94nop and LP settings which has recently been investigated by Fizmo in Redcode Talk.

The exact settings are as follows:

Standard:	CWS'94
Coresize:	8000
Processes:	200
Entry length:	20
Points win:	3
Points tie:	1
Cycles:	80000
Rounds:	1000

The pMARS command line is pmars -p 200 -l 20 -r 1000. STP and LDP are forbidden, up to two entries are allowed and battles will take part in a round-robin tournament.

For more information, take a look at the announcement in rec.games.corewar.

Four Lines of Redcode

2010-11-05T23:07:00.006Z

The Sierpinski triangle or gasket is a fractal named after the Polish mathematician Waclaw Sierpinski. Surprisingly the fractal can be generated with just 4 lines of Redcode:

        width  equ 126
        trail  equ (sum-CORESIZE%width)
        start  equ (trail-width+1)

sum     mov    #3,    @3
ptr     mov.b  trail, sum
        add.b  {ptr,  sum
        djn    sum,   #start

The magic incantation for pMARS is pmars -v 132. Alternatively set the width to 128 to view using CoreWin :-)

Redcode Talk Issue 1

2010-09-05T07:58:00.004+01:00

Christian Schmidt recently published the first issue of Redcode Talk. The issue contains a couple of articles by Fizmo:

The undiscovered area between LP & 94draft
Random Warrior Talk: One Man Army v1.0

Happy Numbers

2010-07-23T23:54:00.025+01:00

Today's Programming Praxis challenges us to write a program to list the happy numbers up to a given limit. A number is happy if the sum of the square of it's digital eventually reaches 1. E.g. 7 is happy because 7²=49, 4²+9²=97, 9²+7²=130, 1²+3²+0²=10, 1²+0²=1.

Here's my solution in Redcode:

org    newcand

        base   equ 10
        limit  equ 100
        tries  equ 50

stack   dat    0
happy   dat    1
cand    dat    0
total   dat    0
repeat  dat    0
 
newcand mov.ba happy,     cand
        mov    #tries,    repeat
again   mov    #-1,       total
digits  mov.ab cand,      cand
        mod    #base,     cand
        div.a  #base,     cand
        mul.b  cand,      cand
        add.b  cand,      total
        jmn.a  digits,    cand
        jmz    found,     total
        mov.ba total,     cand
        add.a  #1,        cand
        djn    again,     repeat
nexthap seq    #limit,    happy
        jmp    newcand,   >happy
        dat    0

found   mov.b  happy,     <stack
writen  mov.b  @stack,    <stack
        div    #10,       >stack
        mod    #10,       @stack
        add    #48,       @stack
        jmn    writen,    <stack
        add    #1,        stack
wloop   sts    >stack,    0
        jmn    wloop,     stack
        sts.a  #10,       0
        jmp    nexthap

Cross Simulator Core Graphics

2010-01-24T19:11:00.003Z

One difficulty when trying to write code to plot graphics in Redcode is the width of the core display. The four most popular simulators uses a variety of different widths:

Simulator	Display Width
pMARS SDL mode 0	157
pMARS SDL mode 2	126
CoreWin	128
ARES	80
nMars	various

The simplest solution is to define a variable for the width which can be modified by the person running the program. Alternatively it's possible to use the the predefined VERSION constant to determine the simulator:

Simulator	Version
pMARS SDL mode 0	92
pMARS SDL mode 2	92
CoreWin	230
ARES	0
nMars	93

Putting the two together we can write the following code which sets the correct width for pMARS SDL, CoreWin and ARES:

width equ ( (VERSION==92)*157 + (VERSION==230)*128 + (VERSION==0)*80 )

Fractals in Corewar

2010-01-07T20:49:00.004Z

In 1997 Anton Marsden organised a Corewar tournament with a difference. The three rounds challenged players to use Redcode to solve a variety of problems.

In the third round of Anton's Corewar Tournament the challenge was to write a Redcode program to draw a pretty picture. First place was taken by Ilmari Karonen with a fractal fern.

Here's my own attempt at creating a pretty picture in the core view of pMARS. It's a fractal known as the Koch Curve.

Here's the program, just 18 instructions:

width equ 157

        org    koch

        stack equ count+30

koch:   mov    #2-ptr, >stack
        jmp    count,  }move

        sub.a  #2,     move
        mov    #2-ptr, >stack
        jmp    count

        jmp    return, }move

count:  djn    koch,   #11
        mod.a  #8,     move
        div.a  #2,     move
        add.b  *move,  pos
        mul.a  #2,     move
pos:    add    #1,     koch+71*width/2+16
return: mov.ba <stack, ptr
ptr:    jmp    0,      >count

move:   dat    -1
        dat    -width
        dat    1
        dat    width

Have you tried to write a graphical display in Corewar?

Tinywarrior Issue 4

2009-10-27T08:01:00.003Z

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

2009-08-25T13:26:00.004+01:00

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

2009-07-09T06:54:00.005+01:00

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

2009-06-25T23:14:00.003+01:00

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

2009-06-20T21:27:00.001+01:00

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

2009-06-10T21:32:00.008+01:00

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

2009-05-27T13:07:00.009+01:00

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

2009-05-25T22:15:00.003+01:00

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.

Redcode's OISC - the DJN Computer

2009-04-19T01:11:00.004+01:00

An OISC is an abstract computer designed to be Turing complete with only one instruction. OISC is short for One-Instruction Set Computer.

The instruction used by most variants of OISC subtracts and branches on certain conditions, for example the URISC / RSSB Single Instruction Computer. It may come as a surprise that the Redcode instruction set contains a primative instuction suitable for building a One-Instruction Computer, DJN.

DJN X, Y uses Y as a pointer into memory. 1 is subtracted from the value stored at location Y. If the result is non-zero, DJN jumps to X. Here's an example demonstrating how to copy A to B using DJN:

        DJN 0,   TEMP
        DJN 0,   B
        DJN 1,   TEMP
        DJN -1,  A
        DJN 1,   A
        DJN 1,   B
        DJN -2,  TEMP

Unfortunately, the performance is poor, 56000 cycles to execute a MOV!

The following code proves DJN is Turing complete by equivalence to SUBLEQ A, B, C:

         DJN 0,   TEMP
         DJN 1,   TEMP
         DJN 10,  B
         DJN 4,   SCRATCH
         DJN 3,   SCRATCH
         DJN 1,   TEMP
         DJN 1,   B
         DJN -2,  A
         DJN 1,   A
         DJN -1,  TEMP
         DJN C,   SCRATCH
         DJN C,   SCRATCH
         DJN -11, A
         DJN 1,   A
         DJN -1,  TEMP

So, who's volunteering to implement the first self-interpreter? ;-)

Happy 25th Birthday Core War

2009-03-02T10:55:00.001Z

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

Implementing Forth in Redcode

2009-02-24T17:28:00.008Z

I'm currently working on a threaded Forth interpreter in Redcode. The first version should provide about 20 key Forth instructions in 50 lines of code.

Threading

The Forth program will be stored as a list of subroutine calls, for example:

        dat    lit     ; push 1111
        dat    1111
        dat    lit     ; push 1234
        dat    1234
        dat    plus    ; add TOS to 2OS
        dat    udot    ; display TOS

A more compact representation would be to store addresses in both the a-field and b-field. Unfortunately this would be at the expense of more complex flow control:

        dat    lit,      1111
        dat    lit,      1234
        dat    plus,     udot

I'm open to suggestions how the interpreter can use the compact representation without causing too many difficulties.

Instruction Set

I'm planning to support the following instructions in version 1. Have I missed anything important, or have I included something which can be left out:

Ins	Description
-	subtract TOS from 2OS
+	add TOS to 2OS
*	multiply TOS by 2OS
U.	print TOS as an unsigned number
SPACE	print a space
DUP	copy TOS
DROP	remove TOS
ABS	replace TOS with its absolute value
NEGATE	replace TOS with -TOS
!	2OS is stored at the address in TOS
+!	2OS is added to the address in TOS
@	fetch the value at the address in TOS
=	TRUE if TOS=2OS, else FALSE
SWAP	exchange TOS with 2OS
DEPTH	number of elements on stack
BEGIN	start of BEGIN .. UNTIL structure
UNTIL	if TRUE, return to matching BEGIN
DO	start of DO .. LOOP structure
LOOP	inc counter, jump to DO if below limit

Signed vs Unsigned

Unfortunately numbers in Forth are signed and numbers in Redcode are unsigned. This affects a number of instructions, including division and comparison. Would it be worth the extra code to support unsigned numbers in Redcode Forth?

Example Code

The following example interprets +, U. and literals. New instructions can easily be added in Redcode. Support for calling new instuctions written in Forth needs to be added:

        org    next

stack   dat    0,         0

; LIT - place the next value on the stack

lit     mov.b  }ip,       <stack
        jmp    next

; + - remove 2OS and TOS and put their sum on stack

plus    add.b  >stack,    @stack
        jmp    next

; U. - remove and display TOS as an unsigned number

udot    mov.b  @stack,    <stack
        div    #10,       >stack
        mod    #10,       @stack
        add    #48,       @stack
        add    #1,        udcount
        jmn    udot,      <stack
        add    #1,        stack
udloop  sts    >stack,    0
udcount djn    udloop,    #0
        sts.a  #32,       0
        jmp    next

; --------------------------------

next
ip      jmp    @prog,     }ip

; --------------------------------

prog
        dat    lit     ; push 1111
        dat    1111
        dat    lit     ; push 1234
        dat    1234
        dat    plus    ; add TOS to 2OS
        dat    udot    ; display TOS

        end

Underload Interpreter in Redcode

2009-02-16T13:32:00.000Z

Underload is a stack-based esoteric programming language designed by ais523. A set of 8 single character instructions operate on a stack of variable length strings:

Ins	Description
:	copy the top stack entry
!	drop the top stack entry
~	swap the top two stack entries
*	join the top two stack entries
S	display then drop the top stack entry
^	drop then run the top stack entry
a	enclose the top stack entry in parentheses
( )	add a new stack entry

A combination of different factors make an interpreter for Underload an interesting project to tackle in Redcode:

parsing single character instructions is easy, I don't like writing parsers
handling variable length data can be tricky
no operands / no side effects to worry about
only 8 instructions, the size of the interpreter should be reasonable
^ is the only means of flow control

The final code weighs in at a mere 79 instructions. Here's the final version of the Underload Interpreter. If you have any improvements to suggest, please leave a comment below.

Display Signed Number in Base X

2009-02-06T21:52:00.000Z

The following Redcode displays a signed number is a chosen number base:

dot     slt    @stack,    #1+CORESIZE/2
        sts.a  #45,       0
        slt    @stack,    #1+CORESIZE/2
        mul    #-1,       @stack
udot    mov.b  @stack,    <stack
        div.b  base,      >stack
        mod.b  base,      @stack
        slt    @stack,    #10
        add    #7,        @stack
        add    #48,       @stack
        add    #1,        udcount
        jmn    udot,      <stack
        add    #1,        stack
udloop  sts    >stack,    0
udcount djn    udloop,    #0

base    dat    10

Unfortunately, the code is pretty ugly. Can you suggest a more elegant solution?

Brainf*** Interpreter in Redcode

2009-01-25T14:12:00.006Z

Brainf*** is an esoteric programming language developed by Urban Müller. There are 8 instructions in brainf***:

Ins	Macro	Description
<	lt	move pointer left
>	gt	move pointer right
+	inc	increment memory cell at pointer
-	dec	decrement memory cell at pointer
.	out	output a character from the cell at pointer
,	in	input a character and store in cell at pointer
[	op	jump past matching ] if cell at pointer is 0
]	cl	jump to matching [ if cell at pointer not 0

Brainf*** operates on an array of memory cells and has a pointer into the array. Each instruction translates directly into Redcode. Before executing the brainf*** program, the interpreter calculates and stores the offset for [ and ] to avoid repeated searching.

Here's the code:

        lt equ sub #1, ptr
        gt equ add #1, ptr
        inc equ add #1, @ptr
        dec equ sub #1, @ptr
        out equ sts @ptr, 0
        in equ lds @ptr, 0
        op equ jmz 0, @ptr
        cl equ jmn 2, @ptr

        org    seek

ptr     mov.ba #0,        #prog

find    sne.a  #2,        *ptr
        sub    #1,        count
        sne.a  #0,        }ptr
        jmp    find,      >count
count   jmn    find,      #0

        mov.a  ptr,       @ptr
        sub.ba ptr,       >ptr
        mov.ba ptr,       {ptr
        sub.a  ptr,       *ptr

seek    jmn.a  seek,      >ptr
        jmn    ptr,       <ptr

prog

Redcode Interpreter for the RSSB Single Instruction Computer

2009-01-18T16:14:00.005Z

The RSSB single instruction computer is a minimal, Turing complete virtual machine. The instruction used is Reverse Subtract and Skip if Borrow. RSSB subtracts the accumulator from the contents of a memory location and stores the result in both. The next instruction will be skipped if the accumulator was greater than the value in memory.

Jumps can be implemented by manipulating the instruction pointer at memory location 0. Other special locations are as follows:

accumulator
always contains 0
input
output

Here's the code for the interpreter. I've included a Hello World program written in RSSB. If you think you can reduce the size of Hello World, please let me know how.

        org    rssbint

rssbint mov.ba >ip,       ip    ; load next instruction

        mov    #0,        zero  ; set zero

        sne.a  #3,        ip    ; handle input
        lds    in,        0

        sne.a  #4,        ip    ; handle output
        sts    acc,       0
        mov    acc,       out
        add    out,       out

        slt    *ip,       acc   ; set flag for skip
        mov    #2,        skip

        sub.b  acc,       *ip   ; acc, *ip = *ip - acc
        mov.b  *ip,       acc

skip    djn    noskip,    #1    ; skip if required
        nop    >ip,       >skip

noskip  slt    #7900,     @ip   ; protect interpreter

        jmn    rssbint,   ip    ; loop until ip = 0

; --------------------------------------

ip      dat    5      ; instruction pointer
acc     dat    0      ; accumulator
zero    dat    0      ; always 0
in      dat    0      ; character input
out     dat    0      ; character output

; --------------------------------------

loop    dat    -ip+   acc       ; acc = character from ptr
ptr     dat    -ip+   hello        

        dat    -ip+   out       ; display character

        dat    -ip+   zero      ; acc = -acc

        dat    -ip+   zero      ; always skipped

        dat    -ip+   sum       ; subtract acc from sum

        dat    -ip+   ip        ; skipped if sum is negative,
                                ; otherwise jump to 0

one     dat    -ip+   acc       ; subtract 1 from ptr
        dat    -ip+   one
        dat    -ip+   ptr

        dat    -ip+   acc       ; jump to loop
        dat    -ip+   loopoff
        dat    -ip+   ip
loopoff dat    -loop

sum     dat    -1116

        dat    33         ; '!'
        dat    100        ; 'd'
        dat    108        ; 'l'
        dat    114        ; 'r'
        dat    111        ; 'o'
        dat    87         ; 'W'
        dat    32         ; ' '
        dat    44         ; ','
        dat    111        ; 'o'
        dat    108        ; 'l'
        dat    108        ; 'l'
        dat    101        ; 'e'
hello   dat    72         ; 'H'

        end

The Corewar DynaHill

2009-01-09T22:15:00.003Z

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.

Call / Return Macros in Redcode, a Possible Solution

2009-01-06T09:58:00.003Z

Here's one solution to the call / ret problem in Redcode. Unfortunately the offsets in multi-line-equates can be slightly out. In this solution, the offsets are adjusted the first time the call is executed. Here's how it works:

call routine compiles as follows:

        mov    #2-return, <stack ; save return address
        jmp    callsub,   1+routine ; jump to callsub which adjusts the address
                                    ; b-field pointer is either correct or out by 1

callsub then adjusts the pointer if necessary and moves it to the a-field of the jmp:

         mov    #2-return, <stack ; save return address
         jmp    routine,   1+routine ; jump to routine, a-field is correct

The jmp now contains the correct offset and jumps directly to routine in future.

Here's the code:

stack   dat    0

call    equ    mov    #2-return, <stack
        equ    jmp    callsub,   1+

ret     equ    jmp    return

return  mov.b  >stack,    #0
        jmp    @return

callsub mov.b  @stack,    #0
        add    #return-callsub, callsub
        mov.ba <callsub,  @callsub
        slt.b  @callsub,  #CORESIZE/2
        jmp    @callsub
        djn.a  @callsub,  @callsub

Call / Return Macros in Redcode

2009-01-04T12:17:00.003Z

For a while I've been trying to implement call / ret macros in Redcode so I can call subroutines. The obvious solution is as follows and doesn't work correctly:

; this code is buggy

stack   dat    0

call    equ    mov    #2-return, <stack
        equ    jmp

ret     equ    jmp    return

return  mov.b  >stack,    #0
        jmp    @return

Unfortunately, this only works for forward calls. The address offset is out by 1 for reverse calls and I can't find a simple fix. I've tried the following solutions, but I'm not particularly happy with any of them:

adding a nop to the top of all subroutines (extra code)
using a macro to automatically adjust the address, e.g. call subroutine adjust (ugly)
adjusting the address the first time it is executed (extra code, slower)

Can you suggest a better solution?

Write Number (implemented using a data stack)

2008-12-24T00:25:00.001Z

Here's an alternative version of the routine to display numbers using exMARS Stream's sts opcode. The code executes in 8x+1 cycles, where x is the number of digits. This implementation uses a data stack.

printd  mov.a  *stack,    {stack
        div.a  #10,       }stack
        mod.a  #10,       *stack
        add.a  #48,       *stack
        add    #1,        pcount
        jmn.a  printd,    {stack
        add.a  #1,        stack
ploop   sts.a  }stack,    0
pcount  djn    ploop,     #0

Hello World in Redcode

2008-12-07T21:34:00.000Z

Here's the shortest "Hello, World!" program I could implement, written using the sts opcode which is available in exMARS Streams.

write   sts.a  hello,     0
        sts.b  }write,    0
        djn    write,     #7

hello   dat    72,        101
        dat    108,       108
        dat    111,       44
        dat    32,        87
        dat    111,       114
        dat    108,       100
        dat    33,        10

nanoWarrior Issue 3

2008-11-19T20:00:00.006Z

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

2008-11-11T21:37:00.010Z

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

2008-10-21T20:33:00.003+01:00

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"

2008-10-17T16:44:00.001+01:00

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.

More Semaphores in Redcode

2008-10-11T21:26:00.008+01:00

While not as elegant as the solution found by Neo and Roy, the following has the advantage of only requiring one DAT.

semaphore: dat    1
        ....
reset:     mul.ab semaphore, semaphore
wait:      djn    reset,     semaphore
           mov.a  #0,        semaphore
        ....
signal:    mov    #1,        }sema

The second technique kills waiting processes, then respawns them when signaled.

semaphore: dat    1
        ....
kill:      dat    0
        ....
wait:      djn    kill,      semaphore
next:
        ....
signal:    mov.a  #1,        semaphore
           add.x  semaphore, semaphore
           seq.a  #1,        semaphore
           spl    next

Semaphores in Redcode

2008-09-29T20:43:00.007+01:00

I'm looking for suggestions on how to code busy-waiting semaphores in Redcode. The lack of an atomic test-and-set operation complicates matters.

The code below works for up to three processes, but under certain circumstances can fail with four processes. The entry points are wait and signal.

semaphore: dat 1
        ....
fail:      add #1,   semaphore
wait:      djn fail, semaphore
        .....
signal:    add #1,   semaphore

If you have any suggestions, please let me know in the comments below.

Replicate - My First Corewar Warrior

2008-07-01T09:39:00.003+01:00

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

2008-05-31T13:16:00.010+01:00

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

x^n (mod CORESIZE) in Redcode

2008-05-14T02:45:00.002+01:00

The following code implements the binary method to calculate x^n (mod CORESIZE) in Redcode. For calculations with n > 13, the binary method out-performs a simple loop.

power     mov    #1,             _powerr
_powloop  mov.b  _powern,        temp
           mod    #2,             temp
           seq.b  temp,           #0
           mul.b  _powerx,        _powerr
           mul.b  _powerx,        _powerx
           div    #2,             _powern
           jmn    _powloop,       _powern

_powern   dat    n
_powerx   dat    x
_powerr   dat    1

Binary Search in Redcode

2008-04-28T22:28:00.008+01:00

Binary search is an algorithm to find a value in a sorted list. Binary search finds the center element of the list and compares it to the target value.

If the target value is higher than the value of the center element, all elements below the center element can be eliminated from the search. Otherwise, all elements above the center element can be eliminated.

The search is then repeated on the remaining elements. In this way, binary search reduces the search space by 50% on each iteration. In Redcode, binary search is more efficient than linear search for lists of 38 or more elements.

The input parameters required are as follows:

size - the number of elements
bot - a pointer to the top of the sequence
find - the target value to find

A pointer to the required element is returned in ptr.

          nop    <bot,           >size
_bsnext   mov.b  size,           ptr
          div    #2,             ptr
          jmn    _bscont,        ptr

          mov.b  bot,            ptr
          jmp    notfound,       >ptr

_bscont   add.b  bot,            ptr
          slt    @ptr,           find
          jmp    _bstopadj

          add.b  bot,            size
          sub.b  ptr,            size
          mov.b  ptr,            bot
          jmp    _bsnext

_bstopadj sne.b  @ptr,           find
          jmp    found

          div    #2,             size
          jmp    _bsnext

Write Number

2008-04-20T19:22:00.000+01:00

Here's a short iterative routine to write a number to standard out. Although longer than the recursive algorithm, it avoids the need to maintain a data / return stack. 9x+1 cycles are required, where x is the number of digits.

The sts opcode is available in exMARS Streams.

writedec  mov    number,         temp
          jmp    _wdloop+1,      >_wdloop

_wdloop   mul    #10,            #0
          div    #10,            temp
          jmn    _wdloop,        temp

_wdprint  mov    number,         temp
          div.b  _wdloop,        temp
          add    #48,            temp
          sts    temp,           0
          mod.b  _wdloop,        number
          div    #10,            _wdloop
          jmn    _wdprint,       _wdloop

Sign v2

2008-04-12T03:56:00.000+01:00

Shortly after publishing a five line snippet to return the sign of the input value, Roy van Rijn commented with the following improvement.

As with the original, Roy's code calculates the sign of location's b-field, returning -1, 0 or 1.

sign      jmz.b  done,           location
          div    #1+CORESIZE/2,  location
          mul.ab #-2,            location
          nop    >location
done

Linear Search

2008-04-03T02:27:00.003+01:00

This short snippet of code performs a linear search on a sorted list. The average time to find a value in a sequence of x cells is x+3 cycles. This outperforms binary search on sequences up to 38 cells.

If the required values isn't in the sequence, a pointer to the first higher value is returned.

lsearch   slt    >ptr,           find
          jmp    _lsdone
          djn    lsearch,        #length
          jmp    notfound

_lsdone   sne    find,           <ptr
          jmp    found
          jmp    notfound

Lagged Fibonacci Pseudo-Random Generator

2008-03-19T09:03:00.000Z

If you need a pseudo-random number generator which works regardless of the coresize, a Lagged Fibonacci generator is one of the better options.

Here's an implementation in 3 instructions with _rndj fixed at 1. _rndk can take the values 3, 4, 6, 7, 15, 22, 60 or 63 depending on the period required. With _rndk = 4 and coresize 8000, the period is 31200.

For more variations, see the Wikipedia article on Lagged Fibonacci generators.

           _rndk  equ 4

random    mov.a  >rdata,        random_out
          mod.ab #_rndk,        rdata
          add.a  *stack,        @rdata

rdata     dat    3711,           0
          dat    1674,           0
          dat    4323,           0
          dat    7835,           0

Sign

2008-03-08T17:43:00.000Z

Calculates the sign of location's b-field, returning -1, 0 or 1.

sign      jmz.b  done,           location
          slt.b  location,       #1+CORESIZE/2
          mov.ab #-1,            location
          seq.ab #-1,            location
          mov.ab #1,             location
done

Absolute Value

2008-03-08T06:12:00.000Z

This two-line redcode snippet returns the absolute value of location's b-field.

abs       slt.b  location,       #1+CORESIZE/2
          mul.ab #-1,            location

Euclid's extended

2008-03-04T16:29:00.000Z

The extended Euclidean algorithm is used to calculate x and y given a and b in the following equation:

ax + by = gcd(a,b)

Implementation in Redcode:

          org    start

          temp   equ r-1

r         dat    55,            89 ; input a b - output gcd(a,b)
s         dat    1,             0
t         dat    0,             1  ; output x y

euclidext mov    r,             temp
          div.ab temp,          temp
          mov.ba temp,          temp
          mul    s,             temp
          sub    temp,          t

          mov    s,             temp
          mov    t,             s
          mov    temp,          t

          mod.ab r,             r
          mov.x  r,             r
start     jmn.a  euclidext,     r

selection sort

2008-02-27T21:54:00.000Z

Selection sort in an algorithm which sorts a sequence of elements. The smallest element is removed from the sequence and added to the end of a new sorted sequence. This continues until all elements have been moved to the new sequence.

Selection sort is an O(n²) algorithm. The redcode implemention is 10 instructions long and requires 1.5n²+5.5n-8 cycles in the worst case, making it approximately twice as fast as Bubble Sort.

Implementation in Redcode:

          org    outer+1

          temp   equ (outer-1)

outer     mov.b  x,              y
          mov    <p,             temp
p         mov.ba #FIRST+LENGTH-1,#FIRST+LENGTH
inner     slt    <p,             *p
          mov.ba p,              p
y         djn    inner,          #LENGTH-1
          add.b  x,              p
          mov    *p,             @p
          mov    temp,           *p
x         djn    outer,          #LENGTH-1

Bubble sort

2008-02-25T04:36:00.000Z

Bubble sort is an O(n²) algorithm to sort a sequence of elements into order. Ilmari Karonen's Bubbly Sort 1b is a 10 line implementation of Bubble sort which requires 3.5n²-0.5n-4 cycles in the worst case.

My alternative code is shown below:

Implementation in Redcode:

          org    inner

          temp   equ (outer-1)

outer     mov.b  x,              y
          mov.f  q,              p

inner     slt    {p,             <p
y         djn    inner,          #LENGTH-1
          jmz    next,           y

          mov    @p,             temp
p         mov    FIRST+LENGTH,   FIRST+LENGTH-1
          mov    temp,           *p
          djn    inner,          y
x
next      djn    outer,          #LENGTH-1

q         dat    FIRST+LENGTH-p, FIRST+LENGTH-p-1

This alternative implementation runs slightly faster than Ilmari's, at the cost of 1 extra line of code. The number of cycles in the worst case is 3n²-5, which also beats Gnome sort.

Comb sort

2008-02-19T01:56:00.000Z

Comb sort (also known as Dobosiewicz sort) makes a number of passes through a sequence of elements, exchanging any elements which are out of order. With each pass the distance between compared elements decreases. The algorithm terminates when all elements are in order.

In the redcode implementation, the value of the temp element is used as a flag to determine whether or not any exchanges occurred in the last pass.

Implementation in Redcode:

          ra     equ 4
          rb     equ 5

          org    inner

          temp   equ (outer-1)

outer     mov    #LENGTH,        y
          sub.b  gap,            y
          mov.f  q,              p
          sub.b  gap,            p
          sub    temp,           temp

inner     slt    {p,             <p
y         djn    inner,          #LENGTH-(LENGTH*ra/rb)
          jmz    done,           y

          mov    @p,             temp
p         mov    FIRST+LENGTH,   FIRST+LENGTH-(LENGTH*ra/rb)
          mov    temp,           *p
          djn    inner,          y

done      mul    #ra,            gap
gap       div    #rb,            #(LENGTH*ra/rb)

          jmn    outer,          gap
          nop    >gap,           {outer
          jmn    outer,          temp

q         dat    FIRST+LENGTH-p, FIRST+LENGTH-p

Quicksort

2008-02-12T15:58:00.000Z

Quicksort is an algorithm developed by C. A. R. Hoare in 1960 to sort a sequence of elements into order. Quicksort works by dividing a sequence into two sub-sequences.

An element is selected from the sequence and called the pivot. The sequence is then re-arranged so all elements with a value less than the pivot are before the pivot and all elements with a greater value are after it.

The sub-sequences before and after the pivot are then recursively sorted.

Implementation in Redcode:

          org    qsort

          stack  equ outer-2
          pivot  equ outer-1

outer     mov    p,              <stack
          mov    {p,             pivot

inner     slt    pivot,          >p
y         djn    inner,          #LENGTH-1
          jmz    done,           y
          mov    <p,             *p
          mov    {p,             @p
          djn    inner,          y

done      mov.a  @stack,         p
          mov.ba p,              @stack
          mov    pivot,          >p

qsort     mov.ab p,              y
          sub.b  p,              y

          slt    y,              #2
          jmp    outer,          <y

          mov.f  >stack,         p
          jmn    qsort,          p

p         dat    FIRST+LENGTH,   FIRST

stooge sort

2008-01-31T21:28:00.000Z

Stooge sort is discussed in Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms. Wikipedia's article on Stooge sort describes the algorithm as follows:

If the value at the end is smaller than the value at the start, swap them.
If there are 3 or more elements in the current list subset,
- Stooge sort the initial 2/3 of the list
- Stooge sort the final 2/3 of the list
- Stooge sort the initial 2/3 of the list again

Stooge sort is extremely inefficient. For example, sorting 100 elements requires in the region of 2.4 million cycles compared to around 3500 for quicksort and 8000 for insertion sort.

Implementation in Redcode:

          org    inner

          stack  equ outer-2
          temp   equ outer-1

outer     mov    p,              <stack
          sub.ba temp,           @stack
          mov    p,              <stack
          add.b  temp,           @stack
          sub.ba temp,           p
inner     slt    {p,             @p
          jmp    noexch,         }p

          mov    @p,             temp
p         mov    FIRST+LENGTH,   FIRST
          mov    temp,           }p

noexch    mov.ab p,              temp
          sub.b  p,              temp
          div    #3,             temp
          jmn    outer,          temp

finished  mov.f  >stack,         p
          jmn    inner,          p

insertion sort

2008-01-20T20:07:00.000Z

Insertion sort is an algorithm to arrange a sequence of elements into order. Elements are removed one by one from the unsorted sequence and inserted into the correct position in a new, sorted sequence.

For the worst case the Redcode Insertion sort requires 1.5n²+5.5n-7 cycles to sort n elements.

Implementation in Redcode:

          org    outer

          temp   equ (outer-1)

outer     nop    }z,             {q
z         mov    #0,             y
q         mov.a  #FIRST+LENGTH-p,p
p         mov    #0,             #0
          mov    {p,             temp
inner     slt    @p,             temp
          jmp    found
          mov    >p,             }p
y         djn    inner,          #0
found     mov    temp,           *p
          djn    outer,          #LENGTH-1

gnome sort

2008-01-16T06:04:00.000Z

Gnome sort is a compact O(n²) algorithm to re-arrange a sequence of elements into order. In his article on Gnome sort, Dick Grune describes the algorithm as follows:

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

The Gnome sort article on Wikipedia describes a slightly modified algorithm.

Implementation in Redcode:

          org    inner

          temp   equ (outer-1)

outer     mov    }p,             temp
p         mov    FIRST+LENGTH-1, {p
          nop    >y,             }p
          mov    temp,           }p
          sne    y,              #LENGTH
          nop    <y,             {p
inner     slt    *p,             {p
y         djn    inner,          #LENGTH-1
          jmn    outer,          y

The redcode implementation is just 9 lines long, and requires 4.5n²-3.5n cycles to sort the sequence in the worse case.

Euclid's algorithm

2008-01-07T22:07:00.000Z

Euclid's algorithm is used to determine the Greatest Common Divisor of two values. Despite it's simplicity, the only previous redcode implementation I can find is broken.

Implementation in Redcode:

          org    euclid+2

euclid    mod.ab #a,                #b
          mov.x  euclid,            euclid
          jmn.a  euclid,            euclid

parallel processes

2008-01-05T22:59:00.000Z

This macro uses the preprocessor to generate Redcode which creates a given number of parallel processes.

processes equ 100 ; works for 1 to 1048576
for 20+0*(a=1048576)
for ((processes-1)/(a=a/2))%2==1 && processes>a
spl 1
rof
for ((processes-1)/a)%2==0 && processes>a
mov.i -1,#0
rof
rof

Privacy Policy

2008-01-04T08:22:00.001Z

Privacy

I respect your privacy. The following policy explains how information is collected on Thoughts on Corewar. Your personal information will never be sold or disclosed to a third party, except where required by law.

Statistics

I use Google Analytics to track aggregate statistics about visitors to Thoughts on Corewar. This information is not linked to personally identifiable information.

Cookies

Cookies are small data files stored by a website on a user's computer. Thoughts on Corewar does not uses cookies. However, some of my advertising partners use cookies. I have no access to cookies set by advertisers.

Advertisers

I use advertising partners to display ads on Thoughts on Corewar. These partners may use cookies. I work with Google Adsense and Entrecard. I receive a list of Entrecard members who use the 'drop' feature. Please check the advertising partners' websites for their privacy policies.

Contact Information

If you have any questions please contact John Metcalf at digital.wilderness@googlemail.com.

why a new blog?

2008-01-03T13:57:00.000Z

I've been inspired to create a new blog for two reasons:

I love corewar and programming in redcode. I spend far too much of my online time creating websites that provide me with an income. Now I'd like to claim back some of that time for something I enjoy.
To show corewar is alive and well in 2008!