Winner David (Rogue Ant 4)

Darkness 2008-11-05 12:00:00 UTC
 
Twilight 2008-11-06 12:00:00 UTC
 
Daylight 2008-11-07 12:00:00 UTC
 
Finish 2008-11-12 12:00:00 UTC

Army Ants - Rules

Arrow_down  Download Sample Code

Rules

The Problem: Ants Again

Three years ago, we ran a contest based on the behavior of ants in an ant colony. We're going to return to that theme, but with a difference.

As before, your ants will all be running a single program that you write for them. As before, they will have no memory. They will only be able to detect and respond to things in their immediate neighborhood. But this time your ant colony will not be alone. It will be sharing the sandbox with another ant colony. We sometimes refer to this other colony as "the opponents."

The ants in the other colony will be running a program of their own. They may be hostile to your ants. They may choose to cooperate with your ants. Your ants have to decide the optimal way to respond to these new neighbors: ignore, cooperate, or fight.

The initial code for the other ant colony will be written by those of us here on the contest team. But after we begin the daylight portion of the contest, the other ant colony will be selected from contestant entries (that is, it will be written by one of you). Every day during the contest daylight period, we'll swap in a new "King of the Hill" to become the opponent colony. That colony will be cloned from the leader at the time of the swap. Note that if your code gets selected to be King of the Hill for a day, it won't make any difference to your standings in the ongoing contest.

How It Works: A Review

Imagine a sandbox in which there are red ants, black ants, sugar cubes, anthills, and rocks. Ants like sugar: collectively they want to bring as many sugar cubes as possible back to their anthills before sunset.

For this contest, you will write the control program used by each ant. Ants, being so small, have some limitations. Each ant can carry no more than one sugar cube at a time. Further, each ant can only see her local vicinity. Your program, which is run sequentially for each ant, knows only what that ant knows. Thus you must bring about the best possible global outcome based only on local information. The ants don't have any memory as such, but they can leave behind a chemical trail to guide themselves and others across the sandbox landscape.

Your score is determined by how much progress you make moving food towards and into the anthills. Ideally your ants will move all the sugar cubes into anthills. In practice this may not be possible; do the best you can. You receive credit even when you move a single sugar cube one step closer to an anthill.

Some considerations:

  • There may be any number of ants, anthills, sugar cubes, and rocks.
  • At each time interval, every ant runs the ant controller program.
  • An ant can carry no more than one sugar cube at a time.
  • A single square can contain multiple ants (from either team) and multiple sugar cubes
  • For each turn, an ant can move a maximum of one square horizontally and one square vertically (i.e. diagonal motion is possible).
  • There is a limited number of time intervals (1000) before sunset.
  • An ant can either move or attack on any given turn, but it can't do both.
  • Every ant has the opportunity to mark the square they are leaving with a number (0-100) that corresponds to a pheromone-like "marking scent".
  • A dying ant disappears and leaves a "death scent" of 100 in its place.
  • The marking scent and death scent deposited by ants on a single square are both cumulative without bound. If five ants put a scent of 10 on a single square in the same time interval, that square will have a scent of 50 by the end of the turn.
  • Marking scent and death scent both dissipate over time in exactly the same way. All scent is decremented by one each time interval.

Move Phases

There are 1000 time intervals before sunset. At every time interval, each ant faces this decision tree.

Each time interval has five distinct phases.

1. Plan
Your ants get to look around and make decisions about what they want to do: move, carry, attack, or sit. Orders are given for all ants in this phase. Once the orders have been finalized, move resolution can begin.

2. Mark
As directed, each ant lays down a marking scent in the square in which they begin the turn.

3. Move
Movement is resolved square-by-square. At each square, each team takes turns moving. One A Team ant moves, then one B Team ant moves, then the next A Team ant moves, and so on until all ants have moved. If an ant has been order to "carry" AND there is sugar in the square in which the ant begins the turn, that sugar is carried along with the ant to the next square. Note that the A Team has a slight advantage, since the first A Team ant gets to move the first sugar cube before any B Team ant can get to it. You have no way of knowing whether you have this advantage in any given game.

