Core War

Last updated
Core War
Developer(s) D. G. Jones & A. K. Dewdney
Initial releaseMarch 1984
Type Programming game
Website www.corewars.org

Core War is a 1984 programming game created by D. G. Jones and A. K. Dewdney in which two or more battle programs (called "warriors") compete for control of a virtual computer. These battle programs are written in an abstract assembly language called Redcode. The standards for the language and the virtual machine were initially set by the International Core Wars Society (ICWS), but later standards were determined by community consensus.

Contents

Gameplay

At the beginning of a game, each battle program is loaded into memory at a random location, after which each program executes one instruction in turn. The goal of the game is to cause the processes of opposing programs to terminate (which happens if they execute an invalid instruction), leaving the victorious program in sole possession of the machine.

The earliest published version of Redcode defined only eight instructions. The ICWS-86 standard increased the number to 10 while the ICWS-88 standard increased it to 11. The currently used 1994 draft standard has 16 instructions. However, Redcode supports a number of different addressing modes and (starting from the 1994 draft standard) instruction modifiers which increase the actual number of operations possible to 7168. The Redcode standard leaves the underlying instruction representation undefined and provides no means for programs to access it. Arithmetic operations may be done on the two address fields contained in each instruction, but the only operations supported on the instruction codes themselves are copying and comparing for equality.

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.
Circular memory
The memory is addressed in units of one instruction. The memory space (or core) is of finite size, but 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. The maximum address value is set to equal one less than the number of memory locations and will wrap around if necessary. As a result, there is a one-to-one correspondence between addresses and memory locations, but it is impossible for a Redcode program to determine any absolute address. A process that encounters no invalid or jump instructions will continue executing successive instructions endlessly, eventually returning to the instruction where it started.
Low-level multiprocessing
Instead of a single instruction pointer a Redcode simulator has a process queue for each program containing a variable number of instruction pointers which the simulator cycles through. Each program starts with only one process, but new processes may be added to the queue using the SPL instruction. 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 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 inspections and modification of the memory while the simulation is running.

Versions of Redcode

A number of versions of Redcode exist. The earliest version described by A. K. Dewdney [1] differs 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 the rec.games.corewar [2] newsgroup.

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 stone, since their performance against each other approximates that of their namesakes in the well-known playground game. [3]

Paper (or replicator)
A replicator 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.
A silk is a special type of very rapid replicator, named after Silk Warrior [4] 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. [5]
Scissors (or scanner)
A scanner is designed to beat replicators. A scanner does not 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. A scanner usually bombs memory with SPL 0 instructions. This causes the enemy to create a huge number of processes which do nothing but create more processes, slowing down useful processes. When the enemy becomes so slow that it is unable to do anything useful, the memory is then bombed with DAT instructions. Scanners are also generally more complex, and therefore are larger and more fragile, than other types of warriors. [6]
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 [7] by Roy van Rijn is an example of a oneshot.
Stone (or bomber)
A bomber 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 to gain extra resiliency against replicators.
Vampire (or pit-trapper)
A vampire 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. myVamp [8] by Paulsson is an example of a vampire.
Imp
Imps are named after the first ever published warrior, Imp [9] by A. K. Dewdney, 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 warriors are 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 instructions 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.
Quickscanner (or q-scan)
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.
Core clear
A core clear sequentially overwrites every instruction in the core, sometimes even including itself. Core clears are not very common as stand-alone warriors, but are often used as an end-game strategy by bombers and scanners.

Core War Programming

With an understanding of Core War strategies, a programmer can create a warrior to achieve certain goals. Revolutionary ideas come once in a while; most of the time, however, programmers base their programs on already published warriors. Using optimizers such as OptiMax or core-step optimizer tools, a more effective warrior can be created.

Warriors can also be generated by genetic algorithms or genetic programming. Programs that integrate this evolutionary technique are known as evolvers. Several evolvers were introduced by the Core War community and tend to focus on generating warriors for smaller core settings. The latest evolver with significant success was μGP [10] [11] which produced some of the most successful nano and tiny warriors. Nevertheless, evolutionary strategy still needs to prove its effectiveness on larger core settings. [12]

Development

