Playing with the Arduino Microcontroller Board

Here are a couple of pictures of my latest toy, the Arduino Duemilanove microcontroller. It's equipped with 16K flash memory, 1K SRAM and 0.5K EEPROM and is currently sitting on my desk, flashing out "hello world" in Morse Code. The processor is an Atmel ATMega168 running at 16MHz.

Now I just need to learn the assembly language so I can implement something useful :-)

Hostile Programming on the BF Joust Hill

For the past couple of days I've been playing on the BF Joust Hill. BF (or Brainf***) is a simple programming language with 8 instructions as follows:

Op	Description
<	move pointer to the left
>	move pointer to the right
+	increment the value stored at pointer
-	decrement the value stored at pointer
[	jump past the matching ] if the cell at pointer is 0
]	jump to the matching [
,	character input (not used by BF Joust)
.	character output (not used by BF Joust)

The object of the game is to capture the flag. The size of memory is chosen at random in the range 135 - 167. Memory is initialise to 0. Both flags are set to 128. Your flag is at the far left end of memory, the opponent's flag is to the right.

The object is to set the opponent's flag to 0. If your flag is set to 0, or your pointer runs off either end of memory, you lose.

A simple strategy would be to keep moving right, setting any non-zero memory to 0:

[>[-]-]

Against the last 15 warriors on BF Joust, this scores 76. The maximum score is 300.

What would happen if we build a decoy to slow down the opponent? We could set a few non-zero memory cells next to the flag:

>+>->+>->+>->+>->+>-[>[-]-]

The new score is 103. Some memory cells are incremented to 1, others are decremented to -1 (255). It doesn't matter whether the opponent is using [-] or [+] to set memory to zero, it will be delayed for hundreds of cycles.

How can we avoid wasting time if the opponent has a similar decoy? One technique is to increment the memory cell just before entering the decrement loop:

>+>->+>->+>->+>->+>-[>+[-]-]

If there's a -1 decoy, it's changed to 0 and the [-] loop is never executed. The new code scores 140.

We can prevent the opponent from benefiting from a similar technique as follows:

>+++>--->+++>--->+++>--->+++>--->+++>---[>+[-]-]

This scores 181 :-)

Finally, we know the enemy's flag is in the memory range 135-167. We can quickly skip ahead to location 135:

>+++>--->+++>--->+++>--->+++>--->+++>---
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>
+[>+[-]-]

Scoring 209!

Rank             Program  TOT
-----------------------------
  1      woggle_050109_2  246
  2              joust12  240
  3      woggle_050109_1  228
  4      woggle_060109_3  213
* 5           Challenger  209
  6      wooble_231208_2  188
  7       ehird_060109_1  143
  8    BPilgrim_271208_1  132
  9      wooble_191208_1  130
 10      ais523_201208_1  121
 11       ehird_201208_4  103
 12    BPilgrim_271208_2   77
 13       ehird_191208_3   55
 14       comex_241208_1   46
 15       comex_241208_3   16
 16       comex_241208_2   16
-----------------------------

Let me know if you've discovered a better technique, or if you can beat 209.

Hello World for the RSSB Virtual Computer

The RSSB virtual computer has a single instruction, reverse subtract and skip if borrow. Each instruction has one operand, a pointer into memory. RSSB subtracts the accumulator from the contents of memory and the result is stored in both. If the accumulator was greater than the number in memory, the next instruction is skipped.

Jumps can be implemented by manipulating the instruction pointer at memory location 0, which normally requires 4 instructions. A conditional jump requires 6 instructions. Other special locations are as follows:

1. accumulator
2. always contains 0
3. character input
4. character output

The four lines of code below demonstrate the shortest jump:

        rssb   acc       ; set acc to 0
        rssb   $+2       ; set acc to loop offset
        rssb   ip        ; subtract acc from ip
        rssb   $-loop    ; the loop offset

The code below implements hello world for the RSSB virtual computer. The sum deserves an explanation. Each character is subtracted from sum until sum passes zero, indicating all character have been printed. The final value of sum is the offset required by the conditional jump!

loop    rssb   acc       ; acc = character from ptr
ptr     rssb   hello        

        rssb   out       ; display character

        rssb   zero      ; acc = -acc

        rssb   zero      ; always skipped

        rssb   sum       ; subtract acc from sum

        rssb   ip        ; skipped if sum is <0
                         ; otherwise jump to 0

one     rssb   acc       ; subtract 1 from ptr
        rssb   one
        rssb   ptr

        rssb   acc       ; jump to loop
        rssb   loopoff
        rssb   ip
loopoff rssb   $-loop

sum     rssb   -1116

        rssb   33        ; '!'
        rssb   100       ; 'd'
        rssb   108       ; 'l'
        rssb   114       ; 'r'
        rssb   111       ; 'o'
        rssb   87        ; 'W'
        rssb   32        ; ' '
        rssb   44        ; ','
        rssb   111       ; 'o'
        rssb   108       ; 'l'
        rssb   108       ; 'l'
        rssb   101       ; 'e'
