RobotWar and the Army of Clones

Back in 1981 Silas Warner created a game for MUSE Software which would go on to spawn an entire army of clones. Silas is probably better know as the author of the legendary Castle Wolfenstein. However it was RobotWar which went on to inspire a whole new genre.

Silas developed RobotWar for the PLATO computer system and later ported it to the Apple II for release by MUSE. The game is set at a time in the distant future when war has been declared hazardous to human health. Wars still rage, but the combatants are robots programmed to battle to the death.

RobotWar is played by writing the control program for one of these battle robots. The program controls the movement, radar and gun of the robot. Here's one of the example robots:

;     ROBOT  'SCANNER'
; SEND RADAR PULSE AND FIRE IF AN
; ENEMY IS SPOTTED

SCAN
AIM + 7 TO AIM

CHECK
AIM TO RADAR
IF RADAR > 0 GOTO SCAN
0 - RADAR TO SHOT
GOTO CHECK

Scanner is a simple stationary warrior. The first instruction (at scan) turns the gun 7° clockwise. The next instruction (at check) lines up the radar with the gun. The radar returns a positive number if it detects nothing, otherwise it returns minus the distance to the opponent.

The next line jumps back to scan if the radar returns positive. Otherwise a shell is fired by the penultimate instruction and the next line jumps back to check.

RobotWar earned a strong following in the early 1980's. Computer Gaming World organised annual tournaments and a group of enthusiasts formed the Postal RobotWar Club of America.

RobotWar has inspired a huge number of clones, I'll just mention a select few here:

• CROBOTS by Tom Poindexter (1985) uses a subset of C
• P-Robots by David Malmberg (1988) uses a Pascal subset
• AT-Robots by Ed T Toten (1992) uses assembly language
• Robocode by Mathew Nelson (2001) uses Java

Robocode is currently the most active. More information is available on the RoboWiki.

Please let me know if you think I've missed an important robot programming game or one of historical note. Also I'd love to hear from you if you have any memories of the above.

Five Computers I Longed to Possess in the 1980s

Back in the 1980's I owned a couple of computers, a Commodore 16 and a Spectrum +2. However, this didn't stop me wanting to own a whole range of other machines.

1. Jupiter Ace: I loved this from the moment I read about it. A Z80 based micro with a built in Forth interpreter, what more could I desire? Only about 9000 machines were manufactured and I've been waiting patiently ever since for one to come up on eBay.
2. Sam Coupé: a Sinclair Spectrum clone with 256K memory, a 6MHz Z80, optional internal disk drives and a 25MHz Z80 processor upgrade. Somewhere in the region of 12000 units were sold. A few years ago I picked up one of these at a car boot sale for a fiver! ;-)
3. NeXT Computer: from the moment I saw screenshots and read about this workstation built around Motorola's 68030 I knew I had to have one. After seeing the hefty price tag I knew I never would. Even now these sell for a small fortune on eBay.
4. Dragon 64: the Dragon's 6809 processor looked amazing compared to the 6502 used in most computers of the time. It boasted two stacks, plenty of registers and on chip multiplication. Whenever I wrote code for the 6502 I'd secretly hope to write for the 6809 one day.
5. KITT: a sentient, artificially intelligent computer built by Knight Industries and installed into a Pontiac Firebird Trans Am. Unfortunately my diecast model came without William Daniels' voice and the cool red lights. If KITT is ever on eBay I'll likely sell my house to buy it!

Let me know if you think I've missed off any cool machines :-)

Executable Compressors

An exe packer is a utility to reduce the size of executable files. It compresses a program and creates a new program with the compressed data and code to extract and run the original. Commonly used compression techniques include variants of Run Length Encoding and members of the LZ family of algorithms.

It's debatable whether there's still any real benefit to compressing exe files. Originally the reduced storage space would have been an advantage as would the slightly reduced disk (or even tape) load time. Nowadays the potential benefits are lower network bandwidth and smaller downloads.

Exe compressors present some interesting challenges for a programmer. The effectiveness of the compression has to be balanced against the size of the decompressor. The compression algorithm has to be chosen carefully for speedy decompression. If the program has a relocation table, what's the best way to optimise it? How can the additional memory requirements be minimised?

It shouldn't come as any surprise that hundreds of programmers have risen to the challenge and written an exe packer. A quick search of the net turns up at least 80 for DOS / Windows and several for other environments.

In 8086 assembly, a Run Length decoder for a DOS .COM file can be written in under 40 bytes and decoders for the simplest LZ77 derivatives in under 50 bytes. Here's an example RLE decoder:

; 8086 .COM RLE decoder

move:   ; copy unpacker and compressed
; code elsewhere in memory

mov si, unpack
mov di, freemem
mov cx, codeend-unpack
push di
rep movsb

; setup RLE paremeters

mov si, freemem+code-unpack
mov di, program
mov bx, num_of_tokens

; transfer control to unpack

ret

; unpack compressed program

unpack: push di
rle:    lodsb
cmp al, token
jne single
lodsw
mov cl,ah
db 0F3h ; rep
single: stosb
dec bx
jne rle

; transfer control to program

ret

code:   ; .....

codeend:

If you have any thoughts on the advantages / disadvantages of exe packers or any implementation ideas I'd love to hear them. Also does anyone know anything about the history of exe packers? The earliest I've found is from November 1987.