4. Attack
For each attacking ant, one enemy ant is removed from that square. Mutual destruction results when two opposing ants both attack. There is no first mover in attack, so there is no inherent advantage for either Team A or Team B.

5. Death
All dead ants vanish and leave behind a death scent of 100. Death scent is distinct by team.

Example

Here is a sample map that an ant might face.

The full 8x8 map is shown, but the black ant only "sees" the 5x5 subset of the map indicated by the blue box. In this case, food is available on this map in several locations, but the ant has no knowledge of the food in the upper right corner.

The ant controller code is called with 8 input arguments and must return 4 output arguments.

[dRow, dCol, action, mark] = ant( ...
    mainMap, ...
    foodMap, ...
    myAntMap, ...
    opAntMap, ...
    myScentMap, ...
    opScentMap, ...
    myDeathMap, ...
    opDeathMap)

The "op" prefix indicates "opponent". In the text below we refer to "your ants" and "opposing ants" since in any given game you don't know if your ants will be red, black, King of the Hill, or any other designation. The inputs are all 5x5 matrices of integers with the ant at the (3,3) center location.

Main map
Location of your anthills (shown as 1), opposing team ant anthills (shown as -1) and impassable regions (shown as NaN). Open space is given by 0.
Food map
Location of any sugar cubes. The number represents how many sugar cubes are at that location.
Ant maps
Location of any ants. By definition you will always have at least one at location (3,3).
Scent maps
Where and how much chemical scent has been deposited. The number in each cell is decremented by one every time interval (all ants get the chance to move before the completion of one time interval).
Death scent maps
Where and how much death scent has been deposited. The number in each cell is decremented by one every time interval.

The outputs are all scalars.

dRow
Delta in rows (-1 is up or north, 0 no move, 1 is down or south)
dCol
Delta in columns (-1 is left or west, 0 no move, 1 is right or east)
action: attack or carry
-1 is attack, 0 is no action, 1 means the ant will attempt to carry a cube of sugar with it. Note that an ant can only attack if it isn't moving. If your input indicates both a move and an attack, the move is respected and the attack is not.
mark
Scent left by the ant, any integer between 0 and 100

