Corewar: Hostile Programming

Corewar is a game from the 1980's, played between computer programs written in Redcode, a language similar to assembly. The programmers design their battle programs to remove opponents from the memory of the MARS virtual computer by any means possible.

Some of the simpler techniques include blindly overwriting memory, searching for the opponent or spawning off new processes. These are commonly known as stone, scissors, paper after the popular playground game. Stone usually wins against scissors, scissors normally defeat paper, and paper mostly beats stone.

Here's an example of a typical Corewar program:

     org   wipe

     step  equ 5
     first equ bomb-10

bomb:mov.i #1,       -1

ptr: sub   #step,    #first
wipe:jmz.f ptr,      @ptr

     mov   bomb,     >ptr
     djn.f wipe,     {ptr-5

     end

This simple example of scissors once held a 20 point lead over it's rivals. The first instruction is never executed, it's the bomb used to overwrite opponents. The next two instructions form a loop which looks through memory for an opponent, and the final two instructions actually overwrite it.

Corewar is still going strong, and celebrates it's 25th anniversary in 2009. If you'd like to discover more about Corewar, here are the top resources:

• The Beginner's Guide to Redcode will teach you the language of Corewar


• pMARS is a portable implementation of the Corewar virtual machine


• Corewar Tutorials exist on virtually every aspect of the game


• Koenigstuhl is an archive of thousands of published Corewar programs


• SAL organises a number of on-going king of the hill tournaments


• sfghoul and impomatic report the latest Corewar news on their blogs


• #corewars is the official Corewar discussion channel, hosted by irc.freenode.net

What are your experiences with Corewar, have you ever had any success?

---

Corewar: Hostile Programming is a guest post written by John Metcalf.

nanoWarrior #03

The latest issue of nanoWarrior has finally been completed, containing articles by John Metcalf, German Labarga and me. Check it out for yourself here:

http://corewar.co.uk/nw/nw03.txt

Neo's Mini Challenge - Roy's Idea

Roy suggested a tricky extension to Neo's Mini Challenge in rec.games.corewar:

Lets try to find a solution for this gate:
djn.f #0,>-5
(I haven't got one yet)

It appears a one instruction solution isn't possible. However, 5 players found a solution in two instructions.  Congratulations to Ilmari, John, Rashnok, Roy and me! Also, well done to German and Lukasz who also discovered solutions, albeit slightly longer.

I discovered a five line imp:

imp mov.i #4,   *1
    mov.i #4,   *1
    mov.i #4,   *1
    mov.i #4,   *1
    mov.i #4,   *1

By adding a loop, I managed to reduce the initial size to two instructions:

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

John and Rashnok discovered the same 3 line imp and used a loop to reduce the size. Ilmari discovered a 2 line imp. Roy wrote a program to find 58 solutions by brute force!

Full details are on Neo's page for the Harmless Overrun Mini Challenge.

Thoughts on Corewar...

Thoughts on Corewar is John Metcalf's Redcode programming blog, hosted at http://impomatic.blogspot.com. Since John's blog was last reviewed, both the name and design have changed.

The standard template has gone and the sidebar now contains a selection of useful rss feeds, including the latest posts from rec.games.corewar and the most recent additions to the infinite nano and tiny hills.

The most interesting recent posts have been about Semaphores in Redcode, which provide a means of implementing mutual exclusing in Corewar.

What I liked:

• Covers advanced programming topics
• The feeds make it easy to keep up-to-date

Room for improvement:

• More comments on the code would be handy

tiny Twilight

Here's the code for Twilight, my most successful tiny warrior so far. When this entered SAL's tiny hill in 24th place two years ago, I didn't expect it to last long!

I'm surprised to see it's still on the tiny hill age 79. Currently it's in 10th place, the best position to date :)

;redcode-tiny
;name Twilight
;author S.Fernandes
;strategy oneshot v1

;assert CORESIZE == 800

; entered the hill on 12 Mar 2006 in 24th place
; still on the hill on 31 Oct 2008, age 79, 10th place

        org    scan
step    equ    24
gap     equ    6
first   equ    loop+step*5

ptr     dat    first+gap-1     ,  first-1

        dat    0     ,  0

x       dat    1     ,  9
clr     spl    #350  ,  12
        mov    *x    ,  >ptr
        mov    *x    ,  >ptr
        djn.f  clr+1 ,  }clr

        for    2
        dat    0     ,  0
        rof

loop    add    inc   ,  ptr
scan    sne    *ptr  ,  @ptr
        djn.f  loop  ,  *ptr
        djn.f  clr   ,  ptr
inc     dat    step  ,  step
        end

Neo's Mini Challenge - The Results

Neo's Mini Challenge is over and the results are in. Seven players entered, 6 of who discovered an optimal solution - 1 line, 1 process, 100% ties.

Neo and I entered the following code:

mov }0, }1

Ilmari and John entered this:

mov.i #1, *1

While Roy and Rashnok used a variation on the above:

mov.i #1, }1

Finally, mjp entered code which expands to a 6 line imp:

mov 2, @1
djn -1, #6
mov 0, >6

Roy suggested an interesting alternative which Neo will hopefully adopt as the next challenge.

Neo's Mini Challenge

After a break of four years, Neo has relaunched the Mini Challenges, starting with Harmless Overrun.  To take part, you need to write an imp capable of passing through an imp gate:

gate: jmp 0,<-5
end gate

The aim is to tie 100% of the time with the shortest possible code. Good luck to everyone taking part.

Miz's Corewar Page

A few days ago Mizcu moved his webpage to http://users.evtek.fi/~mikaos/corewar/, so now seems like an ideal opportunity to take a closer look.

