The Mercury Mercurians' ICFP 2004 programming contest entry


This page describes our team's effort in the 2004 ICFP Programming Contest.

The team members

This year the Merry Mercurians team consisted of three members of the University of Melbourne Department of Computer Science and Software Engineering :

Ralph Becket
A research fellow with the Mercury and HAL programming language groups.
Julien Fischer
A doctoral research student investigating automatic proof of termination in Mercury programs (it works, too!)
Ian MacLarty
The newest member of the group, a masters student working on declarative debugging for Mercury programs.
And here you can see a rather unflattering team photo. Julien is on the left, Ralph is in the middle, and Ian is on the right.

Mercury

Mercury is a highly efficient, purely declarative logic/functional programming language. It might lack the syntactic brevity of Haskell, but our error messages are a joy to behold. Unlike some declarative languages, you don't need a Rosetta Stone and a twisty mind to understand what the Mercury compiler tells you. This was a great help building our tools for the contest: the simulator ran perfectly first time, if you can believe such a thing!

We constructed a number of tools.

The simulator
Pretty much a direct translation of the specification in the Task Description.
A text-based graphical viewer
Handy for early testing while the graphical viewer was being developed (you had to run this one in a huge window with a tiny font; not recommended for users with poor eyesight). Here's a sample of the output showing star.ant at work, with visible trails for the red ants.
A graphical viewer
What can we say? Invaluable. Written by Julien using the Mercury OpenGL binding.
Compilers for two different `high level' ant programming languages
Ralph and Ian disagreed slightly on what a good language would look like, and both ended up with something slightly horrible. Here's a sample of Ralph's language, giving the code for star.ant and here's a sample of Ian's language, giving the code for ian5.ant . Julien even implemented a simple optimizer for Ralph's language.

Solution 1: trailer.ant

trailer.ant was primarily Ralph's effort. On the sample worlds, trailer.ant and ian5.ant performed equally well. Which Ralph felt was a shame because trailer.ant is the more sophisticated of the two.

trailer.ant uses four kinds of ant:

  1. Ants initially on the periphery of the anthill perform a random walk looking for food, leaving behind a trail of markers a b c d e f a b c ... When these ants encounter food, they run their trail through as much of it as possible before moving on to look for more food. The length of the trail sequence makes confusion between trails much less likely -- this was a genuine issue, and ultimately even required that trails not be allowed to cross one another.
  2. Ants not initially on the periphery of the anthill disperse slowly and at random (to avoid congestion) and follow the trails from the nest to the food. When they find food they pick it up and follow the trail back. If a returning ant bumps into a friend, it drops its food item, turns around and goes to get more. This led to a kind of `bucket chain' behaviour.
  3. Three ants in the nest identify themselves at the start of a run. One `fortress' ant sits still and just sits on any food placed in front of it. Two `hoover' ants would wander around the nest at random picking up food left by the gathering ants and bring it to the `fortress' ant. This worked reasonably well as a safeguard against theft by enemy ants.
  4. Random ants -- well, it's a simple strategy for getting out of tight spots!

Solution 2: ian5.ant

ian5.ant was Ian's baby:

  1. Initially a 3 ant triangular fortress is formed with each ant in the fortress continually looking for food in surrounding cells and bringing any food it finds into the fortress. Since no ant in the fortress can be surrounded by more that 4 ants, the fortress is impenetrable.
  2. All other ants leave home and wonder randomly around the map looking for food. They leave behind a home trail that randomly runs out.
  3. When an ant discovers food it marks the surrounding area with food markers, then it returns home by randomly wondering until it reaches a home marker. It will try to stay with a home-marked area until it finds its home. When inside its base camp an ant will stay there until it finds the fortress at which point it will drop it's food. A fortress ant will then detect and collect the food.
  4. When an ant finds a food marker, it tries to stay in the food area until it finds food.
  5. That's it.

A truly voracious ant (but too late): star.ant

As is often the case with ICFP contest, the best ideas don't occur until after the deadline. But for your edification, we present star.ant , an ant of truly frightening efficiency. Ralph's rather proud of this one, but then a sense of timing was never his long suit.

star.ant works like this:

  1. The foremost triangle of ants identify themselves at the start of the run and form a `fortress' where all food will be stored and which, barring unbelievable bad luck, is invulnerable. The front two fortress ants just remain stock still for the rest of the run, while the rear one (eventually) lays out a trail of c markers before returning to its `home' spot in the fortress:
                             + + + + + +     
                            + + + + + + +    
                           + + + + + + + +   
                          + + + + + + + + +  
                         + + + + + + + + + + 
                        c c c c c c c c c R R
                         + + + + + + + + + R 
                          + + + + + + + + +  
                           + + + + + + + +   
                            + + + + + + +    
                             + + + + + +     
    
    Returning ants wander around in the nest until they hit a c, whereupon they bounce back and forth until they can drop their food in front of the rear `fortress' ant, who quickly snaps it up and returns it to his spot.
  2. Every other ant around the periphery then starts laying a trail [blank] a b [blank] a b ... which returning ants will follow when bringing food back to the nest:
                                    .   .   .
                   .               .   .   .
                    .             b   b   b
                 .   b           a   a   a
                  .   a 
               .   b           b   b   b
                .   a   b     a   a   a
                 b       a
                  a   b      + + + + + +   a b   a b   a b   a b ...
                       a    + + + + + + +    
                    b      + + + + + + + +   a b   a b   a b   a b ...
                     a    + + + + + + + + +  
                         + + + + + + + + + +   a b   a b   a b   a b ...
                        c c c c c c c c c R R
    .. b a   b a   b a   + + + + + + + + + R 
                          + + + + + + + + +  
     ... b a   b a   b a   + + + + + + + +   
                            + + + + + + +   a
       ... b a   b a   b a   + + + + + +     b
                                          a
                             a   a   a     b   a
                            b   b   b           b
                                             a   .
                          a   a   a           b   .
                         b   b   b             .
                        .   .   .               .
                       .   .   .
    
    Returning ants just wander around at random until they hit an a or b , orient themselves, and charge straight back to the nest.
  3. All the remaining ants start out as hunters: a hunter performs a random walk across the board looking for food. If if finds a clump of food, it marks the centre and lays out a star of trails [blank] d e [blank] d e ... extending out in all directions:
                       .                 .    
                        .               .    
                         e             e    
                          d           d    
                        
                            e       e    
                             d     d    
                          
                             5 5 5 5
             ...e d   e d   5 5 5 5   d e   d e ...
                           5 5 5 5
                        
                             d     d    
                            e       e    
                          
                          d           d    
                         e             e    
                        .               .    
                       .                 .    
    
    Other hunter ants that stumble upon a d or e quickly orient themselves and charge straight towards the food.
  4. Once the food at a spot has been exhasted, ants will randomly erase the food trails in order to avoid wasting useful foraging time.
  5. It's a beautiful thing to watch: after a short while there are paths leading to all the food clumps and paths leading straight back to the nest. The ants form orderly convoys to pick up food and then order themselves again to return it to the nest. It's fast, efficient, and really simple. I wish I'd thought of it two days ago...