Programming Assignment

Afp0607
<img src="%ATTACHURLPATH%/ants.gif" alt="ants.gif" />

---++ Teams

   * *1:* Alesya, Peter, Matthijs, Niek
   * *2:* Eelco, Niels, Reinier
   * *3:* Robert, Brian, Erik, Bas
   * *4:* Achiel, Jeroen Goudsmit, Remi, Mark
   * *5:* Maaike, Jeroen Leeuwestein, Martijn
   * *6:* Marcin, Xavier, Guangyu
   * *7:* Jeiel, Joost, Tim Breedveld, Tim Smienk

_See the [[Discussion Forum]] for a patch on the simulator to display all markers._

---++ Results

See the [[Course Schedule]] for the slides.

   * [[%ATTACHURL%/score.txt][score.txt]]: Scores (overall and for each team individually)

   * [[%ATTACHURL%/results.log][results.log]]: Log file

   * [[%ATTACHURL%/ants.zip][ants.zip]]: All 17 ant files (in case you want to rerun the tournament)

---++ Introduction

Every year, the ICFP (International Conference on Functional Programming) organizes a programming contest.
Teams from all over the world are challenged to submit a solution within 72 hours. Although the contest is
hosted by the ICFP, which has a desire to promote functional languages, submissions implemented in non-functional
programming languages are accepted as well.
In 2004, the programming contest was organized by members of the PLClub in the Computer and Information Science Department 
at the University of Pennsylvania.
Andres Loeh from Utrecht University was a member of the winning team in the main division: they implemented all their tools in Haskell
(congratulations Andres!).

