My Participation in the
ICFP Programming Contest 2004

I participated in the 7th edition of the ICFP programming contest, in June 2004.

The name of my one-member team was ANTisocial. You can get my final submission. However, It has a last minute bug in the "wait" function, that I fixed in this version.

The ant generator

I wrote OCaml functions that let me define what I called subtasks. I defined several higher order functions that manipulate subtasks: or, and, not, xor, while, until, if, ifnot, ifelse, return, fail, choose, sequence, switch (lib.ml). Then the job was to use these instructions to make my colony work correctly. The source code for my ant is in the file work.ml. It it 2 times shorter than the output, has blank lines, and about 20 lines of dead code (function incr_mark).

Strategy

The strategy I chose is based on:

• tracing 6 straight oriented lines that start from the corners of the anthill, using 3 markers,
• protecting the corners with 5 guards, so that no enemy can take food from these places that have a high probability of containing food since
• when an ant has found some food, it will follow the line that brings it directly to (a corner of) its anthill as soon as possible.

This is better illustrated by the position of the markers, as shown in this map. Note that an additional marker 4 is located on each corner but is not visible since there is already a marker 0.

The final (fixed) ant is here.

Various outputs

Profiling

The number of accesses to each state is output and sorted after each simulation. I think that a healthy brain is one that has a balanced number of accesses to each node. Note that the ants use a collective brain. 100,000 simulation steps were performed with initially 91 red ants. The most accessed node corresponds to the 30 food guards, that simply do nothing once they decided to be guards (the "loop" state).

Graphs

I displayed the transitions between the states of my ants with the dot tool from the Graphviz package. The graph for my ant is available as a PNG image, or better as a PostScript file (or its compact version). The gv tool is convenient for watching this kind of files.

Ascii Ant

                                        _,  _gM#MMA                    
           _;q                         (P]gMMMMMMMM                    
        _m#  q                        gKgMMMMMHMMMW                    
     _mF     q               _       _W#MMMMMMMMMM                     
  _pP'       (k_g_g_        #^M_    qM M#MMMMMMMM                      
#P           `MMMMMHM____ggF  3M,   #F MMMMMMMP                        
           __MHMMTMMMMMMHMMM____A__gBMP"*##W'  __gM##9&                
          gWWHMMMMMMM"__MMMM*MMMMMHMNF     (_g#*       M,              
         / gMM##*8M__F  3FWMA 7WME^HMm___MPHE           M,             
          ""       VMAm# _g#'   7M<   "     V__          V,            
                  gK4   _P       "#m_         7MmA,,      %_           
                _F_#   qF           NM                     \,          
                M_M   _P             #                      %_         
             __# #^   ML            #'                       ML        
                M'   F7            qF                         M        
               M"    1             #                           A       
              `"   _#'            gL                            R_     
                                  #                              ^NMMmm
                                 qL                                    
                                 #                                     
                                 L                                     
                                 R