ICFP 2004

• General
• The Task
• Our Approach
• Finished and Improved
• Screenshots
• Survey

ICFP stands for International Conference on Functional Programming. They organise an anual interational programming contest. See the ICFP 2004 Contest Website

Jörg, Allan and me attended the contest. Our team name was Formicoideas and we used primary haskell. Sorry, but we used also java to implement a graphical user frontend to be able to test our solutions.

We scored place 85 and 252 with our two submissions. It was really unfortunate since we found a very simple bug in our ant program just after the final submission, which caused the ants to stop after some time (pheromone dead lock)

Well the contest was about ants and the biological name for the family is Formicoidea.

Because Allan lives in Edinburgh and we live in Leipzig we have been forced to program territorial distributed. This worked great since we used CVS, Teamspeak and ICQ. I would say the productivity was larger than if we all would have worked together in the labs of the university or somewhere else. The reason is that you know you computer and the enviroment and it is calm if you need it.

The task description and some maps can be downloaded from the ICFP contest webpage or from here task.tgz.

Here a rough decription what it was about: The task was to write a program that controls an ant. It was basicly a finite state machine (FSM) that had to be developed. The programming language was very low level with absolute jumps and so on. Please note that there is no memory in a FSM, so cannot store anything.

There are two teams the red and the black colony. Every colony has an anthill of the same size and the world consists of hexogonal cells. There are rocky cells where you can't go on and there are cells with food. The overall goal was to bring as many food as possible to your anthill. In order to perform that the ant can mark a cell with 6 different markers and is able to sense the own cell and the ahead, left and right cell.

1. order to simplify this task we decided to build a translator from a

slightly higher level language than that of the ant finite state machine language. This language is called pheromone and the compiler is phec for pheromone compiler. We also built a Simulator as described in the task description to evaluate our ant programs, and a Java front end to visually deploy the simulator in order to aid debugging of the ant programs.

Here the modules we have written:

• Phec (Pheromone Compiler)
• Simulator
• Frontend

According to the task the ants are controlled by a final state machine described by an assembler like low level code. Alls ants work independend. The ants have no memory, their state is defined by the current line of code that is executed. Of couse it is possible to simulate something like a memory by splitting the program into special address ranges. Therefor it is necessary to have a high level language with macros, block multiplication and more, see Phec language. Ants can leave marks on fields they run over, there are six markers that can be turned on or off. That means we can save 6 bits of information on every field.

The basic behaviours of an ant are:

1. explore and search for food
2. bring food back home

1. is necessary that an ant easily finds the way to the hill. Our approach is an initial spreading of path information. Initially all ants start at the home base. The idea is that some ants are choosen to run nearly straigth away from the home base and on every field thay mark the direction to go back to the home base. First we thought about writing a number 0..5 in every field to the direction to the ant hill within a hexagon. The disadvantage of this approach is that we need 3 bits (we have only 6) and every ant would have to remember its direction through its whole live. Normally ant's don't know the direction they are looking, it would have been necessary to split the whole code into 6 address ranges and keep tracking of the current direction whatever the ant is doing.

We choose an different approach that overcomes this problems. The idea is to code an gradient field. It is descending the more distance the ant has from the home base. For this field only 2 bits are needed. Like described at the start of the match some ants will start running away from the home base and write gradient information 3,2,1,3,2,1,3,? and so on. The value 0 is reserved for an empty field without way mark. If an ant has found food and searches for the home base it runs straigt until it finds a field with gradient information. Then it starts turning around and searchs for a neigbour field with (gradient + 1), the field is ascending in direction towards the home base.

The same idea is reused for faster finding the food hills. If an ants finds food, it picks it up and then moves back to the home base. During walking back it marks the way to the food with the gradient information. We wanted to have someting like in nature: unused food tracks should get weaker over time. Therefor we use the last free 2 bits to give the food track a strength information. Ants that carry food will write the gradient with strength 3.

Normal ants are randomly exploring the landscape and hope to find food. If they find an food track they will follow it and decrement the strength of the track by one. If the food at a certain place is empty the tracks that lead the this place will be removed over time.

Yes that is our approach: 2 bits for home base gradient, 2 bits for food gradient and 2 bits for food path strength. The approch is tested and works. For the given sample maps the average time to collect all food and bring it to the home base is 50,000 steps.