Core War was inspired by a self-replicating program called Creeper and a subsequent program called Reaper that destroyed copies of Creeper. [13] Creeper was created by Bob Thomas at BBN. [14] Dewdney was not aware of the origin of Creeper and Reaper and refers to them as a rumor originating from Darwin and the worm experiments of Shoch and Hupp. The 1984 Scientific American article on Core War [13] nevertheless cites the game Darwin , played by Victor A. Vyssotsky, Robert Morris, and Douglas McIlroy at Bell Labs in 1961.

The word "Core" in the name comes from magnetic-core memory, an obsolete random-access memory technology. This term was then, and still today, typically in use as the term for working memory in working memory dumps, called core dumps, on Unix and most Unix-like systems. Additionally, the default filename used for core dumps on such systems is usually "core" or contains the word core.

The first description of the Redcode language was published in March 1984, in Core War Guidelines by D. G. Jones and A. K. Dewdney. [1] 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, [15] and again in January 1987. [16]

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. [17] Nonetheless, the 1994 draft was commonly adopted and extended, and forms the basis of 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[ when? ] the ICWS is defunct. [18]

Redcode

0000:ADD.AB#4,$30001:MOV.F$2,@20002:JMP.B$-2,$00003:DAT.F#0,#0
Assembled ICWS-94 style Redcode

Redcode is the programming language 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 languages of the early 1980s, but contains several features[ vague ] 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 is quite simplified relative to "real" assembly, and has no absolute memory addressing

The original 8 instructions are described as follows. Later versions added NOP, multiply and more complex comparisons. [19]

OpcodeMnemonicArgument(s)Action------------------------------------------------------------0DATBInitializelocationtovalueB.1MOVABMoveAintolocationB.2ADDABAddoperandAtocontentsoflocationBandstoreresultinlocationB.3SUBABSubtractoperandAfromcontentsoflocationBandstoreresultinlocationB.4JMPBJumptolocationB.5JMZABIfoperandAis0,jumptolocationB; otherwisecontinuewithnextinstruction.6DJZABDecrementcontentsoflocationAby1.IflocationAnowholds0,jumptolocationB; otherwisecontinuewithnextinstruction.7CMPABCompareoperandAwithoperandB.Iftheyarenotequal,skipnextinstruction; otherwiseexecutenextinstruction.

the ICWS '94 standard draft added more addressing modes, mostly to deal with A-field indirection, to give a total of 8 address modes:

#immediate$direct(the$maybeomitted)*A-fieldindirect@B-fieldindirect{A-fieldindirectwithpredecrement<B-fieldindirectwithpredecrement}A-fieldindirectwithpostincrement>B-fieldindirectwithpostincrement

Implementations

Development of implementations of the game continued over the years by several authors. There are multiple versions of the game available, [20] ported for several platforms. For instance pMARS which is open source software with source code on SourceForge, [21] or the SDL based SDL pMARS for Windows. [22]

The common implementation pMars was downloaded over 35,000 times between 2000 and 2021 from SourceForge. [23]

Related Research Articles

<span class="mw-page-title-main">Data General Nova</span> 16-bit minicomputer series

The Data General Nova is a series of 16-bit minicomputers released by the American company Data General. The Nova family was very popular in the 1970s and ultimately sold tens of thousands of units.

<span class="mw-page-title-main">Machine code</span> Set of instructions executed by a computer

In computer programming, machine code is computer code consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). For conventional binary computers machine code is "the binary representation of a computer program which is actually read and interpreted by the computer. A program in machine code consists of a sequence of machine instructions ."

<span class="mw-page-title-main">PDP-8</span> Minicomputer product line

The PDP-8 is a family of 12-bit minicomputers that was produced by Digital Equipment Corporation (DEC). It was the first commercially successful minicomputer, with over 50,000 units being sold over the model's lifetime. Its basic design follows the pioneering LINC but has a smaller instruction set, which is an expanded version of the PDP-5 instruction set. Similar machines from DEC are the PDP-12 which is a modernized version of the PDP-8 and LINC concepts, and the PDP-14 industrial controller system.

In computer science, threaded code is a programming technique where the code has a form that essentially consists entirely of calls to subroutines. It is often used in compilers, which may generate code in that form or be implemented in that form themselves. The code may be processed by an interpreter or it may simply be a sequence of machine code call instructions.

