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.
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.
There are 1000 time intervals before sunset. At every time interval, each ant faces this decision tree.
Each time interval has five distinct phases.
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.
As directed, each ant lays down a marking scent in the square in which they begin the turn.
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.
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.
All dead ants vanish and leave behind a death scent of 100. Death scent is distinct by team.
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.
The outputs are all scalars.
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'.
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.
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.
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.
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)
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.
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.
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:
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.
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: