We did very poorly this year. Mostly, we ran out of time while writting and correcting our tools that allow us to write ants in a rather high level language that supports functions with arguments (numeric parameters and booleans).
Near the end, we submitted a very buggy ant that does very poorly. After the contest, some in our team started writing a new ant from scratch and in few hours managed to get it to beat the one we submitted 252 to 0!
Our team consists of Nelson Castillo, Alejandro Forero Cuervo and Sergio Garcia. Sergio worked from his apartment in France and Nelson and Alejandro worked at Alejandro's home in Colombia. This was our first time in the ICFP programming contests.
We used the Scheme programming language, in the Chicken Scheme implementation. We also used Subversion and IRC for coordinating our work.
It was very frustrating to run out of time with no working ant, but we still had a lot of fun during the contest! Many thanks to the organizers!
We're looking forward to the following contest. Hopefully we will be able to bring some smart people to work with us and we will manage our development resources better.
Sergio wrote some entry in his blog about our team (in Spanish).
Our Simulator
Nothing very interesting to say about our simulator. It is written in Chicken Scheme and runs 100.000 turns in about 30 seconds.
It can optionally generate PNM images depicting the state of the world every N turns. We convert those images to a GIF animation using Imagemagick (or sometimes just to PNGs using NetPBM). The animation at the beginning of this page was generated in that fashion.
We added two instructions: assert and trace. The first uses a format similar to the one of the sense instruction but stops the execution of the simulator if a condition doesn't hold. This is useful for debugging our ants. The second causes the simulator to print a message to its standard output. These states are different of the others in that they don't take any turns to execute. Actually, we implemented assert after the contest had finished.
The simulator was written by Alejandro and the generation of PNMs by Sergio. Nelson created some scripts to automatize its invocation.
Our Language
Alejandro designed and implemented a compiler from a relatively high language into the ants format specified. Sergio and Nelson helped catch some bugs in the implementation while creating ants.
The specification of an ant consists of a set of functions containing one called main. The code produced starts executing the instructions in the main function. The following are a few example functions:
(function (main-normal first)
(if first
(find-food-random 0 #t)
(find-food))
(sense Ahead Home #f (return (lookback) (dotimes 3 (move-keep-trying (main-normal first))) (main-normal first)))
(move-keep-trying (main-normal first))
(pickup (main-normal first))
(lookback)
(move-keep-trying #f)
(move-home-start first)
(assert Here Home #f)
(assert Here Marker 5)
(deliver-food)
(main-normal #f))
(function (random-2 a b)
(flip 2 (return a)) b)
(function (lookback)
(turn-times 3 Right))
(function (turn-times n dir)
(dotimes n (turn dir)))
(function (twice action)
(dotimes 2 action))
(function (dotimes n action)
(unless (zero? n)
action
(dotimes (- n 1) action)))
(function (sleep-turns turns)
(unless (zero? turns)
(flip 1 (noop))
(sleep-turns (- turns 1))))
(function (deliver-food)
(dotimes 4 (move-keep-trying #f))
(drop)
(sense Ahead Friend #f
(return
(lookback)
(dotimes 2 (move-keep-trying #f))))
(lookback)
(protect-out))
(function (protect-out)
(sense Ahead FriendWithFood #f
(progn
(lookback)
(move-keep-trying-safe)
(protect-in)))
(protect-out))
(function (protect-in)
(turn Right)
(move (protect-in)))
The first definition in the example corresponds to a function called main-normal, which receives a first parameter.
The definitions of functions contain either calls to primitive functions corresponding to the ant instructions (sense, move, ...), calls to user defined functions or one of the special forms described below.
For each ant instruction type that receives two states (all except drop, mark, unmark and turn) we defined one of them to be the exception. If the instruction is executed correctly, the ant continues executing the body of the function. Otherwise, it executes the code passed as an argument. See protect-out above: if the ant senses a friend with food ahead, it executes the (lookback), (move-keep-trying-safe), (protect-in) sequence. Otherwise it continues executing the body of protect-out (a recursive invocation).
There are a few special forms. (noop) just continues the execution. You can find an example above in sleep-turns, where the ant does (flip 1 (noop)). There are some more interesting uses for (noop): one is to pass it as a parameter to a user-defined function that receives code as one of its parameters.
(progn ...) allows the programmer to group a sequence of instructions into one. It is useful as shown in the protect-out example above, as it allows us to build an expresion containing a sequence of expresions.
Finally, (return) causes the current function to return. For convenience, (return code ...) is expanded into (progn code ... (return)) (having return return control to the function outside of the progn). (return) is very useful, as it allows us to specify that if a exception takes place, a certain code should be executed and, once it returns, the current function should return (rather than continue executing the code for the rest of the expresions in the function, after the one that produced the exception). This is very important for some recursive calls.
To produce an automata, the generator starts expanding the code of the no-arguments main function and building the instructions required. To compile a call to a primitive expression (sense, move, ...), an associated instruction is added to a list of states.
To evaluate a function call, the arguments are evaluated (with our own evaluator, not the standard Scheme evaluator), which allows us to do interesting operations on values (see dotimes, for instance) and check is made to find if a call to the same function with the same arguments has already been compiled and either it does not return control or it returns control to the same location of the current call. If the check is sucessful, no new code is generated. Otherwise, the arguments are inserted in the body of the function and its code gets compiled.
This means that our compiler has to detect if a given function call returns or not. It also detects tail-recursion. There are some other interesting details but we decided to omit them from this description.
Last update: 2007-07-02 (Rev 11936)