Changes of ICFP 2004 from #31 to #32

Changed lines at line 33
According to the task the ants are controlled by a final state machine described by an assembler like low level code. Alls ants work independend. The ants have no memory, their state is defined by the current line of code that is executed. Of couse it is possible to simulate something like a memory by splitting the program into special address ranges. And therefor it is necessary to have an high level language with macros, the possibility to multiply blocks and more, see Phec language. Ants can leave marks on fields they run over, there are six markers that can be turned on or off. That means we can save 6 bits of information on every field.
The basic behaviours of an ant are:
1. explore and search for food
2. bring food back home
It is necessary that an ant easily finds the way to home. Our approach is an initial spreading of path information. Initially all ants start at the home base. The idea is that some ants are choosen to run nearly straigth away from the home base and on every field thay mark the direction to go back to the home base. First we thought about writing a number 0..5 in every field and code to give the direction within a hexagon. The disadvantage of this approache is that we need 3 bits (we have only 6) and every ant would have to remember its direction through its whole live. Normally ant's don't know the direction they are looking, it would have been necessary to split the whole code into 6 address ranges and keep tracking of the current direction whatever the ant is doing.
We choose an different approach hat overcomes this problems. The idea is to code an gradient field descending with more distance from the home base. For this field only 2 bits are needed. Like described at the start of the match some ants will start running away from the home base and write gradient information 3,2,1,3,2,1,3,... and so on. The value 0 is reserved for an empty field without way mark. If an ant has found food and searches for the home base it runs straigt until it finds a field with gradient information. Then it starts turning arround and searching for neigboring field with (gradient + 1), the field is ascending in direction towards the home base.
The same idea is reused for faster finding the food hills. If an ants finds food, it picks it up and then moves back to the home base. During walking back it marks the way to the food with the gradient information. We wanted to have someting like in nature: unused food tracks should get weaker over time. Therefor we use the last free 2 bits to give the food track an strength information. Ants that carry food will write the gradient with strength 3.
Normal ants are randomly exploring the landscape and hope to find food. If they find an food track they will follow it and decrement the strength of the track in every step. If the food at a certain place is empty the tracks that lead the this place will be removed over time.
Yes that is our approach: 2 bits for home base gradient, 2 bits for food gradient and 2 bits for food path strength. The approch is tested and works. For the given sample maps the average time to collect all food and bring it to the home base is 50,000 steps.
Unfortunatelly we didn't get the algorithm to work until the contest submission stop. We would have needed 4 hours more :( We submitted two unfinished versions. One that can't follow food tracks and the other follows that but with a bug that lieds to ant dead lock. Nevertheless we finished the algorithm, now it works fine and we are looking for testing it against the winner ant :)
According to the task the ants are controlled by a final state machine described by an assembler like low level code. Alls ants work independend. The ants have no memory, their state is defined by the current line of code that is executed. Of couse it is possible to simulate something like a memory by splitting the program into special address ranges. Therefor it is necessary to have a high level language with macros, block multiplication  and more, see [Phec|ICFP 2004/Phec] language. Ants can leave marks on fields they run over, there are six markers that can be turned on or off. That means we can save 6 bits of information on every field.
The basic behaviours of an ant are: 
1. explore and search for food
1. bring food back home
It is necessary that an ant easily finds the way to the hill. Our approach is an initial spreading of path information. Initially all ants start at the home base. The idea is that some ants are choosen to run nearly straigth away from the home base and on every field thay mark the direction to go back to the home base. First we thought about writing a number 0..5 in every field to the direction to the ant hill within a hexagon. The disadvantage of this approach is that we need 3 bits (we have only 6) and every ant would have to remember its direction through its whole live. Normally ant's don't know the direction they are looking, it would have been necessary to split the whole code into 6 address ranges and keep tracking of the current direction whatever the ant is doing.
We choose an different approach that overcomes this problems. The idea is to code an gradient field. It is descending the more distance the ant has from the home base. For this field only 2 bits are needed. Like described at the start of the match some ants will start running away from the home base and write gradient information 3,2,1,3,2,1,3,? and so on. The value 0 is reserved for an empty field without way mark. If an ant has found food and searches for the home base it runs straigt until it finds a field with gradient information. Then it starts turning around and searchs for a neigbour field with (gradient + 1), the field is ascending in direction towards the home base.
The same idea is reused for faster finding the food hills. If an ants finds food, it picks it up and then moves back to the home base. During walking back it marks the way to the food with the gradient information. We wanted to have someting like in nature: unused food tracks should get weaker over time. Therefor we use the last free 2 bits to give the food track a strength information. Ants that carry food will write the gradient with strength 3.
Normal ants are randomly exploring the landscape and hope to find food. If they find an food track they will follow it and decrement the strength of the track by one. If the food at a certain place is empty the tracks that lead the this place will be removed over time.
Yes that is our approach: 2 bits for home base gradient, 2 bits for food gradient and 2 bits for food path strength. The approch is tested and works. For the given sample maps the average time to collect all food and bring it to the home base is 50,000 steps.
Unfortunatelly we didn't get the algorithm to work until the contest submission stop. We would have needed 4 hours more :( We submitted two unfinished versions. One that can't follow food tracks and the other follows them but with a bug that leads to a dead lock. Nevertheless we finished the algorithm, now it works fine and we are looking for testing it against the winner ant :)