Whirl: '88 qscan -> oneshot

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

Revisiting the Dragon Curve

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

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

Four Lines of Redcode

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

Fractals in Corewar

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?

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.

Redcode's OISC - the DJN Computer

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? ;-)

Implementing Forth in Redcode

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

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

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?

Redcode Interpreter for the RSSB Single Instruction Computer

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:

1. accumulator
2. always contains 0
3. input
4. 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

Call / Return Macros in Redcode, a Possible Solution

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

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)

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

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

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.

More Semaphores in Redcode

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

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.