Saturday, 22 October 2011

Koenigstuhl Top 20: Where Are They Now

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 RankWarriorAuthor2011 Rank
1Pattel's VirusBen Ford8
2Recycled BitsDavid Moore12
3CombatraDavid Moore4
4Self-Modifying Code v0.11Ben Ford22
5Self-Modifying Code v0.10Ben Ford25
6QuicksilverMichal Janeczek76
7UninvitedJohn Metcalf88
8Recycled Bits--David Moore93
9Tuesday AfternoonJohn K W139
10Fire and IceDavid Moore94
11RecoveryIan Oversby97
12ReindeerIan Oversby141
13Three MusketeersRobert Macrae157
14The StormbringerChristian Schmidt133
15Am I alive?Christian Schmidt166
162 CrazyChristian Schmidt189
17Digitalis 4Christian Schmidt198
18Bigger BrotherPhilip Kendall58
19Liquid PaperSean McDonald109
20Origami Harquebusmjp49

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

Tuesday, 27 September 2011

Whirl: '88 qscan -> oneshot

Whirl is a qscan -> oneshot which recently entered the '88 hill.
;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
        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

Thursday, 11 August 2011

The Second ICPC

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

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

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

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

Friday, 1 July 2011

A Brief Introduction to Core War

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

Top Corewar Links

  • Beginners' Guide to Redcode
    Ilmari's guide to Redcode provides a gentle introduction to the art of Corewar.
  • Corewar Bibliography
    The Corewar Bibliography is a comprehensive index of Corewar articles and the ideal starting point to research any Corewar topic.
  • Corewars - King of the Hill is the provider of several online hills. Submit your program by email to compete against others.
  • KOTH@SAL Corewar Hills
    The hills at SAL present some alternative settings, including the beginner hill and the popular nano hill.
  • CoreWar "Koenigstuhl" Page
    Koenigstuhl is the Valhalla of Corewar! When an author publishes their battle programs, they're archived on the Koenigstuhl infinite hills.
  • Programming in Corewar
    In Corewar a battle is played out between computer programs, which attempt to eliminate all opponents within the memory of the MARS virtual computer.
  • Fizmo's Corewar Info
    The ultimate source for any information regarding Corewar, a programming game where small programs fight each other.

Thursday, 10 February 2011

An Early Description of Core War

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?

Monday, 17 January 2011

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.

;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 @plot,    direct
        div    #2,       @plot
        mod    #2,       test
        jmz    test,     test
        mod.a  #4,       direct
direct  add.b  3,        width+1
count #65536,   #1+1
        jmp    dragon,   -width+1

Sunday, 9 January 2011

Dragon Curve in Redcode

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.

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