## Friday, 6 February 2009

### 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:

OpDescription
<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
,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.

1. My highest score is 254 ;-)

2. Proof or it didn't happen

3. Sorry John... 264 :-)

4. Anonymous:

I'll give everyone chance to have a go before I post my 254 :-)

Roy:

Nice work, I guess I'll have to try harder!

5. 225

>--------------------
>--------------------
>--------------------
>--------------------
>--------------------
>--------------------
>++++
>----
>++++
>----
>++++
>----
>++++
>----
>++++
>----
>>>>>>>>>>>>>>>>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

6. 265. BF Joust seemed like it might be a more accessible version of Core Wars, but I see it's much too susceptible to stupid tricks, and there's only one winning strategy (set decoys, race to the right side of the map, methodically zero every cell in order from left to right). The only variation comes in modifying that strategy.

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

7. Unroll the last several inner loops for 277.
>++++++++++++++++++++
>--------------------
>--------------------
>++++++++++++++++++++
>++++++++++++++++++++
>--------------------
>--------------------
>++++++++++++++++++++
>++++++++++++++++++++
>++++
>++++
>++++
>----
>----
>----
>----
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>
>------[+]>------[+]>------[+]>------[+]
>------[+]>------[+]>------[+]>------[+]
>------[+]>------[+]>++++++[-]>++++++[-]
>---------[+]>----------[+]>----------[+]
>--------------------------------
--------------------------------
--------------------------------
--------------------------------
(repeat the last four lines ad nauseam)

8. Nice work, my 254 no longer looks good!

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