In computer science, an instruction set architecture (ISA) is an abstract model that generally defines how software controls the CPU in a computer or a family of computers. A device or program that executes instructions described by that ISA, such as a central processing unit (CPU), is called an implementation of that ISA.

<span class="mw-page-title-main">MCS-51</span> Single chip microcontroller series by Intel

The Intel MCS-51 is a single chip microcontroller (MCU) series developed by Intel in 1980 for use in embedded systems. The architect of the Intel MCS-51 instruction set was John H. Wharton. Intel's original versions were popular in the 1980s and early 1990s, and enhanced binary compatible derivatives remain popular today. It is a complex instruction set computer, but also has some of the features of RISC architectures, such as a large register set and register windows, and has separate memory spaces for program instructions and data.

<span class="mw-page-title-main">IBM 1620</span> Small IBM scientific computer released in 1959

The IBM 1620 was announced by IBM on October 21, 1959, and marketed as an inexpensive scientific computer. After a total production of about two thousand machines, it was withdrawn on November 19, 1970. Modified versions of the 1620 were used as the CPU of the IBM 1710 and IBM 1720 Industrial Process Control Systems.

<span class="mw-page-title-main">IBM 1401</span> 1960s decimal computer

The IBM 1401 is a variable-wordlength decimal computer that was announced by IBM on October 5, 1959. The first member of the highly successful IBM 1400 series, it was aimed at replacing unit record equipment for processing data stored on punched cards and at providing peripheral services for larger computers. The 1401 is considered by IBM to be the Ford Model-T of the computer industry due to its mass appeal. Over 12,000 units were produced and many were leased or resold after they were replaced with newer technology. The 1401 was withdrawn on February 8, 1971.

A one-instruction set computer (OISC), sometimes referred to as an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode. With a judicious choice for the single instruction and given arbitrarily many resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions. OISCs have been recommended as aids in teaching computer architecture and have been used as computational models in structural computing research. The first carbon nanotube computer is a 1-bit one-instruction set computer.

In computer architecture, register renaming is a technique that abstracts logical registers from physical registers. Every logical register has a set of physical registers associated with it. When a machine language instruction refers to a particular logical register, the processor transposes this name to one specific physical register on the fly. The physical registers are opaque and cannot be referenced directly but only via the canonical names.

In computer science, computer engineering and programming language implementations, a stack machine is a computer processor or a virtual machine in which the primary interaction is moving short-lived temporary values to and from a push down stack. In the case of a hardware processor, a hardware stack is used. The use of a stack significantly reduces the required number of processor registers. Stack machines extend push-down automata with additional load/store operations or multiple stacks and hence are Turing-complete.

<span class="mw-page-title-main">Memory address</span> Reference to a specific memory location

In computing, a memory address is a reference to a specific memory location used at various levels by software and hardware. Memory addresses are fixed-length sequences of digits conventionally displayed and manipulated as unsigned integers. Such numerical semantic bases itself upon features of CPU, as well upon use of the memory like an array endorsed by various programming languages.

Addressing modes are an aspect of the instruction set architecture in most central processing unit (CPU) designs. The various addressing modes that are defined in a given instruction set architecture define how the machine language instructions in that architecture identify the operand(s) of each instruction. An addressing mode specifies how to calculate the effective memory address of an operand by using information held in registers and/or constants contained within a machine instruction or elsewhere.

The National Semiconductor COP8 is an 8-bit CISC core microcontroller. COP8 is an enhancement to the earlier COP400 4-bit microcontroller family. COP8 main features are:

<span class="mw-page-title-main">WDC 65C02</span> CMOS microprocessor in the 6502 family

The Western Design Center (WDC) 65C02 microprocessor is an enhanced CMOS version of the popular nMOS-based 8-bit MOS Technology 6502. It uses less power than the original 6502, fixes several problems, and adds new instructions. The power usage is on the order of 10 to 20 times less than the original 6502 running at the same speed; its reduced power consumption has made it useful in portable computer roles and industrial microcontroller systems. The 65C02 has also been used in some home computers, as well as in embedded applications, including medical-grade implanted devices.

The PDP-11 architecture is a 16-bit CISC instruction set architecture (ISA) developed by Digital Equipment Corporation (DEC). It is implemented by central processing units (CPUs) and microprocessors used in PDP-11 minicomputers. It was in wide use during the 1970s, but was eventually overshadowed by the more powerful VAX architecture in the 1980s.