hello   rssb   72        ; 'H'

If you can improve the code above, or you've seen any other programs inplemented with RSSB, please leave a message below.

The Ultimate RISC, One Instruction Set Computers

A One Instruction Set Computer is a virtual computer designed to use only one instruction. There are two common methods to implement a OISC:

Reverse Subtract and Skip if Borrow

The instruction has one operand which points to a memory location. The program counter is stored at location 0 and the accumulator at location 1. Location 2 always contains zero, location 3 is used for input and location 4 for output.

RSSB subtracts the accumulator from the contents of a memory location, storing the result in both.  If the accumulator was greater than the memory location, the next instruction will be skipped. Jumps can be implemented by manipulating location 0.

Subtract and Branch if Negative

SBN requires three operands, a, b and c.  The contents of memory location a is subtracted from the contents of b and the result is stored in b. If the value originally stored in a was greater than the value in b, SBN will jump to c. A variation on the theme is Subtract and Branch unless Positive.

I'll publish my implementation in Redcode shortly. In the meantime, why not take a look at projects listed below. If you're aware of any other implementations, please leave a comment with the details.

• Luke Valenty built a SBN machine using 7400 series logic gates
  
• Clive Gifford has written a SUBLEQ self-interpreter
• Oleg Mazonka implemented a SUBLEQ interpreter in C++
• Safalra has designed a variation called MISC

What can you Write in 128 Bytes?

In contrast to the ever increasing memory available, a number of programmers are choosing to demonstrate their coding prowess by squeezing as much as possible into an incredibly tiny program. It has become a popular pastime to code an impressive graphical display in either 128 or 256 bytes.

Before zooming off to try this for yourself, why not check out some of the competition? Five of the best are listed below, and also my own contribution.

---

OKO by Ind. The coloured rings sway gently. Good use of colour.

---

Interference by New Generation Crew. A fast moving interference pattern between two sets of rings. Supplied with source code.

---

Ctverecky by RRRola. A chaotic, spiralling pattern. Only 93 bytes long. Supplied with source code.

---

Corkscrewed by lord Kelvin - a smooth, gentle swirl slowly draws you in. Great use of colour. Supplied with source code.

---

Color Dream by Digimind - a chaotic looking swarm of spheres. Impressive in motion.

---

Plasma Wave by John Metcalf - my own contribution. A display of flowing plasma. Supplied with source code.

---

If there's a program you think I should have included, or you want to show off your own demo, please leave a comment below.

Core War - Hostile Programming

Core War is a game from the 80's, played between computer programs written in Redcode, a language similar to assembly.  The programmers design their battle programs to remove opponents from the memory of the MARS virtual computer by any means possible.

Some of the simpler techniques include blindly overwriting memory, searching for the opponent or spawning off new processes. These are commonly known as stone, scissors, paper after the popular playground game.  Stone usually wins against scissors, scissors normally defeat paper, and paper mostly beats stone.

Here's an example of a typical Core War program:

org   wipe

step  equ 5
first equ bomb-10

bomb:mov.i #1,       -1

ptr: sub   #step,    #first
wipe:jmz.f ptr,      @ptr

mov   bomb,     >ptr
djn.f wipe,     {ptr-5

end

This simple example of scissors once held a 20 point lead over it's rivals. The first instruction is never executed, it's the bomb used to overwrite opponents.  The next two instructions form a loop which look through memory for an opponent, and the final two instructions actually overwrite it.

Core War is still going strong, and celebrates it's 25th anniversary in 2009. If you'd like to discover more about Core War, here are the top resources:

• The Beginner's Guide to Redcode will teach you the language of Core War
• pMARS is a portable implementation of the Core War virtual machine
• Core War Tutorials exist on virtually every aspect of the game
• Koenigstuhl is an archive of thousands of published Core War programs
• SAL organises a number of on-going king of the hill tournaments
• sfghoul and impomatic report the latest Core War news on their blogs
• #corewars is the official Core War discussion channel, hosted by irc.freenode.net

What are your experiences with Core War, have you ever had any success?

Programming in Strange Places!

Earlier this month I spent a week in Cornwall without access to a computer. In the true spirit of recreational programmers everywhere, this didn't curtail my programming activity. I managed to discover a number of solutions to the Semaphore Problem in Redcode while watching the waves!

However, programming on the beach, public transport, restaurants and even a theme park appear pretty normal alongside the place where I wrote Koch Curve for the Sinclair Spectrum.

One October night 14 years ago I took shelter from the wind and rain in Victoria Cave.  After setting up for the night and studying the map, I eventually tried to code an idea I'd had a few days earlier.

Working by candlelight on scraps of paper I programmed, optimized and hand assembled Koch Curve for the Speccy's Z80. Perhaps the surroundings explain the strange names I used for labels!

What's the strangest place you've written a program? I'd love to know.