New website

Computer Nerd Stuff (ICFP 2004)

In 2004, Michael Thon, Andreas Pfeil and me participated in the ICFP Programming Contest 2004 (if you are interested in participating in the future check this). We also participated together in the ACM ICPC 2003. You can see us discussing, drawing, hacking, playing, ocassionally having visitors and the sun-rise and sun-set in a 300 times speeded-up movie: high-quality(~100megs).

This competition lasted for 72 hours, hence has been an extreme experience pushing our limits on how much we can work in three days straight. It was a lot of fun, too, and a lot of pizza. In fact the given task made hungry. The task was to program ants to collect food from a food place to the own ant hill in a simulated ant world. In the competition, two teams of ants would compete against each other in a simulated world, so the ants had to be programmed to collect the food quickly, protect the food brought to the ant hill from being stolen by the other team and possibly steal the food from the other team. Each ant in one team had the same code and the only possible communication was through markers an ant could set for a field of the world and the ants from the own team could sense from neighbouring fields.

The first hour of the competition we spent setting up the webcam ;-) The first thing we had to do was writing the simulator for the ant world (based on a hexagonal grid). We split up the simulator in different parts each to be written by one of us. This worked - thanks to Andreas' CVS knowledge - perfectly and only around 6 hours after the competition started we had finished an ant world simulator working without any errors. I had actually the idea to improve it and turn it into a gdb-like debugger for the ants. Thanks to Andreas skills e.g. with the readline-library he perferctionized my rudimentary debugger to a powerful tool with elaborate ASCII-art graphical output.

Michael had a lot of good ideas for the strategy for the ants. The strategy of our ants was to leave two sorts of marker particles: pioneer ants would first leave the ant-hill in almost straight lines and leave particles which would help an ant with food to quickly find back to the ant hill. Ants who had found a piece of food would leave a trace when carrying food back so that an ant without food could quickly find a food source. Later we refined the idea so that a certain fraction of ants would destroy food traces when a food source exhausted. Michael also had a really ingenious idea: he positioned the ants in a S-shape on the anthill in such a fashion that it was totally impossible for the other team to steal our food.

We were all writing a lot of ant-code and discussing a lot of ant strategies. Because we were soon sick of drawing hexagonal grids all the time, we printed out one on a slide and projected it onto the white board.

The ants had to be programmed as finite state machines, meaning the code looked something like "if you are in state 0 and smell a marker, go into state 1; if you are in state 1, go one step forward and into state 2; ...". Naturally this was not the right language to express our ideas. Andreas could program some simple routines, but we soon needed a sort of "high-level" language understanding macros and making it easier to write ant-code and reuse it. Our first attempts to write such a "compiler" in Python failed. The second evening I had an amazingly simple idea of how to use the C-compiler to do all this for us: I wrote a couple of functions and then we could write an ant-C program, compile it and run this executable which would output the actual ant code. It turned out to be as powerful as simple - though Andreas and Michael were first laughing at me.

Now we were all implementing the strategies. Each of us did sometimes a little modification to the ant-code and then ran a simulation against the other's ant-code. It was exciting to see on the screen what was happening and discuss it with the others. If you think that I selpt the second night, you are wrong! I was in my room developing a system of how the ants could pass markers in such a way that each ant could figure where it is in the anthill by counting how much time it needed until the marker was passed to it.

The competition was an extraordinary experience. Many thanks to Andreas and Michael.

I am not responsible for the content of other pages that this page links to, nor do such pages necessarily agree with my own opinion.