The highlight of Mizcu's site is Monowire's story, the tale of a beginner's warrior.  Mizcu details the development of his oneshot from a beginner warrior to king of the KOTH.org '94nop hill.

Also in the Redcode section, Mizcu publishes some of his Corewar projects, including a generic table scan, Stoney the second and Lady Imperactive. Huffpaper includes an interesting variation to the standard silk concept.

Finally, there's an article about decoys which Mizcu is working on.  This covers the basics, active decoys, invisibility and will eventually include decoy makers.

What I liked:

• Monowire's story

Room for improvement:

• A few comments would make the code easier to understand

Will Varfar's Corewar Page

Will Varfar has a webpage devoted to Corewar at http://redcoder.sourceforge.net and shares some of his experiences implementing and testing Redcode simulators and evolvers.

Will's Which MARS report gives a thorough examination of different simulators, including some observations on their inner workings. The report concentrates on 6 open source MARS. It would be interesting to see the closed source simulators included in the comparison.

Species is Will's Redcode evolver, which attempts to improve on past evolvers with the introduction of species and chromosomes. Source code and a Windows .exe are available to download.

Some interesting statistics are published on Will's page. Will has gathered data about the frequency of opcode execution during a round robin of over 400k battles. Taking this one step further, graphs have been generated showing how the opcode frequency changes during a battle.

This data has been used to automatically divide the warriors into groups based on their execution fingerprint. It might be interesting to compare the results to those of Joonas's self organising maps.

Finally, there are a couple of article in which Will discusses the development of his entries for Neo's Mini Challenge #3 and Redcoder's Frenzy round 9.

What I liked:

• In my opinion, Will has the most visually attractive Corewar site
• 100% original content

Room for improvement:

• the 3d graph of Optimax benchmark stats is a bit tricky to interpret
  

Welcome sh0newars

A few days ago N. Ristic aka sh0ne joined the Corewar enthusiasts in the #corewars IRC channel and not only started learning the ropes, but created a website which will hopefully document his rise to Corewar fame.  sh0ne's page is at http://sites.google.com/site/sh0newars and is definitely worth keeping an eye on over the next few weeks.

Łukasz Grabuń's Book of Stones

Łukasz Grabuń has a small Corewar site at http://grabun.com/corewar.  Apart from a selection of useful links, Łukasz's site contains the Book of Stones which he describes as "a modest continuation to the second chapter of Steven Morell's book".

The first chapter has an analysis of Carbonite by Ian Sutton.  After describing Carbonite's bombing run and the switch to a clear, the interaction with an opponent D-Clear is examined in detail. Unfortunately, the advantage of the remote bomb and using add.ab {0,}0 in preference to add.ab -1,-1 are not mentioned.

Behemot by Michal Janeczek is discussed in the second (and final) chapter.  The article begins by introducing the airBag and incendiary bomb techniques before moving on to Behemot's inner workings and interaction with dat bombers.

What I liked:

• The Book of Stones

Room for improvement:

• The chapter about Carbonite doesn't mention a couple of important points

Tales from the Digital Wilderness

Tales from the Digital Wilderness is John Metcalf's Redcode programming blog, hosted at http://impomatic.blogspot.com.  Emphasis is given to implementing real algorithms in Redcode such as sorting and seaching.

John uses a standard Blogger template, with a post archive and a selection of useful Corewar links in the sidebar.  Usually there are 3 to 4 posts per month.

There are two Corewar related posts.  Parallel Processes describes a useful pMARS macro and An Improved '88 Quick-scanner shows how Paul Kline's technique can be used to create a 48 instruction '88 qscan which scans 36 locations.  The remainder of the blog is devoted to algorithms.

Some posts I found particularly interesting are Comb sort, Stooge sort and Gnome sort which I hadn't previously heard of.  Apart from sorting, there are implementations of seaching and number theory algorithms.  A post comparing the performance of the different techniques would be an interesting addition.

What I liked:

• A unique concept
• The code is well written

Room for improvement:

• For the more complex code, a detailed description would be nice
• A few comments would make the code easier to understand

Philip Thorne's Corewar Introduction

Philip Thorne's Corewar Introduction can be found at http://home.pipeline.com/~corewar and has been reporting the latest tournament news since 2002.  The homepage has a handy selection of links for Corewar beginners.

What really make's Phil's site stand out is the unique content.  There are two useful tools, RSS feeds for the KOTH hills and a Redcode syntax definition for VIM.  The RSS feeds are updated daily.

Phil's Stone Analysis article has a thorough examination of 13 stones, comparing everything from speed and coverage to the type of core-clear.  Unfortunately, I didn't understand all of the figures in the table - a key would be helpful.

Finally, Phil has published a selection of warriors.  The layout here is almost perfect!  The warriors are presented in an interactive tree structure and the warrior files are displayed with syntax highlighting.

What I liked:

• The Stone Analysis article
• The presentation of warriors

Room for improvement:

• A key to help interpret the Stone Analysis table

Neo's World of Corewar

Germán Labarga completely overhauled his website a few months back with a new URL, new design and updated content. The new location is http://labarga.atspace.com. The new layout is clutter free and easy to navigate.

Neo used to pose a programming challenge in Redcode every couple of weeks, and the results from the Mini Challenges are hosted here. There's also a selection of Neo's published warriors. This section could be improved a little by including some short comments.

The highlight of the site has to be the article documenting P-Key's Development. P-Key is an adaptive switcher which won the Smart Switching tournament round.

What I liked:

• The results from the Mini Challenges
• The article about P-Key

Room for improvement:

• Some brief comments on the warriors page would be nice
• The tools page needs more links (it currently has only one)