<span class="mw-page-title-main">ST6 and ST7</span> 8-bit microcontroller product lines from STMicroelectronics

The ST6 and ST7 are 8-bit microcontroller product lines from STMicroelectronics. They are commonly used in small embedded applications like washing machines.

The PIC instruction set refers to the set of instructions that Microchip Technology PIC or dsPIC microcontroller supports. The instructions are usually programmed into the Flash memory of the processor, and automatically executed by the microcontroller on startup.

<span class="mw-page-title-main">SDS 9 Series</span> Backward compatible line of transistorized computers

The SDS 9 Series computers are a backward compatible line of transistorized computers produced by Scientific Data Systems in the 1960s and 1970s. This line includes the SDS 910, SDS 920, SDS 925, SDS 930, SDS 940, and the SDS 945. The SDS 9300 is an extension of the 9xx architecture. The 1965 SDS 92 is an incompatible 12-bit system built using monolithic integrated circuits.

The 12-bit ND812, produced by Nuclear Data, Inc., was a commercial minicomputer developed for the scientific computing market. Nuclear Data introduced it in 1970 at a price under $10,000.

References

  1. 1 2 Jones, D. G.; Dewdney, A. K. (March 1984). "Core War Guidelines" . Retrieved 2023-05-27.
  2. "rec.games.corewar on Google Groups" . Retrieved 2023-05-29.
  3. Wangsaw, Mintardjo. "Intro to Art in '88: Paper - Stone - Scissors Trilogy" . Retrieved 2023-05-27.
  4. Pohjalainen, Jippo. "Silk Warrior 1.3" . Retrieved 2023-05-27.
  5. Pohjalainen, Jippo (April 1995). "replicators? -> Phoenix & TimeScapesource" . Retrieved 2023-05-27.
  6. Metcalf, John (April 2004). "Anatomy of the Scanner, A Basic Introduction" . Retrieved 2023-05-27.
  7. van Rijn, Roy. "Myrmidon" . Retrieved 2023-05-27.
  8. Paulsson, Magnus. "myVamp v3.7" . Retrieved 2023-05-27.
  9. Dewdney, A. K. "Imp" . Retrieved 2023-05-27.
  10. Squillero, Giovanni. "μGP (MicroGP v2)". GitHub . Retrieved 2018-09-10.
  11. Corno, F.; Sanchez, E.; Squillero, G. (2005). "Evolving Assembly Programs: How Games Help Microprocessor Validation". IEEE Transactions on Evolutionary Computation. 9 (6): 695–706. doi:10.1109/TEVC.2005.856207. ISSN   1089-778X.
  12. Vowk, Barkley; Wait, Alexander; Schmidt, Christian. "An Evolutionary Approach Generates Human Competitive Corewar Programs" (PDF). Retrieved 2023-05-27.
  13. 1 2 Dewdney, A. K. (May 1984). "In the game called Core War hostile programs engage in a battle of bits". Scientific American . Retrieved 2023-05-27.
  14. Shoch, J.; Hupp, J. (March 1982). "The 'Worm' Programs - Early Experience with a Distributed Computation". Communications of the ACM . 25 (3): 172–180. doi: 10.1145/358453.358455 . S2CID   1639205.
  15. Dewdney, A. K. (March 1985). "A Core War bestiary of viruses, worms and other threats to computer memories". Scientific American. Retrieved 2023-05-27.
  16. Dewdney, A. K. (January 1987). "A program called MICE nibbles its way to victory at the first Core War tournament". Scientific American. Retrieved 2023-05-27.
  17. Doligez, Damien; Durham, Mark (8 November 1995). "Annotated Draft of the Proposed 1994 Core War Standard" . Retrieved 2023-05-27.
  18. Metcalf, John. "A Brief History of Corewar" . Retrieved 2023-05-27.
  19. "The beginners' guide to Redcode, v1.23".
  20. The Corewar Emulators on corewar.info
  21. corewar on SourceForge
  22. pMARS-SDL on corewar.co.uk by Joonas Pihlaja (7 May 2003)
  23. download numbers corewar on SourceForge (access 2021-06-07)