![[screen shot of the simulator]](simulator.png)
Team Name: TAPLAS-tiny
The Member: Yutaka Oiwa
Program Name: "ambiants building sweet trees"
Programming Languages Used: Objective Caml, Perl
The task of this year's ICFP Programming Contest is to program an automaton in your ants' brain to collect foods as much as possible to your anthill, avoiding being killed by opponent's ants. Please refer the official homepage of the contest for the complete description.
The submitted ant automaton, along with source code for my own simulator and other helper tools are put in this archive. The simulator and documents are updated after the contest deadline to improve functionality and compatibility with other people's entries.
If you want only the automaton description, refer this directory.
The real archives I submitted to the contest organizers are this one (for the main contest) and this one (for the lightning division).
Six markers provided by the task specification are used in the following manner:
At the very first state of the game, every ants checks whether it is on one of six vertices of the anthill. If it is on a vertex, it enters into trunk building mode. otherwise, if it is the second leftmost ant in the middle line, it prepares the fort (only in the main solution). Otherwise it enters search mode.
| Figure 1. The role assigned at the beginning |
|---|
T + + + + T
+ . . . . . +
+ . . . . . . +
+ . . . . . . . +
+ . . . . . . . . +
T F . . . . . . . . T
+ . . . . . . . . +
+ . . . . . . . +
+ . . . . . . +
+ . . . . . +
T + + + + T
|
In this mode, the ants perform randomized walk around field and searching foods. If an ant finds food outside its own anthill, the ant picks it up and enters carrier mode.
In addition to this, there is a small chance to enter branch building mode when it hits the trunk of a smell tree.
At the first stage, the ants on the corners of anthill draws trunks of six smell trees.
To do this, the ant walks as straight as possible from the anthill corner until it is blocked. If it hits rocks (or other obstacles), only 60-deg diversion is allowed and it recovers to the original direction as soon as possible.
Along the pathway, it puts marker 0 on the every cell, and markers 1, 2, 3 are put alternately on the path, in the order "1-2-3 1-2-3...".
If it is completely blocked, the ant turns into search mode.
Unlike trunk building, the branch building process is performed by "normal" ants occasionally. Branches are constrained in the following way:
If any normal ants not carrying any foods hits the trunk, it sometimes begins to draw branches from that point. It checks the direction of tree, makes sure it is enough space, then begin straight line from the trunk. The ant puts Marker 4 in addition to Marker 0 on every cell of the path, to prevent nested branches.
The example of the "smell tree" is on the following pictures: red tree and black tree in the sample2.world.
When obstructed, the ant reverts to usual search mode.
The obvious goal of mode is to bring foods to their anthill. Until the ant hits either its home or smell tree, it walks randomly. Additionally, it puts food markers (Marker 5) from the food in the straight line (i.e. until it makes any turns), only if there is more foods on the cell which the ant pick up the carrying food from.
If the ant hits one of smell trees (i.e. Marker 0), it traverses the tree to the root. This greatly reduce the turns required to carry foods to home. Markers 1, 2, 3 tells the correct direction to follow: it must be in order 3-2-1, 3-2-1.
If the ant enters the home, it tries to put foods in the center of the anthill. This makes foes with randomized algorithm (like this ambiant) to find the foods in the anthill slightly difficult. After dropping the food, the ant reverts to search mode.
To prevent foes to steal our foods, the fort is prepared by a special ant determined in the opening mode. The special ant walks around its own anthill and puts pre-programmed patterns of markers inside the anthill. The pattern is in Figure 2 below.
| Figure 2. The Programmed pattern for the fort. |
|---|
3 2 1 1 1 1
3 2 1 3 3 3 3
3 2 1 3 2 2 2 3
3 2 1 3 2 1 1 2 3
1 3 2 1 * * 3 1 2 3
2 1 3 2 * 1 2 3 1 2 3
1 3 2 1 * * 3 1 2 3
3 2 1 3 2 1 1 2 3
3 2 1 3 2 2 2 3
3 2 1 3 3 3 3
3 2 1 1 1 1
|
The cells with the mark * are later occupied by some passing friend ants. This prevent foes from stealing foods from our anthill. Markers in other cells pulls food-carrying ants into the center of the anthill. Check that all descending sequence of numbers (3-2-1 3-2-1 ...) leads to the center cell.
To prevent our ants to die from foe's attack, Our ants decline to walk between two foes when following some markers (i.e. returning to the home following the smell tree, or following the food marker to find more foods).
In the alternative solution (solution-2.ant),
fort creation and suicide avoidance is not implemented.
This makes whole moves few percents faster, and
makes the ant group slightly stronger when
matched with naive, weak solutions.
(Note: when my two solutions play a fight,
the solution 2 leads for about 30000 ~ 50000 turn, but then
the solution 1 reverses the game and wins most of the time.)
To solve the contest task, I programmed three tools.
The simulator is implemented in Objective Caml. The simulator has following features:
It is in the tools/sim directory. OCaml 3.06 or later is required to build.
| usage: sim [options] map_file antfile1(red) antfile2(black) | |
| -loose | forgive some syntax/semantic errors |
|---|---|
| -r | number of rounds (default: 100000) |
| -s | seed of random numbers (default: 12345) |
| -x | play two games, exchanging player colors |
| -p | pause each turn |
| -l file | log every states to the file specified |
| -ls file | log map image to the text file specified |
| -g | enable graphics |
| -gr | show only red markers |
| -gb | show only black markers |
| -gn | show no markers |
| When running: | |
|---|---|
| mouse button | stop the game execution |
| mouse motion | displays the state of the cell under cursor |
| When stopping: | |
| mouse button | resume the game / step a single turn |
| mouse motion | displays the state of the cell under cursor |
| "s" key | enable single-step |
| "r" key | disable single-step |
| "q" key | exit the game |
The assembler is implemented in Perl. It resolves the labeled branches in the source code, and removes any whole-line comment. Both local numeric labels (referred by number + back/forward, duplications allowed), and global symbolic labels (referred by its name, duplication disallowed) are supported.
It is in the tools/asm directory. It follows well-known Perl-filter practice: input from stdin, output to stdout.
Only the solution 1 uses this filter.
A tiny ad-hoc filter which inserts two check instructions before Move statements with a special annotation. A ten-liner in Perl language.
It is in the tools/ant directory, along with the assembly-language sources of the two solutions. Use this filter before state machine assembler.