Redcode
| Paradigm(s) | imperative |
|---|---|
| Designed by | A. K. Dewdney & David Jones |
| Appeared in | 1983 |
| Computational class | Turing-complete |
| Major implementations | pMARS, CoreWin |
| Influenced by | assembly code |
| Influenced | CoreLife and many others |
| File extension(s) | .red |
Redcode is an esoteric programming language designed by A. K. Dewdney and David Jones in 1983. The purpose of Redcode is to provide an environment for Core War, in which programs ("warriors") attempt to crash their opponents. Redcode is (almost) Turing Complete in the same sense as C, where any given program must run within finite memory space but may be agnostic to the exact size. In fact, only one of the instructions is required to achieve that: DJN.
Core War is the most famous programming game, a kind of game where humans don't directly play, but instead write programs (warriors) to compete against other programs on servers called "hills". Another good example of a programming game is BF joust, which is much easier than Redcode (in part due to being less developed than Core War).
Redcode is not really esoteric, but closer to assembly code, although it is often considered "weird" for assembly.
History
Well either by accident or design the rules of corewar has led to a diversity of warriors where any type of warrior always has something which can beat it.
- Scott's Quick Core War Guide
Core War and Redcode was designed by A. K. Dewdney and David Jones in autumn 1983 and first described in the May 1984 issue of Scientific American. It soon gained popularity, and there were multiple international tournaments hosted in the following years.
Redcode has a long history, from the initial version described in the article to the '86 and '88 standards by the ICWS (International Core Wars Society), who hosted 8 annual tournaments, and the current '94 standard which was never formally accepted by the ICWS because it is already down at the time. However, it is now the most popular standard.
The "hills", a sort of ongoing tournament, appears as early as 1991 as the "Intel hill", which was later replaced by the KotH and Pizza hills. Planar hosted Mt. Olympus, an "infinite" hill where programs never get pushed off and is more of an archive. The current hills are the KotH, SAL, and the "Koenigstuhl" (replacement for Mt. Olympus).
The types and structure of programs evolved a lot over time. From early on three main types of programs evolved which normally beat each other in a cycle like rock-paper-scissors, to the point that they become the common names for the types of programs. A notable event is the invention of the "quick scanner", which is now a component of every viable non-scanner and even some scanners as well.
Syntax
Due to space limitations, don't expect any detailed descriptions. For a clearer description, refer to the external resources below.
This article follows the '94 standard, non-standard instructions are not listed.
Each command is one line consisting of an opcode and two addresses, namely A-field and B-field. All addresses are relative, so for example 1 means the next instruction and -1 means the previous.
An addressing mode is a character that comes before each address:
| Symbol | Decription |
|---|---|
#
|
Immediate: This means the "address" is an integer and will be treated as 0 for address-demanding instructions. |
$
|
Direct: This is the default mode which is used when no symbol is specified. |
@
|
Indirect: The actual address is the address specified by where the address points to. |
<
|
Same as @, but where the address points to is decremented by one before usage.
|
>
|
Same as <, but it increments instead, and after usage.
|
*
|
Same as @, but it reads the A-field instead of the B-field like everything above.
|
{
|
Same as <, but reads A-field
|
}
|
Same as >, but reads A-field
|
There are also instruction modifiers, used as an extension to the opcode, which modify how the instructions treat the A and B-fields. Valid ones are: .a, .b, .ab, .ba, .f, .x, .i.
The following are opcodes. Note that both opcodes and modifiers are case insensitive.
| Opcode | Description |
|---|---|
| DAT | When executed, the current process is terminated |
| MOV | Copies the contents of the A-field to the B-field |
| ADD | Adds the contents of the A-field to the contents of the B-field |
| SUB | Subtracts the contents of the A-field from the contents of the B-field |
| MUL | Multiplies the contents of the A-field by the contents of the B-field. Redcode-94 only. |
| DIV | Divides the contents of the A-field by the contents of the B-field. Division by zero terminates the executing process. Redcode-94 only. |
| MOD | Divides the contents of the A-field by the contents of the B-field and sets the B-field to the remainder. Modulus by zero terminates the executing process. Redcode-94 only. |
| JMP | Transfers control to the location specified in the A-field |
| JMZ | Transfers control to the A-field location if the B-field is 0 |
| JMN | Transfers control to the A-field location if the B-field is not 0 |
| DJN | Decrements the B-field. Transfers control to the A-field location if the B-field is not 0 |
| SEQ | Skips the next instruction if the A-field and B-field are equal. CMP is a synonym |
| SNE | Skips the next instruction if the A-field and B-field are not equal. Redcode-94 only. |
| SLT | Skips the next instruction if the A-field is less than the B-field |
| SPL | Start a new process at the location specified by the A-field |
| NOP | Do nothing |
| STP | Copies the A-field to the private memory specified by the B-field. Redcode-94 only, and only on hills where P-space is allowed. |
| LDP | Copies the private memory specified by the A-field to the B-field. Redcode-94 only, and only on hills where P-space is allowed. |
An example of a full instruction:
mov.ba #14, @3
Examples
This section lists the two earliest, simplest, and possibly weakest programs, as well as something to demonstrate Redcode's usage in ordinary programming.
Imp
This program copies itself forward forever, turning other processes into copies of itself. Somewhat hard to kill, but always overwrites enemies with executable instructions.
; "Imp", A. K. Dewdney
mov 0, 1
; Alternate versions using redcode-94 instruction modifier semantics:
mov.i #8, 1 ; A-field can store arbitrary data.
mov.i #1, *0 ; Copies itself via A-field indirection.
Dwarf
This was the first "stone" (bomber), best against "scissors" (scanners), and worst against "paper" (replicators). However, it loses against even a weak scanner in modern times.
; "Dwarf", A. K. Dewdney
mov 4, @4 ; Move the bomb to the location pointed to by the bomb. (B-indirect.)
add #4, 3 ; Immediate add adds the immediate A-operand to the B-field of the cell pointed to by the B-operand.
jmp -2 ; Jump back two steps (to the MOV)
dat #4 ; The bomb. After enough cycles, dwarf will overwrite the bomb with itself, harmlessly. It then restarts the bombing run.
Hello, World
This program prints out the words Hello, World!, sts is a non-standard instruction designed to give output:
; Redcode Hello World, John Metcalf
write sts.a hello, 0
sts.b }write, 0
djn write, #7
hello dat 72, 101 ; He
dat 108, 108 ; ll
dat 111, 44 ; o,
dat 32, 87 ; W
dat 111, 114 ; or
dat 108, 100 ; ld
dat 33, 10 ; !\n
See also
External resources
Information sites
- The beginners' guide to Redcode
- https://corewar.co.uk/
- The Core War Imp Ring, a listing of sites related to Core War
- http://www.corewar.info/, a great source of information about Core War, but using HTTPS might cause it to break; use HTTP instead
- pMARS Core War interpreter
- Annotated Draft of the Proposed 1994 Core War Standard
- Thoughts on Corewar..., impomatic's Redcode programming blog
- Core War (Wikipedia), including an overview of different strategy types
- rec.games.corewar newsgroup
Competitive hills
Warning: All hills except for the Beginners' hill are for experts! Do not attempt at the other hills until you have topped the beginners' hill. If you're using an evolver, the Nano hill should be easy.
- KotH (King of the Hill) server, has seven hills with different settings
- KotH@SAL server, has nine hills, but are more creative. Has the two hills mentioned above.
- Koenigstuhl, similar to SAL, but warriors never get pushed off, so the hills are "infinite"
Important: All of the hills require entries to be sent in email and in plain text. If you're doing it correct but they don't respond after several hours, it means you're not sending the email in plain text format, so look though settings and change them so that your email will be sent in plain text.