ICFP Programming Contest 2004

I finally managed to participate in the ICFP programming contest this year. While I had followed the contest in previous years, this was the first time I actually had time to sit down and start hacking.

My team, random boke, consisted of just one member, namely me: Christoph Breitkopf.

My submissions: lightning entry, final submission.

Timeline (local time):

Friday, 18:05 At work: Downloaded and printed task description.
Went shopping.
At home, started working on simulator.
Saturday, 01:20 My simulator exactly reproduces the sample simulator trace.
Saturday, 06:30 Woke up, wrote simple ant compiler.
Tested some ant programs, all bad.
Decided on random ant generation.
Breakfast, shopping.
Saturday, 11:00 - 13:00 Wrote random ant generator and testing scripts.
The random ants suck.
My simulator is too slow.
Saturday, 15:00 Watch the random ants get slowly better. They still suck, though.
Slightly improved the scripts.
Do some profiling on the simulator, to no avail.
Wrote slightly improved version of the ant in the task description by hand.
Saturday, 17:50 Can't think up a good team name. Drat.
Submitted the simple hand-written ant and the best random ant so far for the lightning entry.
Saturday, 20:00 Went to work to start random ant generation on various systems that have nothing else to do over the weekend. No really fast machines, though.
Saturday, 22:30 Home again. Try some more hand written ants. No luck.
Start randomly mutating the simple hand-written ant. This looks a bit better than the purely random ones.
Went to sleep.
Sunday No programming. Just checked the progress of the random mutations. Results are not encouraging.
Sunday, 16:00 Finally search the web for genetic programming. Seems I'm doing just about everything wrong.
Wrote trivial program to combine two ants.
Does not seem to produce better results than random mutation.
Wrote script test a pool of ants, just keeping the better ones of each generation, and replacing the others by new random ones or mutations.
Does not work too well, either. Left it running over night.
Monday morning Nothing interesting continued to happen.
Went to work. Worked.
Monday, 15:00 Felt burnt-out. Decided to submit, since I didn't see any chance of doing better in the remaining time.
Wrote a scheme program to strip the unused states from randomly generated ants. Strangely enough, 5810 states remain.
Submitted a refined simple hand-programmed ant, and the best randomly generated one.
Breathed a deep sight of relief ;-)

The simulator

Written in C because of familiarity with the language. It would have taken me much longer (I think) to write an equally well performing simulator in a functional language. OTOH this would probably have been much stabler and easier to read.

I had the simulator exactly reproducing the sample dump after about 4 hours of programming. Decided not to further improve it, but rather start writing ants.

Later it turned out that my simulator was a bit slow for what I was using it for. My simulator takes about 0.8 seconds to perform a 100000 generations simulation on one of the sample worlds on a 2533 MHz Pentium 4. That's more than 10 seconds for a match of two ants on all ten sample worlds. There's probably an order of magnitude of speed improvement possible in the data structure alone (for example, determining dying ants). However, the big showstoppers seem no to be the data structures, but the division in the RNG and branch prediction. I have no idea if cache effects play a role, too (not enough time to use vtune or oprofile right now). (2004-06-07 ran it through cachegrind. No L2 misses to speak of.) I have tried a faster RNG w/o division, but it was not that much faster, so I kept the original. As for branch prediction in the Flip instruction, what can one do?

Ant compiler

My ant programming language remained rather crude, mostly because I gave up on manual programming way too early.

The compiler is written in Scheme and supports symbolic names for states, and can nest instructions. Here is the ant from the task description in my ant language:

(define get-food
  (if (sense ahead food)
      (if move
	  (if pickup go-home get-food)

(define turn-get-food
  (if (flip 3)
      (turn left get-food)
      (if (flip 2)
	  (turn right get-food)
	  (if move get-food turn-get-food))))

(define go-home
  (if (sense ahead home)
      (if move drop-food go-home)

(define drop-food (drop get-food))

(define turn-go-home
  (if (flip 3)
      (turn left go-home)
      (if (flip 2)
	  (turn right go-home)
	  (if move go-home turn-go-home))))

What's missing from the language are parameterized macros. I certainly would have added those if I had continued to write ants by hand.

Random ant generation

I wrote a few simple ants by hand, starting from the one in the task description. However, I was really bad at this. The best I was able to do was extending the sample ant so that it would not pick up food from its home. As soon as I attempted to use markers in some way, or to use different behaviors, those ants would lose to the simple ant on the sample worlds. I was very discouraged by that and decided to use another approach: random ant generation.

In hindsight, this was a probably bad idea, because I had never done anything of that sort (genetic programming, or whatnot) before. To make matters worse, I proceeded not by reading up on the method, but by hacking away.

I first wrote a mini program to generate n completely random states, and a shell script to repeatedly call this and run a contest against the slightly improved sample ant, and keep the ant if its score exceeded the best so far. This got my up to score 20/20 (that is equally as good - or bad - as the sample ant) in a few thousand runs.

I later changed this to keep the best ant so far, and just randomly mutate a few of its states. This started off much faster and improved to score 24 (vs 16 for the sample ant).

However, this still seemed very bad, and the ants would stop getting better rather quickly. So on sunday afternoon I finally did some reading on genetic programming. Seems that having a larger gene pool as well as combining two genes as the preferred method of getting new ones were the important things. I could not think of a good combination function though - just taking a few random stated from a second ant did not work any better than mutating just one ant.

At this point I did consider going back to writing ants by hand, but given that I had to work on monday, I just let the script run over night, and then submitted my hand-written ant, and the best one randomly mutated from the hand-written one.

The team name

About 10 minutes before the deadline for the lightning submission, I suddenly realized that I had no idea what to call my ‘team’.

When no really good idea turned up after 1 minute, I settled on ‘random boke’ - random for the randomly generated ants, and boke, japanese for senile, for how I felt at the moment. (For another meaning of boke, see my page on bokeh.)

Lessons learned

Copyright © 2004 Christoph Breitkopf

Page history:

2005-01-24 Fixed some spelling errors.
2004-06-10 Added description and submissions.
2004-06-08 First version containing only the timeline.