Core War

From Wikipedia, the free encyclopedia

Jump to: navigation, search
A game of Core War running under the pMARS simulator, as seen through the graphical core display.

Core War (or Core Wars) is a programming game in which two or more battle programs (called "warriors") compete for the control of the "Memory Array Redcode Simulator" virtual computer ("MARS"). These battle programs are written in an abstract assembly language called Redcode. The object of the game is to cause all processes of the opposing program(s) to terminate, leaving your program in sole possession of the machine.

Contents

[edit] History

Core War was in part inspired by a game called Darwin, written by Victor A. Vyssotsky, Robert Morris Sr., and M. Douglas McIlroy at the Bell Labs in the 1960s. The word "Core" in the name comes from magnetic core memory, an obsolete random access memory technology.[1] The same usage may be seen in other computer jargon terms such as "core dump".

The first description of the Redcode language was published in March 1984, in Core War Guidelines by D. G. Jones and A. K. Dewdney.[2] The game was introduced to the public in May 1984, in an article written by Dewdney in Scientific American. Dewdney revisited Core War in his "Computer Recreations" column in March 1985,[3] and again in January 1987.[4]

The International Core Wars Society (ICWS) was founded in 1985, one year after Dewdney's original article. The ICWS published new standards for the Redcode language in 1986 and 1988, and proposed an update in 1994 that was never formally set as the new standard.[5] Nonetheless, the 1994 draft was commonly adopted and extended, and forms the basis for the de facto standard for Redcode today. The ICWS was directed by Mark Clarkson (1985–1987), William R. Buckley (1987–1992), and Jon Newman (1992–); currently the ICWS is defunct.[6]

[edit] Redcode

0000:  ADD.AB  #   4, $   3
0001:  MOV.F   $   2, @   2
0002:  JMP.B   $  -2, $   0
0003:  DAT.F   #   0, #   0

Assembled ICWS-94 style Redcode

Both Redcode and the MARS environment are designed to provide a simple and abstract platform without the complexity of actual computers and processors. Although Redcode is meant to resemble an ordinary CISC assembly language, it differs in many ways from "real" assembly:

  • Redcode has very few operations — 10 in ICWS-88 and 18 in ICWS-94.
  • Each assembled instruction is divided into an instruction code and two numeric fields. No numeric value is defined for the instruction code. The code may only be copied as part of an entire instruction, and may only be compared for equality.
  • Besides the opcode and two numeric operands, ICWS-94 allows each Redcode instruction to have a modifier that defines the size (one field, both fields, or entire instruction) of the data that the instruction operates on. Additionally, each of the numeric fields has associated addressing mode. ICWS-88 defines 4 addressing modes, and ICWS-94 extends this number to 8.
  • Each Redcode instruction has the same length and takes the same time to execute. The memory is addressed in units of one instruction.
  • All numbers are unsigned (i.e. non-negative) integers less than the size of the memory. Therefore there is a one-to-one correspondence between numbers and memory locations. All arithmetic is done modulo the size of the memory.
  • Only relative addressing is used. That is, address 0 always refers to the currently executing instruction, address 1 to the instruction after it, and so on. Addresses past the end of the memory wrap around to the beginning. This way, a program cannot (and need not) know its absolute location in the memory.

Each program can also have several active processes, each having its own instruction pointer. Each program starts with only one process, but others can be created with the SPL instruction. The processes for each program execute alternately, so that the execution speed of each process is inversely proportional to the number of active processes the program has. A process dies when it executes a DAT instruction or performs a division by zero. A program is considered dead when it has no more processes left.

[edit] Strategy

 This article may contain original research or unverified claims. Please improve the article by adding references. See the talk page for details. (November 2008)

