Analysis: Corewar - The Ultimate Video Game?

[In this special analysis, John Harris examines the competitive programming game of Corewar to pick apart its unusual design attributes and uncover lessons that modern game designers can learn from.] When we think of computer games, what is the image that comes to mind? Often, these days, it is something that involves a control pad or analog stick. It might instead have a keyboard and a mouse. There’s usually some kind of 3D graphics involved and some kind of soundtrack, and to facilitate those you’d need a monitor and some speakers. At a deeper level, there’s the presumption of interactivity, that something you do is countered by the machine, and then you do something to counter it, back and forth in an iterative fashion. And after all that, many people then go on to claim that the game requires some degree of something called immersion. But how many of those things is actually necessary? This month, we talk about an essentially computer-oriented game that relies upon absolutely none of these things: the awesome and unique game of Corewar. Introduction Corewar was first popularized in a series of articles printed as part of the Scientific American column "Computer Recreations," a successor of Martin Gardner’s legendary Mathematical Games. This puts it in the same kind of company as John Horton Conway's Game of Life, the prototypical cellular automata. It was created by the column's author A. K. Dewdney, and the columns themselves, linked above, are still a decent introduction to the game for programmers. My own description here is simplified by comparison; if you become further interested in the game, the linked columns are the best place to start. Corewar is a battle for survival between two or more opponents, all of whom happen to be computer programs. There is no monolithic shell to host the battles, the same tools are used to write them as one might write in C. These programs, or "warriors," are written in a language similar to assembly called Redcode, and are submitted to a MARS, or "Memory Array Redcode Simulator," a simulated computer that runs both programs in a shared memory space called the core. The programs do not manipulate vehicles in a physical system in an attempt to vanquish opposing vehicles, as with some other types of programming games. Instead, the programs try to directly destroy the opposing program by overwriting their code. A program thread dies only when it executes an illegal instruction or tries to divide by zero. A program wins when all opposing threads crash in this manner, and it loses if it, itself, is entirely crashed. The warriors take turns executing, first an instruction from one, then from the next, and so on until they've all run an instruction, then the queue starts over from the first. All instructions take the same amount of game time, one "cycle," to execute. As with ordinary machine code programs, after an instruction executes that program's instruction counter increases to the next instruction in memory. (In most traditional machine languages instructions consist of multiple memory locations, each comprised of a single byte. Under the Redcode system all instructions, including arguments, are only one memory location in size. The word "byte" is not used.) The warriors are loaded into memory at random locations before the match starts, and their counters set to the appropriate starting points. Memory is cyclical; programs falling off the end of memory wind up back at the start, and all accesses that overflow will similarly wrap around. The random starting points are an essential aspect of the game, and are the sole element of chance in the simulation. If a warrior always knew where to find its opponents it could crash one immediately by copying an unexecutable DAT instruction right over its initial instruction. Still, some warriors lash out and try to hit an essential memory location without taking the time to look first; these are called "bombers." Some other warriors, "scanners," look first and attack when they think they've found a competitor. Then there are warriors that copy their code elsewhere in memory in case of attack. There are a surprising wealth of strategies in what may appear at first to be a rather simple game. Competing programmers must strike a careful balance between size and complexity. The shorter a program is the harder it is to find and attack in the large core, but with fewer instructions the less nuanced its strategy can be. But a well-written long program can be faster than a short one because it doesn't have to waste time looping. Because keeping size down and speed up are so important, successful Corewar programs can be fiendishly elegant, and like many assembly programs, may be hard to read. Here are some additional quirks of the Redcode language of interest to programmers, so other readers may want to skip to the next paragraph....

Playing the game Because the act of playing consists solely of writing a warrior's code, watching battles and learning their results, this section is going to look over the sources of three prominent warriors from the game's earliest days, all drawn from the pages of Scientific American. Imp, written by A. K. Dewdney

MOV 0, 1
END

