Wednesday 24 December 2008

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

Sunday 7 December 2008

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

Wednesday 19 November 2008

nanoWarrior Issue 3

corewar | nanoWarrior 3The 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.

Tuesday 11 November 2008

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.

Tuesday 21 October 2008

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!

Friday 17 October 2008

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.

Saturday 11 October 2008

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

Monday 29 September 2008

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.

Tuesday 1 July 2008

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

Saturday 31 May 2008

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

Wednesday 14 May 2008

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

Monday 28 April 2008

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

Sunday 20 April 2008

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

Saturday 12 April 2008

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

Thursday 3 April 2008

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

Wednesday 19 March 2008

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

Saturday 8 March 2008

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

Tuesday 4 March 2008

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

Wednesday 27 February 2008

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

Monday 25 February 2008

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.

Tuesday 19 February 2008

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

Tuesday 12 February 2008

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

Thursday 31 January 2008

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

Sunday 20 January 2008

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

Wednesday 16 January 2008

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.

Monday 7 January 2008

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

Saturday 5 January 2008

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

Friday 4 January 2008

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.

Thursday 3 January 2008

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!