Unfortunatelly we didn't get the algorithm to work until the contest submission stop. We would have needed 4 hours more :( We submitted two unfinished versions. One that can't follow food tracks and the other follows them but with a bug that leads to a dead lock. Nevertheless we finished the algorithm, now it works fine and we are looking for testing it against the winner ant :)

You can type make all

1. the tools directory to compile everything. The other option you have is to compile modules (Phec, Simulator and Frontend) seperatly be typeing make inside their directories. You will need ghc (haskell compiler) version 6.2

and the java sdk installed. Note that the java sdk is just needed if you want to recompile the frontend. Because the class files are included a java runtime is sufficient.

1. the tools directory is a ./run.sh shell script to run

the simulator with the graphical front end, this can be used with

./run.sh task/sample0.world --red=source2/initial.phec 
        --black=Simulator/test.prog

Please note that the world files have to be downloaded sperately (task.tgz).

1. the above example the file source2/initial.phec is compiled first whereas the Simulator/test.prog is allready compiled and is used just as it is.

There are a plenty of commandline switches of the main program. Start run -h for a usage information.

For example there is a console front end included. The following call makes the simulator run for 100 steps:

./run <del>world=task/sample0.world </del>red=testing/initial.phec 
      <del>black=Simulator/test.prog </del>console -s100

To run the simulator without any frontend use:

./run <del>world=task/sample0.world </del>red=testing/initial.phec 
      --black=Simulator/test.prog 

1. any case you will get a final result, who as won and so on.

We submitted our submission 3 minutes before the deadline and - how to say - I was really nervous. It is every year a last minute hack!

The submission can be downloaded from the panel beside (formicoideas.tgz).

I let sloccount run over the whole code we produced in the 3 days. Here the results:

SLOC    Directory       SLOC-by-Language (Sorted)
747     Simulator       haskell=747
677     Phec            haskell=677
440     Frontend        java=438,sh=2
209     top_dir         haskell=187,perl=16,sh=6


Totals grouped by language (dominant language first):
haskell:       1611 (77.71%)
java:           438 (21.13%)
perl:            16 (0.77%)
sh:               8 (0.39%)

Total Physical Source Lines of Code (SLOC)                = 2,073
Development Effort Estimate, Person-Years (Person-Months) = 0.43 (5.16)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 0.39 (4.66)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 1.11
Total Estimated Cost to Develop                           = $ 58,086
 (average salary = $56,286/year, overhead = 2.40).

ich hab mal etwas zusammengegoogelt: http://icfp06.cs.uchicago.edu/ sagt: Contest-Veranstalter sind http://www.cs.cmu.edu/~crary/ und http://www.cs.cmu.edu/~rwh/

Wenn es also aus deren Arbeitsgebiet ist, dann etwas mit Programmiersprachen/Übersetzen/Typprüfen und/oder was mit Sicherheit (Protokolle, versteckte Information)

Einer der graduate students http://www.cs.cmu.edu/~tom7/ hat diese Webseite: http://escape.spacebar.org/ Das scheint ein richtiger Spiel-Hacker zu sein. (Das Spiel selbst ist aber nicht open source?)

Johannes hat noch folgendes herausgefunden nachdem ers sich auch den icfp-contest-mailinglisten eingeschrieben hat:

icfpcontest-discuss list run by spoons at CS.CMU.EDU, tom7 at CS.CMU.EDU

das sind Daniel Spoonhower http://www.cs.cmu.edu/~spoons/ (arbeitsgebiet: garbage collection) und der schon erwähnte Tom Murphy http://escape.spacebar.org/ - das spiel ist übrigens ziemlich OK. aber viele gimmicks dabei, die man sich gar nicht alle merken kann.

also mein tipp ist nach wie vor, daß der contest etwas mit dem spiel zu tun hat.

was bedeutet eigentlich das bild: http://icfpcontest.org/teaser.gif labyrinth? grabkammer? hieroglyphen? sanduhr?

Der Codex hat am Anfang einige regelmäßige Struktur, z. B.

$ od -x codex/codex.umz

