• Our submission
• Our first submitted ant
• Our second submitted ant

The language we used to write our ant is simple ( written in 3 hours ) but solves some important problems related with writing ants in a easy way.
We have macro expansion, relative jumps and jumps to label.

There are 3 steps involved in compiling an ant to it's final form:

• Step 1 - Macro expansion
  This was implemented in one of the easiest way possible. We wrote a program in C# that is generating the expanded code that will be processed further.
  That's it: The c# functions are parametrized macros that generate code. The c# functions add instructions in a list that will be written in a file for further processing.
  An example of the result can be found here.
• Step 2 - Relative jumps
  Verify relative jumps and replace with absolute line numbers. Create a list with absolute labels and remove them from the beggining of lines. This is done using regular expressions
• Step 3 - Replace absolute labels reference in code and our ant is good to go.

The main ideea of our algorithm is to gather as much food as possible, and of course, to do that in an efficient way. How do we achieve that? Mainly, our ant has two types of behaviours:

• looking for food ( assuming of course it has none )
• getting the food home as fast as possible ( after finding it )

We will now present details related to the implementation of the two behaviours.

An ant that is looking for food has to leave a trail behind it, specifing the way home. When marking that trail, it follows the next rules:

• We use the first three bits for specifying a direction.
• Each time we find an unmarked cell:
  • we mark it with the direction from which we entered it,
  • we go straight AHEAD, or with a given probability LEFTAHEAD or RIGHTAHEAD
• If a cell allready has a mark:
  • we don't change that mark,
  • we check for a bit of food ( crums ) that was set by ants returning home
  • if we find it we turn with our back towards the mark ( trying to recreate the path )
  • then we move AHEAD, or with a given probability LEFTAHEAD or RIGHTAHEAD

When an ant returns home it follows the path previously created by the ant looking for food. More than that, it sets a bit of food in every cell that it goes through, so that ants looking for food may find the current food source. So what the ant really does is:

• It checks the first three bits for finding the direction
• It turns towards that direction
• It moves AHEAD, or with a given probability ( a lot smaller compared to the previous case ) LEFTAHEAD or RIGHTAHEAD

In order words, we created a huge tree spreading on the entire map, with the first node being our home. When an ant wants to get home, it just has to follow the road. However, this wasn't enough, for two reasons:

• our ants were following false paths - paths that now lead to an exhausted source of food,
• the roads to the food source was full of ants, so the road home was becoming difficult in time.

Our solutions solved both problems: we told our food carriers to set the food bit with a given probability, and our seekers to delete that bit with another probability. The solution proved effective, and all we had to do was to find the right numbers for our probabilities ( implemented through flips ).