The oldest and simplest useful warrior, Imp is as short as possible, as fast as possible, difficult to attack, and surprisingly effective for its limitations. All it does is move the contents of the current location of the program counter (that is, itself) one space ahead. When its execution turn comes around again, it'll find the new copy of its sole instruction, which will then also be copied ahead. It will continue on like this forever unless stopped by another program, leaving a trail of MOVs behind it at a rate of one per cycle. When Imp reaches another program, it'll just bulldoze over its code with copies of itself. When a bulldozed program tries to execute its next instruction it'll find a MOV 0, 1 there, lobotomizing it, basically turning it into an Imp! And to destroy an Imp, a write must hit its current memory location, since it'll copy over whatever lies in front of it on its next turn. All these advantages come with a huge drawback however: Imp cannot win the game on its own. All it can do is copy self-perpetuating MOV instructions. It moves no DATs, which are the only way to halt an opposing program. An opponent who is Imp'd is just as hard to kill as Imp itself, so although it's doing no attacking it's still not dead, and so still has not lost. Because of this, unless a coding error causes the opposing warrior to halt accidentally, the best Imp can do by itself is tie. However, because it's short and easy to set up, Imps are a useful weapon for more sophisticated programs. Dwarf, original version by A. K. Dewdney, modified for modern Redcode by Ilmari Karonen. Obtained from The Beginner's Guide to Redcode.

ADD #4, 3 ; Adds a literal 4 to the value in the DAT, below, and stores the result there.
MOV 2, @2
JMP -2
DAT #0, #0
END

