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

nanoWarrior Issue 3

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

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

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

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

Enjoy the issue.  Any feedback would be greatly appreciated.

Mini Challenge #7 - Results

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

Mini Challenge #7 - Part 1

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

Roy van Rijn and Rashnok found the following solution:

    mov.i #1, }1

Neogryzor and S. Fernandes discovered the following:

    mov }0, }1

And finally, Ilmari Karonen and I entered the following:

    mov.i #1, *1

Mini Challenge #7 - Part 2

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

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

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

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

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

I also entered a slight variation:

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

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

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

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

Thanks to Neo for organising the challenge.

Roy's Modification to Mini Challenge #7

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

djn.f #0, >-5

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

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

Mini Challenge #7 - "Harmless Overrun"

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

jmp 0, <-5 

For more details, see the mini challenge homepage.

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.

Replicate - My First Corewar Warrior

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

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

An Improved '88 Quick-scanner

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

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

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

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

qi  equ 7                       
qr  equ 7

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

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

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

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

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

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

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

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

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

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

pgo
end qgo

x^n (mod CORESIZE) in Redcode

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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?

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

1. 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.
2. To show corewar is alive and well in 2008!