About The Seventh ICFP Programming Contest


Revision: 2 (changelog)

Team Name: TAPLAS-tiny
The Member: Yutaka Oiwa
Program Name: "ambiants building sweet trees"
Programming Languages Used: Objective Caml, Perl

Contents

The Task

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 source code

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).

Strategy

Basic Concept

Use of Markers

Six markers provided by the task specification are used in the following manner:

Movements of Ants

Each ants has five basic modes and switching according to surrounding conditions:
  1. Opening Mode
  2. Search mode
  3. Trunk building mode
  4. Branch building mode
  5. Carrier mode

Opening mode

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
  • T: build the trunk of a tree.
  • .: searches for foods.
  • +: firstly move fast to walls to avoid contention around anthill, then searches for the food.
  • F: build the fort marker.

Search mode

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.

Trunk building mode

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.

Branch building 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.

Carrier 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.

The fort, and countermeasures to foes

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
  • *: Put marker 4. Occupied by friend ants later.
  • 1 2 3: Put the marker of that number.

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.)


Tools

To solve the contest task, I programmed three tools.

Graphical game simulator

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.

[screen shot of the simulator]

Command line options:

usage: sim [options] map_file antfile1(red) antfile2(black)
-looseforgive some syntax/semantic errors
-rnumber of rounds (default: 100000)
-sseed of random numbers (default: 12345)
-xplay two games, exchanging player colors
-ppause each turn
-l filelog every states to the file specified
-ls filelog map image to the text file specified
-genable graphics
  -gr   show only red markers
  -gb   show only black markers
  -gn   show no markers

Runtime commands in graphics mode:

When running:
mouse buttonstop the game execution
mouse motiondisplays the state of the cell under cursor
When stopping:
mouse buttonresume the game / step a single turn
mouse motiondisplays the state of the cell under cursor
"s" keyenable single-step
"r" keydisable single-step
"q" keyexit the game

State machine assembler

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.

Cautious Ambiant creator

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.



Changes to this document