In this years programming assignment for AFP, student teams have to tackle the problem as described by the 
[[http://www.cis.upenn.edu/~plclub/contest/][2004 programming contest]].
A detailed description of the task can be found [[%ATTACHURL%/ants.pdf][here]].
In order to complete this assignment, several topics that are covered in the course have to be dealt with.

---+++ Diner with Ambiants
_(from the Task Description)_

The object of this year's programming contest is to design an ant colony that will bring the most food particles back to its anthill, while fending off ants of another species. To win the contest, you must submit the neural wiring for the ants in your colony - a text file containing code for a simple, finite state machine that is run by all of your ants. In principle, your entry can be written by hand, but for complex behaviors you will probably find it useful to write tools that generate ant code in some way. You may use any programming language you like for this purpose.

Your ants will compete in a tournament with all the ants submitted by other teams. In each match, two species of ants are placed in a random world containing two anthills, some food sources, and several obstacles. They must explore the world, find food and bring it back to their anthill. Ants can communicate or leave trails by means of chemical markers. Each species of ants can sense (with limited capabilities), but not modify, the markers of the other species. Ants can also attack the ants of the other species by surrounding them. Ants that die as a result of an attack become food. The match is won by the species with the most food in its anthill at the end of 100,000 rounds. The overall winner is the ant that wins the most matches.

---+++ Restrictions and rules for the AFP student teams

The focus of this assignment is different from the main goal of the contest (namely submitting clever _ant code_). There are some additional
restrictions, and modifications to the rules.

   * A team consists of 3-4 students (depending on the number of students).
   * The time frame in which the solutions have to be submitted is ten weeks (instead of 72 hours).
   * To minimize the start-up time, you are given a working simulator (to run a game) and visualizer written in
     wxHaskell. 
   * All parts must be implemented in Haskell.
   * Programs are also judged on elegance, style, and clarity. Submitting a program that only does the job is insufficient.
   * Apply techniques from the lectures whenever it seems appropriate. 

The last slot of the course is reserved to present your solution to the other teams. Submissions of the student teams will 
compete against each other in a small tournament. The winning student team may challenge the winning submission of the 
ICFP contest (if we have enough time).

Enjoy!
    
---++ The Task

Create your own ant instruction file: use your creativity to achieve this.
Obviously, one aspect is to obtain the best ant code.
The quality of an ant instruction file can be measured easily by the number of matches it wins, for instance
against the other teams. However, this should not be your main challenge.

Needless to say, writing an instruction file by hand is both cumbersome and error-prone, and 
submitting a hand-written instruction file is therefore not permitted.
A much more interesting approach is to see how ant code can be generated from
a _high-level specification language_. Such a high-level specification language should allow you 
to implement all kinds of strategies relatively easy.
Hence, the main challenge for you is to design your own _domain specific embedded language_ for generating 
ant code.

---+++ Start version

The following zip file contains a simulator and visualizer to see your ants in action: 
[[%ATTACHURL%/Ants-AFP06.zip][Ants-AFP06.zip]]. To build the executable, you must have installed

   * GHC version 6.4.1, and
   * [[http://wxhaskell.sourceforge.net/][wxHaskell]] version 0.9.4

on your computer, although it will probably also work with slightly older versions (with some modifications).
Make sure that the version of wxHaskell is compatible with the version of GHC. Use the makefile for building
the executable (or copy-paste the commands from the makefile). 
_See the remarks on the [[Discussion Forum]] if you want to compile with ghc 6.6._

To start the visualizer, type the following command:
<verbatim>
bin/Ants.exe -w worlds/sample1.world -r ants/sample.ant -b ants/sample.ant
</verbatim>
Windows users should change all =/= separators into =\=. 
Use the =--help= flag to see all the available arguments (including =--simulate= which simulates a match without
a GUI).

Adapt the code to your own needs. Bug fixes and suggestions are welcome.

_MacOS users should call the =macosx-app= application on the produced executable (see comment in makefile)._

---+++ Tips and Tricks

Introduce a data type for _high-level_ ant instructions. As a starting point you may take some of the low-level ant instructions
given in the task description. Next, invent and add your own ant instructions. Keep in mind that you have to be able to translate a set 
of _high-level_ instructions into a set of original instructions, for instance by providing a function 
<verbatim>
compile :: [HighLevelInstruction] -> [LowLevelInstruction]
</verbatim>
The idea of translating a high-level language into a language on a lower level is the essence of a compiler!
You may want to apply other well-known techniques from compiler technology, such as code _analysis_ or code _optimization_.
Furthermore, you may want to include some imperative language constructs to your ant language, such as =gotos= and =labels=.

In addition to the high-level instruction language, you may also want to design a library of combinators to construct often
occurring patterns in your language. For instance, you could offer a function =goHome=, which instructs an ant to seek for 
his own ant hill. (This function serves as an example only: it is not necessary to include it in your library.) 
Ofcourse, =goHome= is nothing but an abbreviation of a series of instructions.

As a language designer, it is your task to find the right balance between the level of abstraction (how easy is it to
implement a certain strategy) and expressiveness (which ideas can be formulated).
Try to keep the following aspects separated in your code at all time (i.e., provide them in different modules):
   * The high-level instruction language.
   * The low-level instruction language. You may reuse parts of the start version.
   * Compilation techniques, including a translation from high-level to low-level.
   * A combinator library on top of the high-level instruction language.
   * Examples of ant programs written in your high-level instruction language (using your combinators).

---+++ Submission Instructions

The submission is split into two phases. Every team must submit one generated ant instruction file on April 10 (Tuesday, 17:00).
*This is a strict deadline*. On Wednesday the 11th, every team has to give a short explanation _(5 minutes)_ on their language, and discuss the design
choices in particular (while playing the matches between the AFP teams).

Note that teams can submit ant instruction files during the whole course: only the last submission will be used for the tournament.
Submitting ant instruction files early on prevents you from submitting a syntactically incorrect file (it gives me the opportunity to run them beforehand).

Friday, April 13th, will be the last day on which you can submit your final version. This should include:

   * The ant code generator.
   * A detailed description of your high-level ant instruction language.
   * The slides of your presentation.
   * At least one example program written in your ant language.
   * A description of how to compile your examples. It is strongly recommended to include the generated files for all your examples.
Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
zip	Ants-AFP06.zip	manage	26.2 K	14 Feb 2006 - 08:30	BastiaanHeeren
pdf	ants.pdf	manage	154.8 K	07 Feb 2007 - 14:44	BastiaanHeeren	Ants task description
zip	ants.zip	manage	244.0 K	11 Apr 2007 - 11:42	BastiaanHeeren	All 17 ant files
log	results.log	manage	110.3 K	11 Apr 2007 - 11:41	BastiaanHeeren	Log file
txt	score.txt	manage	30.4 K	11 Apr 2007 - 11:40	BastiaanHeeren	Scores (per team)