The DAT instruction here holds a pointer, initialized to zero. MARS provides no accumulator or registers, so all pointers and temporary storage must be kept in main memory. (Or in PSpace, but that's an advanced topic beyond the scope of this column.) Execution begins with the ADD instruction, which immediately adds a literal value of four to the B field three locations later in memory, that is, the second value of the DAT. The MOV then copies the DAT instruction to the location pointed to by the DAT's B field. After that, it loops back to the ADD. In this way, it methodically peppers memory with walls at four-location intervals. Since it drops its mines quickly without checking first, Dwarf is classified as a bomber. It can drop a mine every three cycles, which means it extends its reach faster than Imp, but it leaves holes through which a very small program, like Imp or another Dwarf, might slip. In fact this is by design, since if it didn't do this Dwarf would bomb itself when the pointer came back around through memory. Since Dwarf is only four locations in size, the DAT copy will neatly miss all of Dwarf's executable code. Take note of two things: one, the core is initialized with DAT 0, 0 instructions, so the last line is actually unnecessary. And second, under modern Redcode, the ADD could be used on the MOV instruction directly, removing the reliance on one more memory location. Self-modifying code is not a sin in Redcode. Programs are always getting changed at runtime, whether on purpose, due to opponents, or accidentally. In fact, making use of it can help keep code sizes down, reducing vulnerability. In Redcode, no instruction can modify more than one memory location at a time, and the most locations that can be read, using compare instructions, is two. It takes extra instructions, and more time, to make sure a location contains an opponent before writing to it. Dwarf uses up a lot of time bombing empty memory, but it takes about as much time to find opponents as to attack, and the process of searching looks a lot like bombing anyway, just with compares instead of writes. There are programs that take advantage of the fact that compare instructions reference two locations to each other to effectively search twice as fast, and there are even programs that copy themselves around specifically so those comparisons will find identical contents waiting for them. Mice, written by Chip Wendell

ptr:  DAT #12
prg:  MOV #12,     ptr
loop: MOV @ptr,    (The listing above, which I won't step through, is the original version written in Redcode '86.)

Mice is classified as a replicator. It makes a copy of itself to another location in memory, then forks execution to it with a SPL instruction. The old copy then starts making another copy, while the new copy makes a copy of itself.  This continues until memory is filled with copies of Mice, the reasoning behind its name hopefully obvious by now.

When a program splits execution the task of the opposition becomes substantially harder, since all threads must be terminated before victory can be declared. It should be noted, though, that Mice does not gain speed with its many additional copies. When a warrior splits execution, its various threads must take turns with each other for execution time. So if there's three Mice running around the core, but an opponent only has a single thread, then that thread is operating three times faster than each individual copy.

Mice does gain longevity with its endless self-copying, since only one Mice has to survive to continue the battle, which propelled it to victory in the first Corewar tournament, held back in 1986 in the days before the internet.

Beneath the Surface

There are three primary tactics in Corewar strategy today, roughly corresponding to (and named after) the throws in a game of Rock-Scissors-Paper:

Replicators like Mice are called "papers" in Corewar lingo. They get their power from the longevity provided from having many threads running at once, and from being able to work on different things at once. With many copies in operation, the task of the opposition becomes that much harder, although each individual thread operates more slowly.

The best way to beat replicators is by using a scanner, also called a "scissors," a program designed to look for replicators and hunt down their many threads. One way to do this is by, instead of bombing each copy with a DAT instruction once found, to instead hit it with a SPL 0 instruction, causing it to endlessly generate useless threads and drag its execution down even further. The advantage here is only one thread must be found in order to be effective; the more copies there are in the core, the easier it is for the attack to hit.

Scanners must be fairly long in order to house the logic needed to hunt down replicators, making them vulnerable to bombers like Dwarf, which take the name "stones." But bombers, while fast, will often lose to replicators and their many hard-to-kill threads, completing the triad.

There are many variants of these types too, going by exotic names such as imp spirals, vampires and quickscanners.  They're detailed at the Wikipedia entry for Corewar.

What Can We Learn From Corewar?

First: computer games can come in all shapes and sizes  Corewar is a game that is sometimes played without even a UI, with only the results of matches presented to a user. It is work done for the sake of enjoyment. There is nothing interactive or immersive about it.  

But what makes the task of playing this unusually studious game fun? Part of it is something that is easy to forget, sometimes: the act of programming, itself, can be fun. This is why people do insane things like hack Linux kernels as a hobby, in their spare time; these crazy folk actually like it.

But in order to create a game in which developing solutions through programming is the objective, the people creating the game must foresee all of the outcomes and make sure the tasks are possible and balanced, a task tantamount to being smarter than all the players who might play it.

This, itself, is impossible, especially when they collude through avenues such as message boards and FAQs.  Corewar's solution, then, is to pit players against each other, making those opponents into the "designers" a player is pitted against.

A system like that requires a certain degree of open-endedness and richness, and it is by no means simple to create.  Care must be taken that the first side to act (or second for that matter) cannot act upon it to immediately win, or receive some overriding advantage.

Corewar's rules are carefully balanced so that a warrior's resources may change from moment to moment, but do not actually increase or decrease. Splitting execution reduces the number of instructions each thread can process.  Longer programs can utilize more complex algorithms, but are easier for other programs to find or bomb.

The fascinating thing about this balance is that it comes about by taking the behavior of real processors from the time of its creation as an analogue. The limitations of those processors match up nicely with the limits on warriors executing in a MARS.

Appendix: Getting Involved in Corewar

Corewar has declined in popularity since its introduction in Scientific American but people still play it today.

Here are those Scientific American articles, once again.

More basic information can be found at the rec.games.corewar FAQ.

For personal simulation, the two most popular simulators for running the game are pMARS, for many OSes, and CoreWin for Windows.  A Corewar battle taking place on a modern computer, it must be said, goes by almost faster than the eye can see unless it has been slowed down.

A good number of tutorials for the game can be found on this tutorial links page.

One of the most interesting ways to play is by participating on "hills," automated, perpetual Corewar tournaments scattered around the internet.  One will typically upload or email his warrior's source code to the hill, which will then be scheduled for playing against the warriors already there.  When its turn comes up, a large number of trial matches is staged between it and each of the ranked opponents, and score is kept.  When the matches are complete, its score is compared with that of the other warriors.

If the new program ranks above one of the others, it'll be placed as the new warrior at that slot and those at and below that level pushed down.  The lowest is bumped off.  There are also "infinite" hills, which don't bump anyone off but continue ranking new warriors indefinitely.  A beginner's hill, which automatically removes warriors who remain on the hill for a period of time, can be found here.

An interesting thing about Corewar is that some genetic algorithms, given enough iterations, do a good-enough job of writing programs for it that they occasionally win tournaments.  It might have something to do with the value placed on brevity and the relatively low number of opcodes (although there are plenty of addressing modes to make up for it).  The Corewar Info page has a listing of useful tools in this area.