Warriors are commonly divided into a number of broad categories, although actual warriors may often combine the behavior of two or more of these. Three of the common strategies (replicator, scanner and bomber) are also known as paper, scissors and stone, since their performance against each other approximates that of their namesakes in the well known playground game.[7]

  • A replicator (or paper) makes repeated copies of itself and executes them in parallel, eventually filling the entire core with copies of its code. Replicators are hard to kill, but often have difficulty killing their opponents. Replicators therefore tend to score a lot of ties, particularly against other replicators. The earliest example of a replicator is Mice by Chip Wendell.[8]
    • A silk is a special type of very rapid replicator, named after Silk Warrior by Juha Pohjalainen. Most modern replicators are of this type. Silk replicators use parallel execution to copy their entire code with one instruction, and begin execution of the copy before it is finished.[9]
  • A bomber (or stone) blindly copies a "bomb" at regular intervals in the core, hoping to hit the enemy. The bomb is often a DAT instruction, although other instructions, or even multi-instruction bombs, may be used. A bomber can be small and fast, and they gain an extra edge over scanning opponents since the bombs also serve as convenient distractions. Bombers are often combined with imp spirals (see below) to gain extra resiliency against replicators. The second published warrior in Core War history, Dwarf by A. K. Dewdney, was a bomber.
  • A scanner (or scissor) is designed to beat replicators, usually by bombing memory with SPL 0 instructions. This causes the enemy to create huge number of processes which do nothing but create more processes. This slows down useful processes. When the enemy becomes so slow that it is unable to do anything useful, the memory is bombed with DAT instructions.
    • A scanner doesn't attack blindly, but tries to locate its enemy before launching a targeted attack. This makes it more effective against hard-to-kill opponents like replicators, but also leaves it vulnerable to decoys. Scanners are also generally more complex, and therefore larger and more fragile, than other types of warriors.[10] He Scans Alone by P. Kline is an example of a strong scanner.
    • A vampire or pit-trapper tries to make its opponent's processes jump into a piece of its own code called a "pit". Vampires can be based on either bombers or scanners. A major weakness of vampires is that they can be easily attacked indirectly, since they must by necessity scatter pointers to their code all over the core. Their attacks are also slow, as it takes an extra round for the processes to reach the pit. myVamp5.4 by Paulsson is a good example of a vampire.
    • A one-shot is a very simple scanner that only scans the core until it finds the first target, and then permanently switches to an attack strategy, usually a core clear. Myrmidon by Roy van Rijn is a simple, yet effective oneshot.
  • An imp (named after the first ever published warrior, Imp by A. K. Dewdney) is a trivial one-instruction mobile warrior that continually copies its sole instruction just ahead of its instruction pointer. Imps are hard to kill but next to useless for offense. Their use lies in the fact that they can easily be spawned in large numbers, and may survive even if the rest of the warrior is killed.
    • An imp ring or imp spiral consists of imps spaced at equal intervals around the core and executing alternately. The imps at each arm of the ring/spiral copy their instruction to the next arm, where it is immediately executed again. Rings and spirals are even harder to kill than simple imps, and they even have a (small) chance of killing warriors not protected against them. The number of arms in an imp ring or spiral must be relatively prime with the size of the core.
  • A quickscanner attempts to catch its opponent early by using a very fast unrolled scanning loop. Quickscanning is an early-game strategy, and always requires some other strategy as a backup. Adding a quickscanning component to a warrior can improve its score against long warriors — such as other quickscanners. However, the unrolled scan can only target a limited number of locations, and is unlikely to catch a small opponent.
  • A core clear is a simple warrior that sequentially overwrites every instruction in the core, sometimes even including itself. Core clears are not very common as stand-alone warriors, but they are often used as an end-game strategy by bombers and scanners.
  • A bomb-dodger is a specialized strategy against bombers. It scans the core until it locates a bomb thrown by the bomber, and then copies its code there, assuming that the bomber won't attack the same spot again any time soon.

[edit] Core War Programming

Based on the understanding of Core War strategies, a programmer can create a warrior to achieve certain goals. The warrior is saved in ASCII format, with a ".red" extension. Revolutionary ideas come once in a while; most of the time, however, programmers utilize the published warriors to get some ideas. Using optimizers such as OptiMax or core-step optimizer tools, a more compact and efficient warrior can be created.

