My simulator was written in C, having a text based GUI, and some debuging commands (screen shot). It takes 3 seconds for a full simulation on my Celeron 2.4G desktop. My ants are written in python and compiled using a small python script. All the stuff are put in this tar ball. Some (text) screen shot is available in the README file of the tar ball, or here.
This year I decided to take part in the contest. Purpose: to see where I am and if possible, to get the prize. The task was published Friday 5:00pm. At that time, unfortunately, I was still revising a paper with a deadline at Sunday. I even thought of postponing the paper revising (because it is rather annoying and dull, and it seemed difficult to be finished at Sunday).
Adopting the advice of my wife, I paused thinking of those ants and worked hard first on the paper submission. It turned out that all the revision was done Friday evening around 12:00pm (those ants had really a big effect on my efficiency of the revision). The paper was successfully submitted Saturday evening after a second proof read.
I started working on the simulator Saturday morning. Everything seemed unprepared. At first, I planed to wrote it in my favorite Delphi platform, but no Delphi was available on my laptop. I turned to Python, which was right there on the laptop: my wife is using it programming some web application. I am still learning python but know that it is very good for rapid prototyping. My wife helped me a lot on the grammar. It is not very difficult and by dinner time, I almost had a perfect simulator which passed almost half of the dump file test.
Now the problem was speed. Using my python-based simulator, I never got a full 100,000 round simulation done. It seems that it would take several hours to finish a full round. This was surely impractical for later evaluation of ant performance. I looked some articles on python optimization, but didn't believe that these tips could boost the speed to within 1 minute.
Saturday night is a sad night. I have to spend another several hours for paper submission, while my simulator problem was still unsettled. I decided to switch language, to C. I was confident about the performance of C, and 3-4 hours should be enough for me to rewrite the simulator, since all the code are there, and correct.
My translation started Saturday midnight, after the paper submission. Till about 6:00am, the simulator was finished, takes only several seconds for a full simulation. Now I can have a good sleep, and start thinking of writing my ants.
I got up at about 10:00am, unable to stop thinking in the bed. It was hard to programming those ants that have no memory even to remember their directions (this belief later turned out to be wrong: state space can be traded for memory, although very expensively). I went into a wrong way and believed that there is no ways of accurate programming these ants -- their performance depends on the global effect of their random walks. As a result, I choose to let ants put marks randomly, using a higher probability when they are close to the hill. This could result in a denser marked region around hill and sparsely otherwise. Then ants are programmed to have a higher probability exploring unmarked regions and have a higher probability chosing marked regions when they return with food. Using this strategy, they indeed bring more food to the hill than random walk ants.
Monday, I spent a lot of time fine tuning my ants, comparing the effectiveness of using 4 or 6 bits to mark the map, comparing the different food gain using different probabilities. Due to this, I have no time to implement food trails. Finally, my submission is two 9000+ states ants done using this strategy. That many states are due to the memory of how far they went from the hill, the further, the less probablity to do a mark.
After the submission deadline, I was astonished to learn that ants could be programmed so smart as to keep food using all kinds of traps (Dunkosmiloolump, Linepithema humile, Fourmix, ANTisocial), mark home trials so smartly (Dunkosmiloolump), block the foe hill (Frictionless Bananas), or never step into the foe hill (Road Crew). Homepages of these teams are collected here.
Another thing I learned is that functional languages are more powerful than I thought. They have good performance (Linepithema humile), advanced GUI (Dunkosmiloolump). Moreover, researchers like Peter Sewell, Alan Schmitt also took part in the contest, and have very cool solutions. It is really a profitable experience, and I think I will follow next year, get more prepared and better join some team.
