Core War
Encyclopedia
Core War 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 the victorious program in sole possession of the machine.
The 1984 Scientific American article on Core War nonetheless cites the game 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. 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. 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, and again in January 1987.
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. 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.
used in Core War. It is executed by a virtual machine
known as a Memory Array Redcode Simulator, or MARS. The design of Redcode is loosely based on actual CISC
assembly language
s of the early 1980s era, but contains several features not usually found in actual computer systems.
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:
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.
No absolute addressing: All addresses are interpreted as offsets relative to the instruction containing them. Since the address space wraps around, it is in fact impossible for a Redcode program to determine its absolute address.
Low level multiprocessing: Instead of a single instruction pointer a Redcode simulator has a number of process queues, each containing a variable number of instruction pointers which the simulator cycles through. New processes may be added to the queue using the
Other notable features of Redcode include:
No external access: Redcode and the MARS architecture provide no input or output functions. The simulator is a closed system, with the only input being the initial values of the memory and the process queues, and the only output being the outcome of the battle, i.e. which programs had surviving processes. Of course, the simulator may still allow external inspection and modification of the memory while the simulation is running.
Constant instruction length and time: Each Redcode instruction occupies exactly one memory slot and takes exactly one cycle to execute. The rate at which a process executes instructions, however, depends on the number of other processes in the queue, as processing time is shared equally.
Relatively few instructions: The earliest published version of Redcode had only eight instructions, while the currently used version has eighteen. However, Redcode supports a number of different addressing modes and (in later versions) instruction modifiers which increase the actual number of possible opcodes to several thousand.
All addresses are valid: All numbers in Redcode are treated as unsigned integers, and the maximum integer value is set to equal the number of memory locations minus one. Thus each integer is a valid address, and each memory location has exactly one valid address. Numbers that would fall outside the valid range are wrapped around according to the usual rules of modulo arithmetic.
Circular memory: As a consequence of the above and the lack of absolute addressing, the memory space (or core) appears to the programs in it as a circle with no definite start or end. A process that encounters no invalid or jump instructions can continue executing successive instructions endlessly, eventually returning to the instruction where it started.
.
. The language as described here differs significantly from the later variants, being in many ways closer to actual assembly languages of the era.
The Guidelines describe a set of only eight instructions, but it is stated that the earliest implementations of Redcode by Dewdney and Jones had a larger instruction set. Indeed, the language described in the Guidelines is best seen more as a basis for other developers to expand on than as an actual standard.
, since their performance against each other approximates that of their namesakes in the well known playground game.
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 µGP which produced nano and tiny KOTHs. Nevertheless, evolutionary strategy still need to prove its effectiveness in bigger hills (9000 or more cores).
Programming game
A programming game is a computer game where the player has no direct influence on the course of the game. Instead, a computer program or script is written in some domain-specific programming language in order to control the actions of the characters...
in which two or more battle programs (called "warriors") compete for the control of the "Memory Array Redcode Simulator" virtual computer
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
("MARS"). These battle programs are written in an abstract assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
called Redcode. The object of the game is to cause all processes of the opposing program(s) to terminate, leaving the victorious program in sole possession of the machine.
History
Core War was inspired by a program called Creeper and a subsequent program called Reaper that destroyed copies of Creeper. Creeper was created by B. Thomas at BBN. Dewdney was not aware of the origin of Creeper and Reaper and refers to them as a rumor originating from the Darwin game and the worm experiments of Shoch and Hupp.The 1984 Scientific American article on Core War nonetheless cites the game Darwin
Darwin (programming game)
Darwin was a programming game invented in August 1961 by Victor A. Vyssotsky, Robert Morris Sr., and M. Douglas McIlroy. The game was developed at Bell Labs, and played on an IBM 7090 mainframe there...
, written by Victor A. Vyssotsky
Victor A. Vyssotsky
Victor A. Vyssotsky, son of the astronomers Alexander N. Vyssotsky and Emma Vyssotsky is a mathematician and computer scientist. He was one of the team member of Multics project. Multics, whilst not particularly commercially successful in itself, directly inspired Ken Thompson to develop...
, Robert Morris Sr., and M. Douglas McIlroy at the Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
in the 1960s. The word "Core" in the name comes from magnetic core memory
Magnetic core memory
Magnetic-core memory was the predominant form of random-access computer memory for 20 years . It uses tiny magnetic toroids , the cores, through which wires are threaded to write and read information. Each core represents one bit of information...
, an obsolete random access memory technology. The same usage may be seen in other computer jargon terms such as "core dump
Core dump
In computing, a core dump consists of the recorded state of the working memory of a computer program at a specific time, generally when the program has terminated abnormally...
".
The first description of the Redcode language was published in March 1984, in Core War Guidelines by D. G. Jones and A. K. Dewdney. 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, and again in January 1987.
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. 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.
Redcode
Redcode is the programming languageProgramming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
used in Core War. It is executed by a virtual machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
known as a Memory Array Redcode Simulator, or MARS. The design of Redcode is loosely based on actual CISC
Complex instruction set computer
A complex instruction set computer , is a computer where single instructions can execute several low-level operations and/or are capable of multi-step operations or addressing modes within single instructions...
assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
s of the early 1980s era, but contains several features not usually found in actual computer systems.
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
Complex instruction set computer
A complex instruction set computer , is a computer where single instructions can execute several low-level operations and/or are capable of multi-step operations or addressing modes within single instructions...
assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
, 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 modeAddressing modeAddressing modes are an aspect of the instruction set architecture in most central processing unit designs. The various addressing modes that are defined in a given instruction set architecture define how machine language instructions in that architecture identify the operand of each instruction...
. 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 moduloModular arithmeticIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
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.
Key features
No numeric instruction values: The Redcode standard leaves the underlying representation of instruction codes undefined, and provides no means for programs to directly access it. Arithmetic operations may only be done on the two address fields contained in each instruction. The only operations supported on the instruction codes themselves are copying and comparison for equality.No absolute addressing: All addresses are interpreted as offsets relative to the instruction containing them. Since the address space wraps around, it is in fact impossible for a Redcode program to determine its absolute address.
Low level multiprocessing: Instead of a single instruction pointer a Redcode simulator has a number of process queues, each containing a variable number of instruction pointers which the simulator cycles through. New processes may be added to the queue using the
SPL instruction.Other notable features of Redcode include:
No external access: Redcode and the MARS architecture provide no input or output functions. The simulator is a closed system, with the only input being the initial values of the memory and the process queues, and the only output being the outcome of the battle, i.e. which programs had surviving processes. Of course, the simulator may still allow external inspection and modification of the memory while the simulation is running.
Constant instruction length and time: Each Redcode instruction occupies exactly one memory slot and takes exactly one cycle to execute. The rate at which a process executes instructions, however, depends on the number of other processes in the queue, as processing time is shared equally.
Relatively few instructions: The earliest published version of Redcode had only eight instructions, while the currently used version has eighteen. However, Redcode supports a number of different addressing modes and (in later versions) instruction modifiers which increase the actual number of possible opcodes to several thousand.
All addresses are valid: All numbers in Redcode are treated as unsigned integers, and the maximum integer value is set to equal the number of memory locations minus one. Thus each integer is a valid address, and each memory location has exactly one valid address. Numbers that would fall outside the valid range are wrapped around according to the usual rules of modulo arithmetic.
Circular memory: As a consequence of the above and the lack of absolute addressing, the memory space (or core) appears to the programs in it as a circle with no definite start or end. A process that encounters no invalid or jump instructions can continue executing successive instructions endlessly, eventually returning to the instruction where it started.
Variants
A number of variants of Redcode exist. The earliest versions described by A. K. Dewdney differ in many respects from the later standards established by the International Core War Society, and could be considered a different, albeit related, language. The form of Redcode most commonly used today is based on a draft standard submitted to the ICWS in 1994 that was never formally accepted, as the ICWS had become effectively defunct around that time. Development of Redcode, however, has continued in an informal manner, chiefly via online forums such as therec.games.corewar newsgroupNewsgroup
A usenet newsgroup is a repository usually within the Usenet system, for messages posted from many users in different locations. The term may be confusing to some, because it is usually a discussion group. Newsgroups are technically distinct from, but functionally similar to, discussion forums on...
.
Earliest versions
The earliest published description of Redcode is found in the Core War Guidelines published in March 1984 by A. K. Dewdney and D. G. JonesD. G. Jones
Douglas Gordon Jones is a Canadian poet, translator and educator.Born in Bancroft, Ontario, Jones was educated at a private school in Quebec's Eastern Townships, at McGill University and at Queen's University. He received his M.A. from Queen's University in 1954. Jones then taught English...
. The language as described here differs significantly from the later variants, being in many ways closer to actual assembly languages of the era.
The Guidelines describe a set of only eight instructions, but it is stated that the earliest implementations of Redcode by Dewdney and Jones had a larger instruction set. Indeed, the language described in the Guidelines is best seen more as a basis for other developers to expand on than as an actual standard.
Strategy
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 stoneRock, Paper, Scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
, since their performance against each other approximates that of their namesakes in the well known playground game.
- A bomber (or rock) 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 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.
- 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.
- A scanner (or scissor) is designed to beat replicators, usually by bombing memory with SPL 0 instructions. This causes the enemy to create a 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. 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 PaulssonPaulssonPaulsson is a Swedish patronymic surname meaning "son of Paul", itself an English language derivative of the ancient Roman nomen Paulus, meaning "small". There are over 200 variants of the surname. Within Sweden, an alternate spelling is Pålsson, while the Icelandic is Pálsson, and the British...
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 primeCoprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
with the size of the core.
- 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
- 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.
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.Warriors can also be generated by Genetic Algorithms
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
or Genetic Programming
Genetic programming
In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
. 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 µGP which produced nano and tiny KOTHs. Nevertheless, evolutionary strategy still need to prove its effectiveness in bigger hills (9000 or more cores).
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.
- TierraTierra (computer simulation)Tierra is a computer simulation developed by ecologist Thomas S. Ray in the early 1990s in which computer programs compete for central processing unit time and access to main memory...
is an adaptation of Core War, written by Thomas S. RayThomas S. RayThomas S. Ray is an ecologist who created and developed the Tierra project, a computer simulation of artificial life.In 1975, he and Donald R...
(an early member of the ICWS), used in the modeling of living systems. - AvidaAvidaAvida is an artificial life software platform to study the evolutionary biology of self-replicating and evolving computer programs . Avida is under active development by Charles Ofria's Digital Evolution Lab at Michigan State University and was originally designed by Ofria, Chris Adami and C. Titus...
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.
See also
- Digital organismDigital organismA digital organism is a self-replicating computer program that mutates and evolves. Digital organisms are used as a tool to study the dynamics of Darwinian evolution, and to test or verify specific hypotheses or mathematical models of evolution...
- RoboWarRoboWarRoboWar is an open source video game in which the player programs onscreen icon-like robots to battle each other with animation and sound effects...
- Algorithmic tradingAlgorithmic tradingIn electronic financial markets, algorithmic trading or automated trading, also known as algo trading, black-box trading or robo trading, is the use of electronic platforms for entering trading orders with an algorithm deciding on aspects of the order such as the timing, price, or quantity of the...
: stock trading programs sometimes compete with each other.