Implement MIN in Forth without Conditional Code

While lurking in the #forth channel on irc.freenode.net I was pointed to an interesting problem from the Gforth tutorial. The problem is to implement MIN in Forth without any conditionally executed code.

DO, LOOP, BEGIN, UNTIL, REPEAT, WHILE, IF, ELSE and THEN are all forbidden.  MIN removes the top two values from the data stack then puts the lower of the two back on.

Can you implement MIN under these conditions? If so I challenge you implement it in as few Forth words as possible! Let me know if your implementation is under 10 words :-)

BF Joust King of the Hill

BF Joust is a capture the flag programming game based on the esoteric Brainf*** programming language. Recently ais523 revised the language and enviroment, setting up a king of the hill tournament.

The game is played between two programs on a tape with a length randomly chosen between 10 and 30 cells. The cells initially contain 0 with the exception of the cells at either end which contain the flag 128.

Each program views the tape with their own flag on the left and the opponent's flag on the right. The object of the game is to find and set the opponents flag to 0 and keep it 0 for two consecutive cycles. If a program's pointer points to a location off the tape, it loses.

Here's a quick summary of the instruction set:

Op	Description
<	move the pointer to the left
>	move the pointer to the right
+	add 1 to the value stored at pointer
-	subtract 1 from the value stored at pointer
[	jump past the matching ] if the cell at pointer is 0
]	jump to instruction after matching [ unless cell at pointer is 0
.	no operation, do nothing

The interpreter also understands certain macros. Instructions inside parentheses are repeated a number of times. For example (>-)*4 expands to >->->->-.

For full details see the rules on the BF Joust Wiki page and check the current hill standings. To submit a program to the BF Joust hill, join the channel #esoteric on irc.freenode.net and send a message to egobot:

/msg egobot !bfjoust program_name program_code

It isn't possible to remove a program, but it can be replaced by submitting another with the same name.

Finally, I'll leave you with the code for shortsword the current king of the hill with 100% wins ;-)

(>++>--)*2(>)*6([-[+]]>)*20

The standings:

ID Score Pts Program
18 90.00  18 shortsword.bfjoust
19 71.12  12 stranger.bfjoust
16 69.75  11 scythe_impomatic.bfjoust
 1 59.38   9 ais523_attack5.bfjoust
 6 42.50   4 ais523_defend5.bfjoust
 2 41.50   6 ais523_attackslow.bfjoust
 7 38.00   2 asie1.bfjoust
 0 37.00   0 ais523_attack2.bfjoust
12 32.38  -1 fool1.bfjoust
 9 28.00   0 attack1.bfjoust
 4 18.25  -4 ais523_defend0_1.bfjoust
 3 16.25  -5 ais523_defend0.bfjoust
11 11.88  -9 ehirdomatic.bfjoust
10 10.50  -7 defend1.bfjoust
 5 10.50  -5 ais523_defend1.bfjoust
17  5.62  -4 shield.bfjoust
15  5.62  -9 programname.bfjoust
14  2.62 -10 nop.bfjoust
 8  2.62  -8 asie2.bfjoust
20  0.00   0 stuff.bfjoust
13  0.00   0 iwin.bfjoust

Let me know if you have any success with BF Joust.

CoreLife: Programming in 2 Dimensions!

For a while I've been promising to take a closer look at Dennis Luehring's list of programming games to select a few for further investigation. The list contains over 1500 links in 200 categories!

The first I've chosen is CoreLife, a 2D variant of Corewar by Brent Adams. CoreLife is one of the earliest 2D programming languages, predating Befunge by a few months.

Battles take place on a 100 × 100 memory grid. The outcome of a battle isn't uniquely determined by the initial conditions as there's a random element to the game.

Unfortunately, there's very little information about CoreLife strategies. There are 13 published battle programs. Most of these launch imps or bomb the grid with protected locations. Battle programs are often surrounded by a membrane or shield of protected locations. Despite this CoreLife has the potential to support more complex programs, for example replicators.

I've set myself the challenge of writing a replicator. First I'll attempt to write something linear and if that's successful, a square replicator! Has anyone experimented with CoreLife and if so, did you create a successful program or discover anything interesting?

For more information about programming games, take a look at Steven Robbins' list of programming games or Dennis Luehring's list of programming games.

The Recursive Universe by William Poundstone

In The Recursive Universe, William Poundstone uses Conway's Life as a vehicle to explore complexity theory and modern physics. Poundstone demonstrates how simple rules can produce complex results when applied recursively and suspects our own universe was created in a similar manner.

Conway's Game of Life was devised by John Conway in 1970. The Game of Life is played on a grid of square cells, each of which can be in one of two states, dead or alive. Three simple rules are applied repeatedly, first to the initial pattern, then to each new pattern in turn:

• a live cell with less than 2 neighbours dies
• a live cell with more than 3 neighbours dies
• a dead cell with 3 neighbours becomes a live cell

Each cell has eight neighbours, 2 horizontally, 2 vertically and 4 diagonally. Conway's Game of Life is also know as 23/3 Life. This indicate a live cell survives if it has 2 or 3 neighbours and a dead cell becomes live if it has 3 neighbours.

The Recursive Universe briefly explores some variations of Life, for example 34/34 Life. I'm currently experimenting with some other variations and will let you know the results shortly.