003240 0000 0000 0000 ff00 b8ff b8b8 b8b8 b8b8 0003260 b8b8 b8b8 b8b8 b8b8 b8b8 b8b8 b8b8 b8b8 * 0003340 b8b8 b8b8 b8b8 ffb8 deff dede dede dede 0003360 dede dede dede dede dede dede dede dede * 0003440 dede dede dede ffde fbff fbfb fbfb fbfb 0003460 fbfb fbfb fbfb fbfb fbfb fbfb fbfb fbfb * 0003540 fbfb fbfb fbfb fffb ffff ffff ffff ffff 0003560 ffff ffff ffff ffff ffff ffff ffff ffff * 0003640 ffff ffff ffff ffff b8ff b8b8 b8b8 b8b8 0003660 b8b8 b8b8 b8b8 b8b8 b8b8 b8b8 b8b8 b8b8 * 0003740 b8b8 b8b8 d3b8 ffd3 ffff ffff ffff ffff 0003760 ffff ffff ffff ffff ffff ffff ffff ffff *

und einige Strings drin (haben die anderen auch schon bemerkt)

waldmann@afa:~/icfp06> strings codex/codex.umz | tail

Tga'G abulafiabad wolf lambda roswell area51 i love bees 42 lullus surmount currents

vielleicht kann man noch einige statistische Tests laufen lassen (häufige bitfolgen usw.)

meta-comment: wie geht hier <CODE> .. </CODE>?

Ich hab mal die Buchstaben (Bytes) im Codex durchgezählt. Bei Gleichverteilung wäre jedes Byte 2346960/256 = 9167.8 mal dran.

Tatsächlich kommen alle Bytes vor, die Hitliste sieht so aus:

(8894,('=',61)) (8896,('\155',155))

(8929,('\128',128)) (8930,('A',65)) (8966,('\224',224)) …

(9370,('\191',191)) (9376,('\146',146)) (9440,('d',100))

(9793,('\184',184)) (9818,('\DEL',127)) (11040,('\NUL',0)) (11273,('\255',255))

Ich würde sagen, die letzten vier sind deutlich (5 .. 10 %) über den anderen, also haben sie eine Bedeutung.

ich dachte, vielleicht ist es ein Rechteck (Bild), welche Abmessungen hat es dann?

Die Länge der Datei ist 2346960. Die Primfaktoren sind:

waldmann@dfa:~/icfp06$ factor 2346960 2346960: 2 2 2 2 3 5 7 11 127

immerhin 127 ist eventuell kein Zufall, und davor steht das Produkt (2*3)*(2*5)*(2*7)*(2*11)

kann mal jemand die bytes als Farben interpretieren und ein paar Rechtecke zeichnen? (und Resultat oder Quelltext hier uploaden)

3 byte (d. h. 3 Farben) * 1024×768 (XGA) = 2359296, das liegt immerhin in der Nähe.

so jetzt noch eine obskure beobachtung: vielleicht ist es ein ppm-file? http://de.wikipedia.org/wiki/Portable_Pixmap

wenn man diese drei Zeilen davorschreibt:

P6

889 880

255

und dann codex.ppm nennt und mit “display” (imagemagick) anschaut, dann … sieht man dann etwas? Kanäle auf dem Mars?

Man sieht, dass am Anfang Datei was anderes passiert, ansonsten ist es huebsch verrauscht

ja, es läßt sich auch praktisch nicht komprimieren:

waldmann@afa:~/icfp06> ls -l

-rw-rr 1 waldmann users 2354909 2006-07-20 19:21 codex.bz2

-rw-rr 1 waldmann users 2343322 2006-07-20 19:21 codex.gz

-rw-rr 1 waldmann users 2343456 2006-07-20 19:21 codex.zip

die Marskanäle sind wohl auch Zufall (eine gewürfelte Datei gleicher Größe sieht genauso aus)

Da sind noch ein paar lustige Strings drin am Anfan der Datei:

  33c ignoti et quasi occulti

354 welldonedaed si luap

  38f 5Evan Chan was murdered

  3a8 fnord

  1628 abracadabra

1634 eval

 1a38 evalso dark the con of man
  * !! das ist ein Schlüsselsatz aus "Da Vinci Code"

 1a74 GIF89a@ -- !!

  21dc tycon mismatch -- so hieß das Team der jetzigen Veranstalter beim vorigen contest

hier Erklärung zu Evan Chan: http://en.wikipedia.org/wiki/Cloudmakers

und hier “count welldone/tsarogy”: http://en.wikipedia.org/wiki/Count_of_St_Germain

da ist tatsächlich ein GIF-Bild drin (man kann nach Zeichenkette “GIF89a” suchen und dann die folgenden ca. 300 byte nehmen) auf dem Bild steht “CBV” und ein Dreieck mit zwei Kreisen (siehe oben auf dieser seite)