Another year and another missed competition. This time by a week.
See icfp contest for more info.
I decided to write a program to the contest spec under the time span given, as an exercise to see how far I would get.
The task is to write a control program to control an ant colony. The system is a simple state machine and the ants understand a set of simple instructions. The result of each instruction determines the next instruction to execute for that ant.
The goal is to get food and bring it back to the ant nest. There are two colonies and the task is to write a better control system than the other colony.
This programming challange does not stress the implementation language as much as others.
It is in the same vein as Battling Robot challanges. We have a virtual machine that controls the actions of the ants. We have to write the brain of the ants in a fixed language.
The only feature of the implementation will be how slowly it simulates the execution of the ant brain.
As I had missed the submission date, I did not follow the implementation plan exactly. The random number generator for the Flip instruction does generate the same numbers as the sample 100 given. We use a different numbering convention for the cells. In theory the ant moves the same direction as the spec but will use different cell numbers. During simulation the Move rest period can be set to zero to get faster simulation times.
As usual, my language of choice is TCL. This language is unsuited to this type of task so it adds conciderably to the challange.
As every ant executes the same control loop we must rely on random choices to seperate the ants into the groups we want.
I have decided that there should be two groups of ants
We are limited to 10000 instructions in the whole control program so each type must be implemented as simply as possible. This means that given the random nature of the choices we must accept that each ant may not operate in the most optimal way.
Day2 Another type of ant could be a next blocker, which sticks to the foes nest and surounds it. This prevents any food into the nest. Once sufficient ants have stuck to the outside they cant be killed.
While the main simulator executes the virtual instruction set for the ants, we will write the control code at a higher level.
This will allow the use of named states. It will also allow us to define the states in a nested structure.
The control system will convert the input format into the linear list of instructions as required by any constest submission.
I will reply on YCL's use of nested lists to create the source structure.
I plan to implement a system of disparate control states depending on what the ant is trying to do.
I envision that I need to subdivide the ant types into smaller sub types and give each ant a goal.
First Cut:
Thankfully the ants can drop scent markers as it moves, this will help us overcome the problem of not having stored data with each ant.
I propose to create the following Markers:
I have defined some basic rules that the ants should follow:
If we arrange some ants in the nest as to suround a cell with five ants, then we create an impenatrible fortress. Any intruder ant that enters the circle will be killed and converted into food.
Some ideas for how the ants operate.
The most complex of the two types, we basically need these modes.
We start off from the nest and drop a scent trail alternating between dot dash dotdash as we walk. When we come to obsticles we will either choose turn left or implement some more complicated algorithm.
If along the way we bump into a scent trail that is tagged with food we will enter FollowTrail mode.
In this mode we head away from the ant nest. If we bump into other ants of ours along the way we must give way and allow them to get back to the nest.
If the other ant is an enemy then we will sit on the trail and block their path.
Once we have found food at the end of the trail, we will enter ReturnHome mode and backtrack the trail to the nest and once we have entered the nest we switch to DropFood mode.
DropFood mode makes us head for the center of the nest and either add food to an existing pile or create a new pile and hope that there are spare defenders to swarm around it. There are likely to be a lot of other sub modes within each major mode that will be created as the code develops.
Time approx 6Hrs.
Time approx 4 Hrs
Time approx 10 /hrs.
Due to the time it takes for TCL to run the simulator , there was not much development on the ant brain. The end result was only implementing two out of the three ant types and not all of the ant logic for following a trail with food.
The poor speed meant that the longest run was only about 10 thousand steps. This was not enough to gauge the suitablility of the ant logic. Plus the time spent simulating reduced the time spent refining the logic.
The use of an assembler to allow the use of labels was a good move, but not having any higher order logic terms (such as conditionals, conjuctions, and disjunctions) resulted in the requirement to block copy code into multiple states.
It was also easy to make mistakes in jump labels, due to the use of relative brances, as a replacement for conditional statements.
Overall I rate this effort 7 out of 10 for coding. and 4 out of 10 for suitability for TCL to the problem.