Since Redcode is Turing Complete, warriors can also be generated by Genetic Algorithms or Genetic Programming. Programs that integrate this evolutionary technique are also known as Core War Evolvers. Several small and fast evolvers were introduced by Core War community but were more focused on tiny or nano Core War settings. The latest evolver with significant success was microGP which produced nano and tiny KOTHs. Nevertheless, evolotionary strategy still need to prove its effectiveness in bigger hills (8000 or more cores).[11]

[edit] Variants

  • CoreWars 8086 implements a game very similar to the original Core War. Instead of using the customized instruction set of Redcode, CoreWars 8086 warrior programs are written in 8086 assembly language.
  • Tierra is an adaptation of Core War, written by Thomas S. Ray (an early member of the ICWS), used in the modeling of living systems.
  • Avida is a further derivative of Core War, building upon Tierra, and abstracting further the processes of evolution. Avida, created by Christoph Adami, Charles Ofria, and Titus Brown, is used in scientific research about evolution.

[edit] See also

Video games portal

[edit] References

  1. ^ Dewdney, A. K. (May 1984). "In the game called Core War hostile programs engage in a battle of bits.". Scientific American. http://corewar.co.uk/vogtmann/first.htm. Retrieved on 2008-11-18. 
  2. ^ Jones, D. G.; Dewdney, A. K. (March 1984). "Core War Guidelines". http://corewar.co.uk/cwg.txt. Retrieved on 19 November 2008. 
  3. ^ Dewdney, A. K. (March 1985). "A Core War bestiary of viruses, worms and other threats to computer memories.". Scientific American. http://corewar.co.uk/vogtmann/second.htm. Retrieved on 2008-11-18. 
  4. ^ Dewdney, A. K. (January 1987). "A program called MICE nibbles its way to victory at the first Core War tournament.". Scientific American. http://corewar.co.uk/vogtmann/third.htm. Retrieved on 2008-11-18. 
  5. ^ Doligez, Damien; Durham, Mark (8 November 1995). "Annotated Draft of the Proposed 1994 Core War Standard". http://corewar.co.uk/icws94.txt. Retrieved on 19 November 2008. 
  6. ^ Metcalf, J. A.. "A Brief History of Corewar". http://corewar.co.uk/history.htm. Retrieved on 19 November 2008. 
  7. ^ Mintarjo, W. "Intro to Art in '88: Paper - Stone - Scissors Trilogy."
  8. ^ The First International Core War Tournament
  9. ^ replicators? - Phoenix & TimeScape source
  10. ^ Metcalf, J. A. "Anatomy of the Scanner, A Basic Introduction."
  11. ^ Bvowk, Sasha & Fizmo: An Evolutionary Approach Generates Human Competitive Corewar Programs

[edit] External links

[edit] Documents

[edit] Programs

  • pMARS is the official simulator of the newsgroup rec.games.corewar. SDL-pMARS is a SDL based Windows port of pMARS; compatible with the extended ICWS-94 draft standard.
  • CoreWin a GUI-based Core War simulator for Windows; compatible with the extended ICWS-94 draft standard.
  • ARES - Core War simulator and debugger for Windows, includes an interactive tutorial; compatible with the extended ICWS-94 draft standard.
  • nMars - Core War MARS for .NET; compatible with the extended ICWS-94 draft standard.
  • XRK - Italian kit with Assembler, Disassembler, Simulator & Tournament (with network support) for DOS & Windows - ICWS-86 standard.
  • corewars8086 - CoreWars 8086 game engine, written in Java.

[edit] Tournaments

  • KOTH.org hosts "King of the Hill" Core War tournaments and provides information and software.
  • KOTH@SAL hosts a number of alternative Core War hills.
  • Koenigstuhl is the home of several infinite Core War hills.
  • The Corewar DynaHill implements Sumo tournament rankings.
Retrieved from "http://en.wikipedia.org/wiki/Core_War"
Personal tools