Wednesday 27 May 2009

The Incredible! Corewar Secret

Towards the end of 2002 a five line warrior entered the KOTH.org '94 Draft hill in fifth place, later becoming King of the Hill. Although I've often been asked about Incredible, so far I've kept its secret quiet:
Program "Incredible!" (length 5) by "John Metcalf"
;strategy tweaked away one instruction

Last battle concluded at : Sun Dec 1 17:26:58 EST 2002

# %W/ %L/ %T Name Author Score Age
1 40/ 42/ 18 Herbal Avenger Michal Janeczek 139 18
2 39/ 42/ 19 Combatra David Moore 136 7
3 24/ 11/ 65 Blowrag Metcalf/Schmidt 136 62
4 35/ 35/ 30 Mantrap Arcade Dave Hillis 136 2
5 24/ 13/ 64 Incredible! John Metcalf 135 1
6 28/ 22/ 51 Reepicheep Grabun/Metcalf 133 135
7 27/ 22/ 52 Son of Vain Oversby/Pihlaja 132 106
8 33/ 34/ 33 Cyanide Excuse Dave Hillis 131 8
9 25/ 22/ 53 Paperazor Christian Schmidt 129 79
10 28/ 27/ 45 Uninvited John Metcalf 129 125

Incredible is a standard paper/imp using an exploit to hide its true length from the KOTH script. The script has two sections. The front-end checks a warrior compiles correctly and extracts the name, author, strategy and length for the reports. The back-end runs the actual battle.

Incredible takes advantage of the fact the front-end calls pMARS with a different number of rounds to the back-end. This is used to present different code to the front-end:
;redcode-94
;name length exploit
;author John Metcalf
;strategy demonstrate how to hide a program's true length
;assert CORESIZE == 8000

for ROUNDS < 5
;the front-end sees this code
for 5
dat 0, 0
rof
rof

for ROUNDS > 4
;the back-end sees this code
;insert warrior code here
rof
end

I couldn't reveal the secret earlier because the KOTH script crashes if the code for the back-end contains errors. The script also crashes if the exploit is used to send '94 code to the '88 hill or p-space code to the no p-space hill. Unfortunately KOTH.org will be closing in a few days so it should be safe to share this now.

Monday 25 May 2009

First Results from a New Corewar Evolver

Over the last few days I've been working on a short program written in GWBasic to evolve Corewar programs. After a test run earlier today, plateau entered SAL's nano hill:
;redcode-nano
;name plateau
;author John Metcalf
;strategy evolved mad mad bomber
;strategy hit a plateau after 4 hours
;assert CORESIZE==80

spl.b #16,  <28
mov.i <-15, {-35
mov.i {-1,  {-3
mov.i <-28, <25
djn.f $-3,  <33
end
The evolver creates warriors through pure evolution. The soup is seeded with random instructions and evolution is guided only by performance against the 2007 Nano Benchmark. If a benchmark test is scoring below a certain threshold, the test breaks out early.

Evolution is by mutation only. Crossover, insertion and deletion are not implemented. The lower a warrior scores, the more it is changed by mutation. After each round, a high scoring program replaces a randomly chosen low scoring program.

Here are the plans for the next version:
  • keep a checksum of warriors to prevent duplicates in the pool
  • add a hint mode, but to keep it pure it'll hint what we don't want
  • implement crossover
  • think of a decent name (I think revolver is already taken)
Any suggestions would be greatly appreciated.