Tuesday 27 October 2009

Tinywarrior Issue 4

Tinywarrior issue 4, corewarThe 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.

Tuesday 25 August 2009

Maezumo, Evolving for the Corewar Tiny Hill with a Twist

Maezumo, the Evolver with a TwistAt 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 :-)

Thursday 9 July 2009

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.

Thursday 25 June 2009

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

Saturday 20 June 2009

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

Wednesday 10 June 2009

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

Wednesday 27 May 2009

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.

Monday 25 May 2009

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.

Sunday 19 April 2009

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

Monday 2 March 2009

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:


Tuesday 24 February 2009

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:

InsDescription
-subtract TOS from 2OS
+add TOS to 2OS
*multiply TOS by 2OS
U.print TOS as an unsigned number
SPACEprint a space
DUPcopy TOS
DROPremove TOS
ABSreplace TOS with its absolute value
NEGATEreplace 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
SWAPexchange TOS with 2OS
DEPTHnumber of elements on stack
BEGINstart of BEGIN .. UNTIL structure
UNTILif TRUE, return to matching BEGIN
DOstart of DO .. LOOP structure
LOOPinc 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

Monday 16 February 2009

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:

InsDescription
:copy the top stack entry
!drop the top stack entry
~swap the top two stack entries
*join the top two stack entries
Sdisplay then drop the top stack entry
^drop then run the top stack entry
aenclose 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.

Friday 6 February 2009

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?

Sunday 25 January 2009

Brainf*** Interpreter in Redcode

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

InsMacroDescription
<ltmove pointer left
>gtmove pointer right
+incincrement memory cell at pointer
-decdecrement memory cell at pointer
.outoutput a character from the cell at pointer
,ininput a character and store in cell at pointer
[opjump past matching ] if cell at pointer is 0
]cljump 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

Sunday 18 January 2009

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

Friday 9 January 2009

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.

Tuesday 6 January 2009

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

Sunday 4 January 2009

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?