April 1, 2008
Our old pal A. K. Dewdney first introduced the world to Core War in a series of Scientific American articles starting in 1984. (Full page scans of the articles, including the illustrations, are also available.)
Core War was inspired by a story I heard some years ago about a mischievous programmer at a large corporate research laboratory I shall designate X. The programmer wrote an assembly-language program called Creeper that would duplicate itself every time it was run. It could also spread from one computer to another in the network of the X corporation. The program had no function other than to perpetuate itself. Before long there were so many copies of Creeper that more useful programs and data were being crowded out. The growing infestation was not brought under control until someone thought of fighting fire with fire. A second self-duplicating program called Reaper was written. Its purpose was to destroy copies of Creeper until it could find no more and then to destroy itself. Reaper did its job, and things were soon back to normal at the X lab.
(The story of Creeper and Reaper seems to be based on a compounding of two actual programs. One program was a computer game called Darwin, invented by M. Douglas McIlroy of AT&T Bell Laboratories. The other was called Worm and was written by John F. Shoch of the Xerox Palo Alto Research Center. Both programs are some years old, allowing ample time for rumors to blossom.)
Core War, surprisingly, is still around. The current hub appears to be at corewar.co.uk. You can download simulators for a variety of operating systems there. Here's how a Core War battle works:
Core War has four main components: a memory array of 8,000 addresses, the assembly language Redcode, an executive program called MARS (an acronym for Memory Array Redcode Simulator) and the set of contending battle programs. Two battle programs are entered into the memory array at randomly chosen positions; neither program knows where the other one is. MARS executes the programs in a simple version of time-sharing, a technique for allocation the resources of a computer among numerous users. The two programs take turns: a single instruction of the first program is executed, then a single instruction of the second, and so on.
What a battle program does during the execution cycles allotted to it is entirely up to the programmer. The aim, of course, is to destroy the other program by ruining its instructions. A defensive strategy is also possible: a program might undertake to repair any damage it has received or to move out of the way when it comes under attack. The battle ends when MARS comes to an instruction in one of the programs that cannot be executed. The program with the faulty instruction -- which presumably is a casualty of war -- is declared the loser.
Let's see it in action using one of the simulators. What you're watching here is a round-robin tournament between the Imp [yellow], Mice [blue], Midget [white], and Piper [green] programs.
The winner is Piper [green], with 2 wins, 0 losses, and 1 tie.
These programs are written in an assembly-like dialect known as Redcode. Here's the source code for Midget:
;author Chip Wendell
;strategy stone (bomber)
;history Third place at the 1986 ICWS tournament
Bomb dat #0, #-980
Spacer equ 28
Start mov Bomb, @Bomb
jmp Start, #0
The Redcode instruction set is deliberately simple. There are two variants, ICWS-88 with 10 instructions and 4 addressing modes, and ICWS-94 with 19 instructions and 8 addressing modes.
decrement and jump if not zero
move / copy
skip if equal
skip if not equal
skip if lower than
load from private space
save to private space
jump if zero
jump if not zero
It's structured so that there is no "killer app"; three broad strategies are possible, each with its own strengths and weaknesses.
- Paper or Replicator
Try to fill the core with copies of your program, so you are harder to kill.
- Rock or Bomber
Attack by writing illegal instructions throughout the core-- but not on your own program's memory.
- Scissors or Scanner
Attempt to identify enemy programs lurking in the core, then target writes to eliminate them.
Of course, combinations of the above strategies are possible as well. As you might imagine after 25 years of battlefield evolution, some modern Core War programs are quite baroque by now.
It's not particularly useful, but it is a programming game, after all. It's also a fascinating bit of computer science history. If you're interested in participating in the venerable sport of Core War, it's still very much alive and kicking. The top 10 links for Core War newbies is a great place to get started.
Posted by Jeff Atwood
Another great post.
I was never to impressed by this kind of programing, but now I will give it a try.
Code wars here I come!
I usually lurk through, don't comment, but thanks for reverting back to the old theme.
The 'Matrix' theme was not very professional, though it showed that this is a geek's blog. Hard on the eyes.
Thanks for the responses, I do not think that the mov current current+1 would work to end in anything but stalemate.
However, depending on the instruction set a variant would work if it was:
movdoubleword current current+1
I find this interesting because:
I once tried to write a program like mov current current+1 on a motorola processor, but it was not possible because the move double word instruction was a double word itself and the operand was a word. So, I would have needed a move triple word, which did not exist:) And of course the move word instruction was 1 word + a 1 word operand.
For a more modern programming game, check out BitBath (http://www.hacker.org/bitbath/).
Armies of bots fight in a virtual battlefield, capturing cities, navigating terrain, and communicating over radio.
This game uses a custom JVM, which means it's the only programming game in existence that both uses a modern programming language (Java) and has precise instruction counting (crucial for ensuring fairness and reproducability.) It's also a lot of fun!
Thanks Jeff for another thing I learnt from your blog. I will try core wars.
I was fiddling with this just the other day. It certainly teaches you how to write fault-proof code ;)
Cool to see an easy implementation of Assembly, "deliberately simple", and quite intuitive... the way it should've been, regarding the naming convention.
Someone now needs to make a CoreWar facebook app.
Commercial success guaranteed.
Corewar facebook app! Finally a good facebook idea..
Reminds me of Terrarium: showcase .NET application. It was higher level then core wars, creatures were graphical and underlying code had functions like bite(), eat() and look(). You upload your dll to server and watch your creature perform.
It can still be found at http://windowsclient.net/Terrarium/default.aspx
Ever heard of IBM's Robocode?
Wow. I played Core Wars for a while about five years ago, but never was very good at it. Even my best warrior couldn't get past 5th on the beginner hill. But it was a lot of fun, and I learned a lot about assembler (even though redcode is a toy language).
Please please change your color scheme back to the old one :)
I thought it was just an April 1st Joke but you seem to be serious. This is hardly readable :-(
I was just about to post the same thing. Try a CTRL-F5 to refresh the CSS and it should be back to normal.
Ahh, I've been looking for something useful to put my assembly skills to use on (and by 'skills' I mean 'small amount of experience').
Perfect. Thanks, Jeff.
Robocode is the way to go. Its like Battlebots on the computer.
That is a fascinating field.
The best corewar program I have ever seen is Firefox2.
If it is running, you cannot run anything else.
Brings back memories. Trying to write original material for CoreWars that actually worked mainly just made me feel stupid. Still, it's fun to watch.
It is in Java.
You have tanks/robots driven by your own algorithms to fight other robots on the battlefield.
You can have team battles, where a number of your robots work as a team to beat the other team.
That is a lot of fun, and good starting place for those who want to learn Java. Bare minimum java/programming experience needed to start building your own robots.
what about DarwinBots?
anyone tried that?
The programs evolve too.
The _Carnage Heart_ series for the PS1 has a similar scope to Core Wars, except the programming is done graphically and is used to run robots which battle in various environments.
It's one of those games that I was amazed was ever released, high critical regard but absolutely zero mainstream appeal. I'd _really_ like the new PSP version to be ported to English sometime soon though :)
Dr. Ofria at Michigan State University runs the DevoLab ( http://devolab.cse.msu.edu/ ). His introduction to the lab begins with a story about Core Wars and how the best programs often 1) copy themselves and 2) copy themselves, but not perfectly, leaving slight mutations.
The lab is now dedicated to studying the mechanics of evolution in swarms digital organisms which compete for resources and space.
I was happy to see Core Wars pop up again. Thanks.
Thanks a lot for this blog entry and the links. I didn't know Core War was actually still around.
I became interested in Core War while reading the Hyperion Cantos by Dan Simmons which has some rather interesting ideas growing out of Core War and Tierra, the research of Tom Ray, a biologist (!). Incidentally, I highly recommend the books. One of the coolest far-future epics ever written.
Interesting blog! I wonder if there might be real world applications for such programs?
P.S. I hope the new look is just a fad or a passing bout of angst.
Jeff, I vote on leaving the April 01 stylesheet as an alternate on the site :)
I vaguely remember playing that when the apparent killer app (won like 95% of the battles for me) was a simple "MOV current current+1". It would just copy this single instruction into the next memory slot, which it then would move on to, only to repeat, etc. How did they fix that ?
I'm going to have to give this one a shot, I've been playing RoboCom (http://www.cyty.com/robocom/) which is very similar in concept and highly addictive. It's hard to explain without just watching a sample round but it seems to be a great combination of Code War and Robocode, with "robots" infecting other "robots" with software viruses, replicating, or even just reprogramming the others to work for them. It's great fun!
Another pair of programming games that are very entertaining: AT-Robots (http://necrobones.com/atrobots/) uses an assembly style language and lets you control a single tank against a field of competitors.
The best programming game, IMHO, is Grobots (http://grobots.sf.net). Pronounced Grow-bots, this adds some very different aspects to the programming game genre. First is food, you need to obtain it to have enough energy to run. Second is reproduction, the robots (or cells is a better description) can make more robots. Its no longer about a single unit, but controlling an entire colony of robots. Very challenging, very fun. Uses a forth based language.
These competitions sound like a lot of fun. :-)
@Shaun Austin: Thanks for the CSS refresh tip. Worked like a charm! I can actually read the posts here. :-)
I know this is off topic, but I've got to beg you to change your site design back to something more readable. My eyesight is not up to reading this greed on black and I think it will put other people off too. I will not be reading this site on this design because it is far too much strain, but I hope ikt goes back to something easier to read soon.
jeff, how are you doing the server side caching for this site? even though i set my browsers to check new content on every visit, i still have to hit ctrl+f5 to see new comments, or visual changes.
Indulge me, I do not understand how this wins the game:
MOV current current+1
It seems like it will turn all the other users into bots that do the same thing as yours, but never cause the other programs to execute an illegal instruction.
It seems like it would fill the memory space up with instructions that were all legal, leading to a stalemate.
To all who oooh-and-aaah about real world uses of CoreWar, just a quick reminder: viruses, worms and trojans are a "social" form of corewar programs. We need more of those. Maybe the dudes at Microsoft should wrap their mind around the idea too. We might get fewer security holes.
CoreWar is a great pursuit. Its exploitation in the real world isn't.
The main idea behind writing core war programs is to write code that can modify itself and remain functional. By "functional", I mean it needs to "bomb" other code and stop it from executing and "bombing". Whoever kills other program(s) first, wins.
Self-modifying code, anyone? VB crowd? I thought so.
Now I want to write a program to display a picture of Tina Turner.
I remember a more intensive game also called "Core Wars". Basically, you set up a LAN with one machine for each player, and all that was installed on each was a bare bones OS, and network. The OS was agreed upon by all players, and all have the exact same OS, version etc. (could be UNIX/Linux, Windows, VMS, etc.) No security of any type was set up on any machines. The network was local only. No outside connection. The object of the game was to crash or cripple your opponents machines, while setting up your defenses (system security, firewalls and so on), but you aren't allowed to take yourself off the network. You had to plan your strategies well in order to hit your opponents while their security was down, and minimize the risk to your system enough for you to carry out quick attacks. Last machines standing WITH a network connection went to the next round.
There was usually one machine set up as a monitoring station, which had full security to prevent it from being taken down. Any players machine that failed to respond to the monitor was considered killed.
A variation was to have another box set up as a network server (with or without security, depending on player prefs). The server would contain various software goodies that could be used to augment your security, or more sophisticated attack software to use as weapons. Players could also take down the storage server to prevent opponents from getting the bonus software.
That's the "Core Wars" I remember, but I have never seen it mentioned anywhere. Does anybody else remember this?
I like the green on black text, I read some stuff that said it is supposed to be easier on the eyes.
How do I get it back?
Actually, I'm taking part in organizing a contest that is very similar to Core War.
As part of the Israeli CodeGuru contests (www.codeguru.co.il) for teenagers there's a competition called CodeGuru Extereme, where participants write assembly code that is then ran in the competition in an arena, with all kinds of interesting twists. =)
"I like the green on black text, I read some stuff that said it is supposed to be easier on the eyes."
I find that it strongly depends on the environment.
While sitting in a bright/well-lit room, black text on white background really is easiest for me to read. But, if the monitor's brightness is significantly higher than ambient lighitng, then trying to read dark text on a light background gives me a headache - like trying to read the fine print on a lightbulb while its on.
"...To all who oooh-and-aaah about real world uses of CoreWar, just a quick reminder: viruses, worms and trojans are a "social" form of corewar programs..." So sayeth Sam on April 2, 2008 10:01 AM.
Yes, Sam (oh, mighty disparager of VB), we know about viruses, etc. Nonetheless, a big thank you for pointing out the obvious. Perhaps in the real world, anti-virus apps could employ some ideas from core war champs...
"MOV current current+1" copies the currently running instruction into the next memory location. When the instruction is not JMP, the next command in memory is then run. Thus, it is a one-line program that copies itself into the entire memory space. (Redcode uses a circular memory space, so it loops around at the end.)
It's hard for a bomber to defeat that program, since it replicates on every single instruction. The only way to defeat it is for the opponent to overwrite the just-written instruction right before it is run.
Since the programs take turns on every instruction, a sophisticated program typically doesn't have time to do anything before being overwritten by a simple one.
This is all very well and good, until someone hooks this thing up to NORAD's missiles and bombers. I bet it'll decide our fate in a nanosecond.
You are correct. That program is the Imp and it never wins it only leads to stalemates. It just writes the whole core to move instructions and so it becomes nearly impossible to kill, but yet it can't win either.
Core Wars and the derivatives some people mentioned got me thinking of a neat little project... maybe genetic programming can be used to create a better competitor.
This is really nice, RoboCode is even better :D.
Thanks alot for bringing that up
how come we dont hear about such things these days? i think this one for me was a coincidence!
wow, I'm going to show this site a friend!
I'm dissappointed I couldn't be the fist one to plug the avida project (devo lab). The moment I saw an article on code wars I got so excited that it might be on avida.
I'll never forget the the final lecture in my compilers class when I first saw Prof. Ofria's presentation on Avida. It is still by far the most incredible thing I've ever seen in computing. Programs that can reproduce and evolve just like biological organisms? Wow and that's just the beginning of the complex phenomonon studied by this project!
Then, years later, I even got a double dose when Dr Pennock talked about Avida in his presentation on the Kitzmiller v. Dover Area School District case in which he testified.
Oddly enough, I was just thinking about those old Scientific American articles. I started reading some of them in 1987 to 1988 time-frame. At that time I had a Commodore C128 and it really was fun to read the articles. Oh the memories!!
I wonder how many virus/worm/trojan programmers cut their teeth reading these articles.
*Snathi, Windows didn't exist when this codewar was written about. So this is not the codewar you're thinking of....and these are not the driods you are looking for.
Some comments from a reddit post that I thought deserved to be echoed here:
* there's no mention of redcode's rich addressing modes (8 in the last revision)
* there are two variants with different opcode sets, redcode'88 (ICWS-88) and ICWS-94; the latter adds multi-processing and state saved across runs (so the warrior can choose the best strategy based on previous outcomes)
* there are several hills with different opcode sets and core sizes. AFAIK the most popular ones are hosted at koth.org.
* the three basic strategies he lists (paper, stone, scissors) are not the only fundamental ones; you could add at least imp(-spiral)s, and vampires which trick the opponent's process(es) into executing your code
* you can see the evolution of the state of the art in the Core Warrior newsletter (http://corewar.co.uk/cw/)
This is incredible. Thanks for exposing me to it.
Whats with the green and black layout. I thought that was an April's Fools joke but it is still there. It is so hard to read, not to mention that it is annoying. You more than others should understand human factor and UI conventions. And the convention is that people are used to read black on white. Could you please provide an alternative style at least.
My bad. It was simply cached in the browser.
Hey, I sent your article to my Digital Logic teacher, it seems he will a CoreWar with FPGA, we will build a processor implement it in a FPGA and then play CoreWar in it. Very cool, thanks Jeff.
I'm loving this idea - I haven't tried it out yet but I've downloaded it for when I have a spare hour or so... I've tried many "bot battle" things in the past seeking programming "victory", but they've never been that satisfying. I get the feeling this will be a little different!
Thanks for the suggestion Jeff!
I remember I read a book a long time ago. The author (I don't remember his name) gave Dewdney the "honour" of invent the computer viruses. He said that some time after the Core War game was introduced, the first actual viruses came out. I don't know if it's historically exact.
Hehe, remembers me the time back 1993 when I wrote a core war simulator with my cousin in Turbo Pascal. But writing the simulator was much more exciting than writing red code programs.
Sorry about that, Corewar folk are getting lazy when it comes to preparing newsletters :(
There's also a newsletter specific to the nano hill:
Ah, corewars is very cool. I always was too dumb to develop my own warrior, so I wrote a program that uses genetic programming to create warriors automatically. Thats easier :-)
One year, Core War was a problem on the ACM programming team competition. Our team opted not to attempt it, but it looked cool.
Looks tasty, although I'd probably add the carrots a good fifteen minutes before the cabbage.
J.Stoever: "I vaguely remember playing that when the apparent killer app (won like 95% of the battles for me) was a simple "MOV current current+1". It would just copy this single instruction into the next memory slot, which it then would move on to, only to repeat, etc. How did they fix that ?"
That's the Imp. I find it hard to believe that it won 95% of the battles for you; most of the time it will result in a tie, since the opposing program gets "converted" into an Imp as well, and as soon as control gets transferred, it will do exactly the same thing your Imp just did. You need DATs to guarantee a win.
David: Imps may be hard to hunt, but they are VERY easy to trap, and a trap is also only 1 instruction. Your explanation isn't right either; not only does an imp not replicate itself on every instruction, it doesn't replicate itself at all (it just moves around). Replicating, in the sense of having an "extra life" if you execute an illegal instruction, requires an SPL. A nave imp never does this, so as soon as it hits a gate, the entire program is dead because it only has one process.
Maybe a long time ago those things could win or tie, but they're not very effective now unless you use a few different kinds and spawn a whole bunch of them (which of course takes away from the simplicity and tiny size).
It's really not so simple. If it were, they would have declared the competition over a long time ago.
Code/Programs that learn? Sounds like Skynet.
It became self aware on August 29 , 1997...
I've heard about core wars before, but this post did inspire me to look it up again. While I've always thought the idea core wars was pretty cool, I've clicked through the links and the scene looks pretty moribund. For example, the last installment in the core wars newsletter was in May 2007. A pity. But understandable, given this is a game that's been going on since 1984 or so.
Some idiot forgot to upgrade the GLIB and GTK+ dependencies for Linux.
`vim configure`, here I come...