If we step through this example, we get the following problem inputs (for the sake of readability, zeros in the following matrices are shown as dots).

      main = [ .  .  .  .  . ]         food = [ .  .  .  .  . ]
             [ .  .  .  .  1 ]                [ 5  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [ .  .  . NaN . ]                [ .  .  .  .  . ]
             [-1  .  . NaN . ]                [ .  .  .  .  1 ]
 
  myAntMap = [ .  .  .  .  . ]     opAntMap = [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [ .  .  1  .  . ]                [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ 2  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  1  .  .  . ]

myScentMap = [ .  .  .  .  . ]   opScentMap = [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [10  .  .  .  . ]                [57  .  .  .  . ]
             [15 27  .  .  . ]                [80 12  .  .  . ]

myDeathMap = [ .  .  .  .  . ]   opDeathMap = [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [99  .  .  .  . ]                [ .  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]

The variable "myAntMap" reveals exactly one ant on my team in the middle of the map. Let's say that's me. Based on the information available to me, I can set the following scene: I have no other team mates in sight. There is abundant sugar (5 units) to the west of my location, but there are at least three opposing ants nearby. Furthermore, I can see that (at least) one of my team's ants died to the southwest, so I can expect trouble if I head in that direction. The prudent thing to do is move toward the single sugar situated in the southeast.

I want to march due east (one column to the right). Accordingly I issue the following commands.

dRow = 0
dColumn = 1
mark = 10
action = 0

I am leaving a scent trail marker of ten to show where I've been. Since I'm not in a square with any sugar cubes, there is no need to set the action to 'carry'.

Inconsistent outputs

  • Setting the action to 'carry' when there is no food present does not cause an error. The move is respected and the action causes no side effect.
  • If you ask one ant to move and attack in the same turn, the move is respected and the attack is ignored.
  • If dRow and dCol are set such that the ant will move into an obstacle (a rock or the edge of the board), there is no error, but no move occurs.

Passing information

You're not allowed to explicitly pass information from one ant to the next through the use of programming techniques, like persistent variables, global variables, or similar.

Scoring

How well your algorithm does (which we call the "result") is determined by how thoroughly you move all the sugar cubes to the anthills. There is no explicit reward for killing opposing ants. You are not competing with them. They simply represent a hazard as you seek to collect sugar. If they don't attack you, and their ant hill is near yours, they may actually improve your score. At the end of the total available simulated time, your result will be determined by calculating the aggregate improvement in the total Euclidean distance of all sugar cubes to the nearest holes.

      main = [ .  .  .  .  . ]         food = [ .  .  .  .  . ]
             [ .  .  .  .  1 ]                [ 5  .  .  .  . ]
             [ .  .  .  .  . ]                [ .  .  .  .  . ]
             [ .  .  . NaN . ]                [ .  .  .  .  . ]
             [-1  .  . NaN . ]                [ .  .  .  .  1 ]

In the example above, there are five sugar cubes at location (r=3,c=1), one sugar cube at location (r=5,c=5), and an anthill at location (r=2,c=5). The result is currently

5 * sqrt((5-1)^2 + (2-2)^2) + sqrt((5-5)^2 + (2-5)^2) = 23

If an ant picks up the sugar cube in the southeast and moves it one row closer to the anthill (north), the overall result would be improved (lowered) to

5 * sqrt((5-1)^2 + (2-2)^2) + sqrt((5-5)^2 + (2-4)^2) = 22

The best possible result is zero.

Overall Score

The overall score for your entry is a combination of several factors. The first two in this list are the most important. The other two have a milder effect.
  1. Your average result across all the problems
  2. How fast your code runs
  3. The cyclomatic complexity of your code (more information below)
  4. The node count of your code (more information below)
Since each of these is to be minimized, the lowest overall score at the end of the contest wins.

Cyclomatic Complexity

Cyclomatic complexity, also known as McCabe complexity, is a measure of the number of independent paths through a program's source code. Typically, as this number gets higher, it becomes more difficult to understand what's happening in a program. This makes it harder to test, modify, and refactor.

Since a file can contain multiple functions, the complexity for any given file is defined as the MAXIMUM complexity of any functions contained in it. A good practice is to keep the complexity for each function below 10, so for this contest your overall score will increase according to the complexity in excess of 10. So there is no complexity penalty for submissions in which all functions have a complexity of 10 or less.

You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB using the "cyc" switch for mlint. Try this, for example:

>> mlint -cyc magic.m

We have also included a getComplexity.m function with the contest distribution to make it easier to find the complexity for your entry.

Node Count

This is a rough measure of how long your code is, but it will not penalize you for comments and variable name length.

t = mtree('your code');
length(t.nodesize)

Time and Size Limits

Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).

The code is limited in size by the database architecture. The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. Submissions longer than this limit will fail.

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.

Syntax

The main routine is solver.m. The syntax is described above. Keep in mind that these functions must have the right signature. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m.
 >> runcontest

Collaboration and Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the thread that we've started from our newsreader.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against the latest version of MATLAB.

The following are prohibited:
  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, function handles, etc.
  • Shell escape such as !, dos, unix
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, pause
  • error, clear, persistent

Hacking

Entries that compromise the contest machinery are no longer allowed. We've all learned some interesting MATLAB tricks in the past by contestants figuring out how to pass information from one entry to the next, or finding clever ways to execute disallowed functions, but it's too hard for the few of us running the contest to keep ahead of the group intelligence. In short, out of consideration for everyone participating in the contest, we ask that you not abuse the system.

Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. In the small scale, this has been an element of many past contests, but in the Blockbuster Contest, Alan Chalker turned this into a science. Tuning the entry to the contest test suite via tweak bombing or other techniques is still allowed, but we ask that you not overwhelm the queue.

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

  • Darkness - You can't see the code or scores for any of the entries.
  • Twilight - You can see scores but no code.
  • Daylight - You can see scores and code for all entries.
  • Finish - Contest end time.