Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
1151 lines (1104 sloc) 70 KB
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html><head><title></title>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<meta name="GENERATOR" content="hevea 1.06">
</head>
<body>
<!--HEVEA command line is: hevea main.tex -->
<!--HTMLHEAD-->
<!--ENDHTML-->
<!--PREFIX <ARG ></ARG>-->
<!--CUT DEF section 1 -->
<h1 align="center"> <b><font size="7">Dinner with Ambiants<br>
<font size="5">ICFP Programming Contest<br>
2004 Task Description</font></font></b></h1>
<h3 align="center">
<font size="4"><b>Brought to you by the University of Pennsylvania PL Club</b></font><sup><a name="text1" href="#note1"><font size="2">1</font></a></sup><font size="4"><b>
</b></font></h3>
<h3 align="center">
<b><font size="4">Version </font></b><a href="#currentversion"><b><font size="4">4</font></b></a><b><font size="4"><br>
June 5, 2004, 21:00 EDT</font></b></h3>
<!--TOC section Overview-->
<h2><a name="htoc1">1</a>&nbsp;&nbsp;Overview</h2><!--SEC END -->
The object of this year's programming contest is to design an ant
colony that will bring the most food particles back to its anthill,
while fending off ants of another species. To win the contest, you
must submit the neural wiring for the ants in your colony---a text
file containing code for a simple, finite state machine that is run by
all of your ants. In principle, your entry can be written by hand, but
for complex behaviors you will probably find it useful to write tools
that <em>generate</em> ant code in some way. You may use any programming
language you like for this purpose.<br>
<br>
Your ants will compete in a tournament with all the ants submitted by
other teams. In each match, two species of ants are placed in a
random world containing two anthills, some food sources, and several
obstacles. They must explore the world, find food and bring it back
to their anthill. Ants can communicate or leave trails by means of
chemical markers. Each species of ants can sense (with limited
capabilities), but not modify, the markers of the other species. Ants
can also attack the ants of the other species by surrounding them.
Ants that die as a result of an attack become food. The match is won
by the species with the most food in its anthill at the end of
100,000 rounds. The overall winner is the ant that wins the
most matches.<br>
<br>
Along with your finite state machine, your contest submission must
include the source code for any tools you write to generate or test
ants programs. We will not attempt to run your tools, but your code
may influence our choice of the judges' prize. We also encourage you
to publish a web page describing your entry after the contest results
have been announced. You can submit up to four separate entries---two
in the lightning division and two in the regular division.<br>
<br>
<!--TOC subsection A Brief Look at the State Machine-->
<h3>A Brief Look at the State Machine</h3><!--SEC END -->
As outlined above, the behavior of your ants is defined by a simple,
finite state machine. Informally, the instructions of this state
machine can be described as follows:
<blockquote>
<table cellpadding="0" cellspacing="2">
<tbody><tr><td nowrap="nowrap" align="left"><tt>Sense sensedir st1 st2 cond</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Go to state <tt>st1</tt> if <tt>cond</tt> holds in <tt>sensedir</tt>;</td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">and to state <tt>st2</tt> otherwise.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>Mark i st</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Set mark <tt>i</tt> in current cell and go to <tt>st</tt>.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>Unmark i st</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Clear mark <tt>i</tt> in current cell and go to <tt>st</tt>.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>PickUp st1 st2</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Pick up food from current cell and go to <tt>st1</tt>;</td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">go to <tt>st2</tt> if there is no food in the current cell.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>Drop st</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Drop food in current cell and go to <tt>st</tt>.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>Turn lr st</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Turn left or right and go to <tt>st</tt>.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>Move st1 st2</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Move forward and go to <tt>st1</tt>;</td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">go to <tt>st2</tt> if the cell ahead is blocked.</td>
</tr>
<tr><td nowrap="nowrap" align="left"><tt>Flip p st1 st2</tt></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">Choose a random number <tt>x</tt> from <tt>0</tt> to <tt>p-1</tt>;</td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">go to <tt>st1</tt> if <tt>x=0</tt> and <tt>st2</tt> otherwise.</td>
</tr></tbody></table>
</blockquote>
Here is a description of very simple ants in the finite state machine
language. The ant searches for food by performing a random walk until
it locates some food. It then picks up the food and wanders randomly
until it finds itself at home.<br>
<br>
<blockquote>
<pre>Sense Ahead 1 3 Food ; state 0: [SEARCH] is there food in front of me?
Move 2 0 ; state 1: YES: move onto food (return to state 0 on failure)
PickUp 8 0 ; state 2: pick up food and jump to state 8 (or 0 on failure)
Flip 3 4 5 ; state 3: NO: choose whether to...
Turn Left 0 ; state 4: turn left and return to state 0
Flip 2 6 7 ; state 5: ...or...
Turn Right 0 ; state 6: turn right and return to state 0
Move 0 3 ; state 7: ...or move forward and return to state 0 (or 3 on failure)
Sense Ahead 9 11 Home ; state 8: [GO HOME] is the cell in front of me my anthill?
Move 10 8 ; state 9: YES: move onto anthill
Drop 0 ; state 10: drop food and return to searching
Flip 3 12 13 ; state 11: NO: choose whether to...
Turn Left 8 ; state 12: turn left and return to state 8
Flip 2 14 15 ; state 13: ...or...
Turn Right 8 ; state 14: turn right and return to state 8
Move 8 11 ; state 15: ...or move forward and return to state 8
</pre>
</blockquote>
A more detailed specification of the state machine is given in the
following section.<br>
<br>
<!--TOC section Technicalities-->
<h2><a name="htoc2">2</a>&nbsp;&nbsp;Technicalities</h2><!--SEC END -->
The rest of this document specifies the rules of the game in detail.
For compactness, we use a combination of English descriptions and
program fragments written in a simple pseudo-code language. It should
be easy to translate this specification into a simulator in a
programming language of your choice, which you can use to develop and
test your ants. These details are given only for the rigor of
specification and the ease of implementation. The main part of the
contest should be the design of your ants rather than the
implementation of this simulator.<br>
<br>
<!--TOC subsection Geometry-->
<h3><a name="htoc3">2.1</a>&nbsp;&nbsp;Geometry</h3><!--SEC END -->
The <i>world</i> on which the game is played is a hexagonal grid (just
for fun).
A <i>position</i> in the world is an (<i>x</i>,<i>y</i>) coordinate, with (0,0) at
the upper-left corner of the world. <br>
<br>
<br>
<div align="center"><img src="2004-task_files/main001.gif"></div>
<br>
<br>
<br>
In the rest of the specification, we
use the type <tt><i>pos</i></tt> as an abbreviation for pairs of integers:
<blockquote><pre>type pos = (int, int)
</pre></blockquote>On a hexagonal grid, each cell is adjacent to six other cells. We number these in
clockwise order, from 0 (east) to 5 (north-east). We write <tt><i>dir</i></tt> below
for the type of integers that we intend to use as directions.
<blockquote><pre>type dir = 0..5
</pre></blockquote>
<br>
<div align="center"><img src="2004-task_files/main002.gif"></div>
<br>
<br>
<br>
If <tt><i>d</i></tt> is a direction and <tt><i>p</i></tt> = (<tt><i>x</i></tt>,<tt><i>y</i></tt>) is a position, then the function
<tt><i>adjacent</i>_<i>cell</i>(<i>p</i>,<i>d</i>)</tt>, which calculates the position of the cell adjacent to <tt><i>p</i></tt> in
direction <tt><i>d</i></tt>, can be defined as follows:
<blockquote><pre>function adjacent_cell(p:pos, d:dir):pos =
let (x,y) = p in
switch d of
case 0: (x+1, y)
case 1: if even(y) then (x, y+1) else (x+1, y+1)
case 2: if even(y) then (x-1, y+1) else (x, y+1)
case 3: (x-1, y)
case 4: if even(y) then (x-1, y-1) else (x, y-1)
case 5: if even(y) then (x, y-1) else (x+1, y-1)
</pre></blockquote>In our pseudo-code notation, functions are defined by <tt><i>function</i></tt>
declarations (as on the first line). The name and intended type of
each argument to the function are given in the form <tt><i>name</i>:<i>type</i></tt>.
If the function returns a value, its type is also given.
We use <tt><i>let</i></tt> (as on the second line) to bind names to the results
of intermediate calculations; here, <tt><i>x</i></tt> and <tt><i>y</i></tt> are the components of
the pair <tt><i>p</i></tt>. The expression ``<tt><i>switch</i></tt> ... <tt><i>of</i></tt> ...'' on the third and
following lines chooses one of the branches (the expressions following
``<tt><i>case</i></tt> ...<code>:</code>'') depending on the value of <tt><i>d</i></tt>.<br>
<br>
From its current orientation, an ant can turn one step to the left or
right. We write <tt><i>left</i>_<i>or</i>_<i>right</i></tt> for the set {<tt><i>Left</i></tt>,&nbsp;<tt><i>Right</i></tt>}. In
pseudo-code:
<blockquote><pre>type left_or_right = Left | Right
</pre></blockquote>Now, the <tt><i>turn</i></tt> function takes an element of this set and a direction and
returns a suitably adjusted direction.
<blockquote><pre>function turn(lr:left_or_right, d:dir):dir =
switch lr of
case Left: (d+5) mod 6
case Right: (d+1) mod 6
</pre></blockquote>
Ants can also sense their surroundings, by checking whether one of several
predicates (defined below) is true in either their current cell or one of
the three cells in front of them. The function <tt><i>sensed</i>_<i>cell</i></tt> calculates the
coordinates of the cell being sensed.
<blockquote><pre>type sense_dir =
Here /* sense the ant's current cell */
| Ahead /* sense the cell straight ahead in the direction ant is facing */
| LeftAhead /* sense the cell that would be ahead if ant turned left */
| RightAhead /* sense the cell that would be ahead if ant turned right */
function sensed_cell(p:pos, d:dir, sd:sense_dir):pos =
switch sd of
case Here: p
case Ahead: adjacent_cell(p, d)
case LeftAhead: adjacent_cell(p, turn(Left,d))
case RightAhead: adjacent_cell(p, turn(Right,d))
</pre></blockquote>
<!--TOC subsection Biology-->
<h3><a name="htoc4">2.2</a>&nbsp;&nbsp;Biology</h3><!--SEC END -->
There are two colors of ants:
<blockquote><pre>type color = Red | Black
</pre></blockquote>Given one color, the function <tt><i>other</i>_<i>color</i></tt> yields the other:
<blockquote><pre>function other_color(c:color):color =
switch c of
case Red: Black
case Black: Red
</pre></blockquote>The internal state of each ant can be described as a record with the following fields:
<ul><li>
A unique integer <tt><i>id</i></tt> that determines the order in which the ant takes its
turn to move or sense during each round of gameplay.
</li><li>A <tt><i>color</i></tt>.
</li><li>An integer between 0 and 9999 representing the current
<tt><i>state</i></tt> of its brain. (All the ants of each species run exactly the
same program, so the entire neural state of an ant of the species can
be characterized by just one number.)
</li><li>An integer <tt><i>resting</i></tt> that keeps track of how long the ant has to
rest after its last move before any other action. (Ants move much
more slowly than they can turn and sense their surroundings. This
is modeled by making an ant rest for 14 rounds after each time it
executes a <tt><i>Move</i></tt> instruction. Details of how this works are
specified in Section&nbsp;<a href="#step">2.11</a>.)
</li><li>A current <tt><i>direction</i></tt>.
</li><li>A boolean <tt><i>has</i>_<i>food</i></tt> indicating whether the ant is currently
carrying a food particle. (An ant can hold only a single unit of
food at a time.)
</li></ul>
Rather than making up pseudo-code syntax for creating, projecting, and
modifying records, we will simply assume we can use the following functions to
extract and modify the components of an ant:
<blockquote><pre>function state(a:ant):int = &lt;get state component of a&gt;
function color(a:ant):color = &lt;get color component of a&gt;
function resting(a:ant):int = &lt;get resting component of a&gt;
function direction(a:ant):dir = &lt;get direction component of a&gt;
function has_food(a:ant):bool = &lt;get has_food component of a&gt;
function set_state(a:ant, s:int) = &lt;set state component of a to be s&gt;
function set_resting(a:ant, r:int) = &lt;set resting component of a to be r&gt;
function set_direction(a:ant, d:dir) = &lt;set direction component of a to be d&gt;
function set_has_food(a:ant, b:bool) = &lt;set has_food component of a to be b&gt;
</pre></blockquote>
<!--TOC subsection Geography-->
<h3><a name="htoc5">2.3</a>&nbsp;&nbsp;Geography</h3><!--SEC END -->
Each cell in the world is either <i>clear</i> or <i>rocky</i>. The
predicate <tt><i>rocky</i>(<i>p</i>)</tt> is <tt><i>true</i></tt> if the cell at position <tt><i>p</i></tt> is rocky and <tt><i>false</i></tt>
if <tt><i>p</i></tt> is clear.
<blockquote><pre>function rocky(p:pos):bool = &lt;true if the cell at position p is rocky&gt;
</pre></blockquote>Rocky cells are not very interesting---they just impede movement. All the
action happens in clear cells.
At any given moment during the game, each clear cell contains:
<ul><li>
At most one <tt><i>ant</i></tt>.
</li><li>Some non-negative number of <tt><i>food</i></tt> particles. (There is no limit to the number of food particles that may be on a single
cell at a given time. An ant and any amount of food may be on a given
cell at the same time.)
</li><li>One set of chemical <tt><i>markers</i></tt> for each of the two ant colors.
</li></ul>
As we did for ants, we will not bother fixing a concrete representation for
this information. Instead, we assume we are given several functions for
investigating and manipulating the information in cells.
The first group of
functions concerns ants in cells:
<blockquote><pre>function some_ant_is_at(p:pos):bool =
&lt;true if there is an ant in the cell at position p&gt;
function ant_at(p:pos):ant =
&lt;return the ant in the cell at position p&gt;
function set_ant_at(p:pos, a:ant) =
&lt;record the fact that the given ant is at position p&gt;
function clear_ant_at(p:pos) =
&lt;record the fact that no ant is at position p&gt;
</pre></blockquote>The <tt><i>ant</i>_<i>at</i></tt> function should only be called on positions for which
<tt><i>some</i>_<i>ant</i>_<i>is</i>_<i>at</i></tt> returns <tt><i>true</i></tt>. <br>
<br>
Three more functions are useful for checking whether a given ant is
alive or dead and, if it is alive, finding the <em>position</em> of the
ant from its <tt><i>id</i></tt>.
<blockquote><pre>function ant_is_alive(id:int):bool =
&lt;true if an ant with the given id exists somewhere in the world&gt;
function find_ant(id:int):pos =
&lt;return current position of the ant with the given id&gt;
function kill_ant_at(p:pos) = clear_ant_at(p)
</pre></blockquote>The <tt><i>find</i>_<i>ant</i></tt> function should only be called when <tt><i>ant</i>_<i>is</i>_<i>alive</i></tt> is
<tt><i>true</i></tt>. A naive implementation of these functions could simply scan
all the cells in the world looking for an ant with the given <tt><i>id</i></tt>
field. Note that whether an ant is alive or dead is defined by
whether it exists somewhere in the world (as in <tt><i>ant</i>_<i>is</i>_<i>alive</i></tt> and
<tt><i>kill</i>_<i>ant</i>_<i>at</i></tt>) rather than the ant's own state. Of course, more
efficient implementations are possible.<br>
<br>
The next group of functions concerns food in cells:
<blockquote><pre>function food_at(p:pos):int =
&lt;return the amount of food in the cell at position p&gt;
function set_food_at(p:pos, f:int) =
&lt;record the fact that a given amount of food is at position p&gt;
</pre></blockquote>Note that the amount of food in a cell does <em>not</em> include the food being
carried by an ant in the cell (if any).<br>
<br>
Functions for checking and manipulating chemical markers will be given in
Section&nbsp;<a href="#chemistry">2.5</a>.<br>
<br>
Another important feature of the world's geography is anthills.
Some set of clear cells is designated as comprising the
<i>red anthill</i>. Another (disjoint) set of cells
constitutes the <i>black anthill</i>. The function <tt><i>anthill</i>_<i>at</i></tt> can
be used to check whether a given position is part of the anthill of a
given color.
<blockquote><pre>function anthill_at(p:pos, c:color):bool =
&lt;true if the cell at position p is in the anthill of color c&gt;
</pre></blockquote>
<!--TOC subsection Cartography-->
<h3><a name="htoc6">2.4</a>&nbsp;&nbsp;Cartography</h3><!--SEC END -->
Contest entries will be judged by playing them against each other on a
collection of worlds generated at random under certain constraints,
described in Section&nbsp;<a href="#contestworlds">3.1</a>. To facilitate testing and
save you the trouble of writing your own random world generator,
several of these worlds---similar but not identical to the ones we
will actually use for judging---can be found on the contest web site
at <a href="http://icfpcontest.org/worlds/"><tt>http://icfpcontest.org/worlds/</tt></a>. The concrete format of
these worlds is as follows:
<ul><li>
The first line contains a single integer representing the size of the
world in the <tt><i>x</i></tt> dimension.
</li><li>The second line contains a single integer representing the size of the
world in the <tt><i>y</i></tt> dimension.
</li><li>The rest of the file consists of <tt><i>y</i></tt> lines, each containing <tt><i>x</i></tt>
one-character cell specifiers, separated by spaces (even lines also
contain a leading space before the first cell specifier). The top-left
cell specifier corresponds to position (0,0).
</li></ul>
The possible cell specifiers are:
<blockquote><pre> # rocky cell
. clear cell (containing nothing interesting)
+ red anthill cell
- black anthill cell
1 to 9 clear cell containing the given number of food particles
</pre></blockquote>For example, here is a concrete description of a very tiny world (this
world is for testing only; it does not qualify as a world used for
judging as described in Section&nbsp;<a href="#contestworlds">3.1</a>):
<blockquote>
<blockquote><a name="tiny"></a>
<pre>10
10
# # # # # # # # # #
# 9 9 . . . . 3 3 #
# 9 # . - - - - - #
# . # - - - - - - #
# . . 5 - - - - - #
# + + + + + 5 . . #
# + + + + + + # . #
# + + + + + . # 9 #
# 3 3 . . . . 9 9 #
# # # # # # # # # #
</pre>
</blockquote>
</blockquote>
Note that world description files do not explicitly mention ants. Instead,
during initialization, each anthill cell is populated with an ant of the
same color (see Section&nbsp;<a href="#init">2.12</a>).<br>
<br>
<!--TOC subsection Chemistry-->
<h3><a name="htoc7">2.5</a>&nbsp;&nbsp;Chemistry</h3><!--SEC END -->
<a name="chemistry"></a>
Each ant can place and sense 6 different kinds of
<i>chemical markers</i>, numbered <tt>0</tt> through <tt>5</tt>.
<blockquote><pre>type marker = 0..5
</pre></blockquote>The markers for the two colors of
ants are completely separate---i.e., the marks in each cell contain 12 bits
worth of information. The following functions are used to investigate and
manipulate the markers in a cell.
<blockquote><pre>function set_marker_at(p:pos, c:color, i:marker) =
&lt;set marker i of color c in cell p&gt;
function clear_marker_at(p:pos, c:color, i:marker) =
&lt;clear marker i of color c in cell p&gt;
function check_marker_at(p:pos, c:color, i:marker):bool =
&lt;true if marker i of color c is set in cell p&gt;
function check_any_marker_at(p:pos, c:color):bool =
&lt;true if ANY marker of color c is set in cell p&gt;
</pre></blockquote>Note the final function, <tt><i>check</i>_<i>any</i>_<i>marker</i>_<i>at</i></tt>. Ants of a given color can
individually sense, set, and clear all 6 of their own markers, but are only
able to detect the presence of <em>some</em> marker belonging to the other
species. <br>
<br>
Unlike the chemical markers used by real ants, markers in this game persist
until they are explicitly cleared. All markers in all cells are initially
clear. <br>
<br>
<!--TOC subsection Phenomenology-->
<h3><a name="htoc8">2.6</a>&nbsp;&nbsp;Phenomenology</h3><!--SEC END -->
The <tt><i>Sense</i></tt> instruction in the ant control language described below can be
used to check a number of conditions:
<blockquote><pre>type condition =
Friend /* cell contains an ant of the same color */
| Foe /* cell contains an ant of the other color */
| FriendWithFood /* cell contains an ant of the same color carrying food */
| FoeWithFood /* cell contains an ant of the other color carrying food */
| Food /* cell contains food (not being carried by an ant) */
| Rock /* cell is rocky */
| Marker(marker) /* cell is marked with a marker of this ant's color */
| FoeMarker /* cell is marked with *some* marker of the other color */
| Home /* cell belongs to this ant's anthill */
| FoeHome /* cell belongs to the other anthill */
</pre></blockquote>Note that the <tt><i>Marker</i></tt> condition is parameterized by the kind of the
chemical marker to be sensed: an ant can test for the presence of just
one of its own markers in a single instruction.<br>
<br>
The function <tt><i>cell</i>_<i>matches</i></tt> takes a position <tt><i>p</i></tt>, a condition <tt><i>cond</i></tt>,
and a color <tt><i>c</i></tt> (the color of the ant that is doing the sensing), and
checks whether <tt><i>cond</i></tt> holds at <tt><i>p</i></tt>.
<blockquote><pre>function cell_matches(p:pos, cond:condition, c:color):bool =
if rocky(p) then
if cond = Rock then true else false
else
switch cond of
case Friend:
some_ant_is_at(p) &amp;&amp;
color(ant_at(p)) = c
case Foe:
some_ant_is_at(p) &amp;&amp;
color(ant_at(p)) &lt;&gt; c
case FriendWithFood:
some_ant_is_at(p) &amp;&amp;
color(ant_at(p)) = c &amp;&amp;
has_food(ant_at(p))
case FoeWithFood:
some_ant_is_at(p) &amp;&amp;
color(ant_at(p)) &lt;&gt; c &amp;&amp;
has_food(ant_at(p))
case Food:
food_at(p) &gt; 0
case Rock:
false
case Marker(i):
check_marker_at(p, c, i)
case FoeMarker:
check_any_marker_at(p, other_color(c))
case Home:
anthill_at(p, c)
case FoeHome:
anthill_at(p, other_color(c))
</pre></blockquote>The operator <tt>&amp;&amp;</tt> here represents <em>boolean and</em>. (Below, <tt>||</tt>
represents <em>boolean or</em>).<br>
<br>
<!--TOC subsection Neurology-->
<h3><a name="htoc9">2.7</a>&nbsp;&nbsp;Neurology</h3><!--SEC END -->
<a name="instructions"></a>
The brain of each species of ant consists of a simple finite state
machine. States are numbered beginning from 0 (up to
a maximum of 9999).
<blockquote><pre>type state = int
</pre></blockquote>In each state, the next action to be taken and the next state(s) to enter
after executing the action are determined by one of the following
<tt><i>instruction</i></tt>s:
<blockquote><pre>type instruction =
Sense(sense_dir, state, state, condition)
| Mark(marker, state)
| Unmark(marker, state)
| PickUp(state, state)
| Drop(state)
| Turn(left_or_right, state)
| Move(state, state)
| Flip(int, state, state)
</pre></blockquote>The meanings of these instructions are specified formally in the <tt><i>step</i></tt>
function in Section&nbsp;<a href="#step">2.11</a>.<br>
<br>
Conceptually, each ant brain is just an array of instructions, indexed by
states. We use the function <tt><i>get</i>_<i>instruction</i>(<i>c</i>,<i>s</i>)</tt> to retrieve the instruction
for state <tt><i>s</i></tt> in the brain of color <tt><i>c</i></tt>. (All ants of the same color have
the same state machine in their brains.)
<blockquote><pre>function get_instruction(c:color, s:state):instruction =
&lt;get the instruction for state s of ant color c&gt;
</pre></blockquote>
<!--TOC subsection Neuro-Cartography-->
<h3><a name="htoc10">2.8</a>&nbsp;&nbsp;Neuro-Cartography</h3><!--SEC END -->
<a name="antsyn"></a>
Each contest entry is a file describing an ant state machine. The concrete
format of these files is as follows:
<ul><li>
Each line in the file represents one state. The first line is state
0, the second line state 1, and so on.
</li><li>The file may contain no more than 10000 lines. (It may contain
fewer.)
</li><li>Each line consists of a sequence of whitespace-separated <em>tokens</em>,
followed (optionally) by a comment beginning with a
semicolon and extending to the end of the line.
</li><li>Tokens are either keywords or integers. Keywords are case-insensitive.
</li><li>The first token on the line indicates the instruction. The others
supply the required arguments, depending on the instruction as in Section&nbsp;<a href="#instructions">2.7</a>.
</li><li>The possible tokens for instructions are:
<blockquote><pre> Sense
Mark
Unmark
PickUp
Drop
Turn
Move
Flip
</pre></blockquote>The tokens for sensing directions are:
<blockquote><pre> Here
Ahead
LeftAhead
RightAhead
</pre></blockquote>The tokens for conditions are:
<blockquote><pre> Friend
Foe
FriendWithFood
FoeWithFood
Food
Rock
Marker
FoeMarker
Home
FoeHome
</pre></blockquote>The tokens for arguments to <tt><i>turn</i></tt> are:
<blockquote><pre> Left
Right
</pre></blockquote>Note that the tokens are exactly the same as the names used in our pseudo-code
type definitions.
</li><li>Thus, the concrete syntax of each instruction line can be summarized as
follows:
<div align="center"><table>
<tbody><tr valign="middle"><td nowrap="nowrap">
</td>
<td nowrap="nowrap"><table cellpadding="0" cellspacing="2">
<tbody><tr><td nowrap="nowrap" align="left"><i><i>instruction</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Sense</i></tt>&nbsp;&nbsp;<i><i>sensedir</i></i>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">1</font></sub>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">2</font></sub>&nbsp;&nbsp;<i><i>cond</i></i></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Mark</i></tt>&nbsp;&nbsp;<i>i</i>&nbsp;&nbsp;<i><i>st</i></i></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Unmark</i></tt>&nbsp;&nbsp;<i>i</i>&nbsp;&nbsp;<i><i>st</i></i></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>PickUp</i></tt>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">1</font></sub>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">2</font></sub></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Drop</i></tt>&nbsp;&nbsp;<i><i>st</i></i></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Turn</i></tt>&nbsp;&nbsp;<i><i>lr</i></i>&nbsp;&nbsp;<i><i>st</i></i></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Move</i></tt>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">1</font></sub>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">2</font></sub></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Flip</i></tt>&nbsp;&nbsp;<i>p</i>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">1</font></sub>&nbsp;&nbsp;<i><i>st</i></i><sub><font size="2">2</font></sub></td>
</tr>
<tr><td nowrap="nowrap" align="left"><i><i>sensedir</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Here</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Ahead</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>LeftAhead</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>RightAhead</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left"><i><i>cond</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Friend</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Foe</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>FriendWithFood</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>FoeWithFood</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Food</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Rock</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Marker</i></tt>&nbsp;&nbsp;<i>i</i></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>FoeMarker</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Home</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left">&nbsp;</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">|</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>FoeHome</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left"><i><i>lr</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left"><tt><i>Left</i></tt> | <tt><i>Right</i></tt></td>
</tr>
<tr><td nowrap="nowrap" align="left"><i><i>st</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">0 | 1 | 2 | ... | 9999</td>
</tr>
<tr><td nowrap="nowrap" align="left"><i><i>i</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">0 | 1 | 2 | 3 | 4 | 5</td>
</tr>
<tr><td nowrap="nowrap" align="left"><i><i>p</i></i></td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="center">::=</td>
<td nowrap="nowrap" valign="top" align="center">&nbsp;&nbsp;</td>
<td nowrap="nowrap" align="left">1 | 2 | 3 | ...</td>
</tr></tbody></table></td>
</tr></tbody></table></div>
Note the syntax of <tt><i>Marker</i></tt> conditions.
See also <a href="http://icfpcontest.org/sample.ant"><tt>http://icfpcontest.org/sample.ant</tt></a> for an example.
</li></ul>
<!--TOC subsection Martial Arts-->
<h3><a name="htoc11">2.9</a>&nbsp;&nbsp;Martial Arts</h3><!--SEC END -->
Besides gathering food, ants may engage in combat with other ants. The
rules are simple:
<ul><li>
If an ant ever finds itself adjacent to 5 (or 6) ants of the other
species, it dies.
</li><li>When an ant dies, it turns into 3 particles of food.
</li></ul>
More formally:
<blockquote><pre>function adjacent_ants(p:pos, c:color):int =
let n = 0 in
for d = 0..5 do
let cel = adjacent_cell(p, d) in
if some_ant_is_at(cel) &amp;&amp; color(ant_at(cel)) = c then &lt;increment n by 1&gt;
end;
n
</pre></blockquote>
<blockquote><pre>function check_for_surrounded_ant_at(p:pos) =
if some_ant_is_at(p) then
let a = ant_at(p) in
if adjacent_ants(p, other_color(color(a))) &gt;= 5 then begin
kill_ant_at(p);
set_food_at(p, food_at(p) + 3 + (if has_food(a) then 1 else 0))
end
</pre></blockquote>
<blockquote><pre>function check_for_surrounded_ants(p:pos) =
check_for_surrounded_ant_at(p);
for d = 0..5 do
check_for_surrounded_ant_at(adjacent_cell(p,d))
end
</pre></blockquote>The last function is used in Section&nbsp;<a href="#step">2.11</a> for checking possible
death each time an ant moves.<br>
<br>
<!--TOC subsection Number Theory-->
<h3><a name="htoc12">2.10</a>&nbsp;&nbsp;Number Theory</h3><!--SEC END -->
<a name="random"></a>
To implement the <tt><i>Flip</i></tt> instruction, we need a source of random numbers.
Pretty much any pseudo-random number generator will do for this, but,
if you want to test that your simulator gives exactly the same
results as ours, you will want to use the same random numbers that we do.
To this end, let us define a function <tt><i>randomint</i></tt> that, whenever it is called
with a positive argument <tt><i>n</i></tt>, yields a pseudo-random integer between <tt>0</tt> and <tt><i>n</i></tt>-1,
inclusive.
<blockquote><pre>function randomint(n:int):int = ...
</pre></blockquote>The sequence of numbers returned by <tt><i>randomint</i></tt> may be specified as follows:
<ul><li>
Let <i>s</i><sub><font size="2">0</font></sub> be an <i>initial seed</i> for the series.
</li><li>For each <i>i</i>, calculate <i>s</i><sub><font size="2"><i>i</i>+1</font></sub> from <i>s</i><sub><font size="2"><i>i</i></font></sub> as follows:
<div align="center">
<i>s</i><sub><font size="2"><i>i</i>+1</font></sub> = <i>s</i><sub><font size="2"><i>i</i></font></sub> × 22695477 + 1
</div>
The multiplication and addition operations here are the ordinary mathematical
ones---i.e., the specification is phrased in terms of infinite-precision integers.
</li><li>Next, we calculate another series <i>x</i><sub><font size="2">0</font></sub>, <i>x</i><sub><font size="2">1</font></sub>, etc. from the elements
<i>s</i><sub><font size="2">4</font></sub>,&nbsp;
<i>s</i><sub><font size="2">5</font></sub>, etc. of the first series:
<div align="center">
<i>x</i><sub><font size="2"><i>i</i></font></sub> = (<i>s</i><sub><font size="2"><i>i</i>+4</font></sub> <b>div</b> 65536) <b>mod</b> 16384
</div>
Again, the integer division and modulus operations are the ordinary
mathematical ones.
</li><li>Now, if the the <i>i</i><sup><font size="2"><font size="1">th</font></font></sup> call to <tt><i>randomint</i></tt> is given
argument <tt><i>n</i></tt>, then the result is
<div align="center">
<i>x</i><sub><font size="2"><i>i</i></font></sub> <b>mod</b> <tt><i>n</i></tt>.
</div>
</li></ul>
This specification can readily be translated into ordinary fixed-precision
arithmetic in many programming languages using the standard multiplication,
addition, and bitwise operations on machine integers. To help you check
that your implementation of <tt><i>randomint</i></tt> matches ours, here are our values
for <i>x</i><sub><font size="2">0</font></sub> to <i>x</i><sub><font size="2">99</font></sub>, when the initial seed <i>s</i><sub><font size="2">0</font></sub> is 12345:
<blockquote>
7193, 2932, 10386, 5575, 100, 15976, 430, 9740, 9449, 1636, 11030, 9848,
13965, 16051, 14483, 6708, 5184, 15931, 7014, 461, 11371, 5856, 2136, 9139,
1684, 15900, 10236, 13297, 1364, 6876, 15687, 14127, 11387, 13469, 11860,
15589, 14209, 16327, 7024, 3297, 3120, 842, 12397, 9212, 5520, 4983, 7205,
7193, 4883, 7712, 6732, 7006, 10241, 1012, 15227, 9910, 14119, 15124, 6010,
13191, 5820, 14074, 5582, 5297, 10387, 4492, 14468, 7879, 8839, 12668,
5436, 8081, 4900, 10723, 10360, 1218, 11923, 3870, 12071, 3574, 12232,
15592, 12909, 9711, 6638, 2488, 12725, 16145, 9746, 9053, 5881, 3867,
10512, 4312, 8529, 1576, 15803, 5498, 12730, 7397.
</blockquote>
<!--TOC subsection Kinetics-->
<h3><a name="htoc13">2.11</a>&nbsp;&nbsp;Kinetics</h3><!--SEC END -->
<a name="step"></a>
At last, we are ready to describe what happens when an ant actually
executes an instruction. The function <tt><i>step</i></tt> takes an ant <tt><i>id</i></tt>, finds
that ant in the world (if it is still alive), gets the instruction
corresponding to its current <tt><i>state</i></tt>, evaluates the instruction, and
changes the ant's internal state and the state of the world. Note
that the step for Move instructions takes into account the rest period
needed after an ant moves. It also checks whether the ant's movement
has caused an enemy to become surrounded.
<blockquote><pre>function step(id:int) =
if ant_is_alive(id) then
let p = find_ant(id) in
let a = ant_at(p) in
if resting(a) &gt; 0 then
set_resting(a, resting(a) - 1)
else
switch get_instruction(color(a), state(a)) of
case Sense(sensedir, st1, st2, cond):
let p' = sensed_cell(p, direction(a), sensedir) in
let st = if cell_matches(p', cond, color(a)) then st1 else st2 in
set_state(a, st)
case Mark(i, st):
set_marker_at(p, color(a), i);
set_state(a, st)
case Unmark(i, st):
clear_marker_at(p, color(a), i);
set_state(a, st)
case PickUp(st1, st2):
if has_food(a) || food_at(p) = 0 then
set_state(a, st2)
else begin
set_food_at(p, food_at(p) - 1);
set_has_food(a, true);
set_state(a, st1)
end
case Drop(st):
if has_food(a) then begin
set_food_at(p, food_at(p) + 1);
set_has_food(a, false)
end;
set_state(a, st)
case Turn(lr, st):
set_direction(a, turn(lr, direction(a)));
set_state(a, st)
case Move(st1, st2):
let newp = adjacent_cell(p, direction(a)) in
if rocky(newp) || some_ant_is_at(newp) then
set_state(a, st2)
else begin
clear_ant_at(p);
set_ant_at(newp, a);
set_state(a, st1);
set_resting(a, 14);
check_for_surrounded_ants(newp)
end
case Flip(n, st1, st2):
let st = if randomint(n) = 0 then st1 else st2 in
set_state(a, st)
</pre></blockquote>
A single <em>round</em> of the game consists of executing the next instruction
for every ant---i.e., calling the <tt><i>step</i></tt> function for each ant in numerical
order, from 0 up to the maximum <tt><i>id</i></tt>.<br>
<br>
<!--TOC subsection Game Play and Scoring-->
<h3><a name="htoc14">2.12</a>&nbsp;&nbsp;Game Play and Scoring</h3><!--SEC END -->
<a name="init"></a>
A complete <em>game</em> is played as follows:
<ul><li>
The world and the brains of the two ants are loaded from files as
described above
</li><li>Each cell in the red anthill is populated with a red ant and each black
anthill cell with a black ant. The ants all start in state 0, facing east
(direction 0), and not carrying any food.
</li><li>All ants (regardless of their colors) are assigned identities in
top-to-bottom, left-to-right order---i.e., the topmost-leftmost ant
gets identity 0; the next ant to its right gets identity 1; etc.
When all ants on the topmost row have been assigned identities, then
the leftmost ant on the second row down gets the next identity, and
so on.
</li><li>The game is played for 100,000 complete rounds. (I.e., every
ant gets to execute up to 100,000 instructions.)
</li><li>At the end, we count the number of food particles currently
in the anthill cells of each color. The color with the most
food wins. Remember that food being carried by an ant does not count, even if it
is standing on its own anthill.
</li></ul>
<!--TOC subsection Testing-->
<h3><a name="htoc15">2.13</a>&nbsp;&nbsp;Testing</h3><!--SEC END -->
<a name="testing"></a>
To make sure your simulator is behaving exactly the same as ours, you
may find it useful to compare their results step by step. The file
<a href="http://icfpcontest.org/tiny.world"><tt>http://icfpcontest.org/tiny.world</tt></a> on the contest web site
contains the tiny world shown in Section&nbsp;<a href="#tiny">2.4</a>. The file
<a href="http://icfpcontest.org/sample.ant"><tt>http://icfpcontest.org/sample.ant</tt></a> contains an ant that is
written in a convoluted way so as to exercise most of the control
paths in the simulator. The directory
<a href="http://icfpcontest.org/dump/"><tt>http://icfpcontest.org/dump/</tt></a> contains complete traces of
the state of our simulator after each round in a game pitting this ant
against itself on this tiny world with initial random seed <i>s</i><sub><font size="2">0</font></sub> =
12345. These traces show the initial random seed and the entire
state of the world after every round between 0 and 10,000. This state
of the world contains the state of every cell---whether it is rocky,
the number of food (if any), the color of a hill (if the cell is a
hill), all the red and black marks in the cell, and the state of an
ant (if there is one) in this order. The state of an ant consists of
its color, id, direction, number of food being carried, state, and the
<tt><i>resting</i></tt> field.
The first executed round of the game is Round 1. Round 0 in the
beginning of the dump just marks the description of the initial state.
See the actual files for more details. All
the files are in ASCII code with 0x0a (called LF or NL, also known as
the UNIX newline code) for the end of a line.<br>
<br>
<!--TOC section Contest Mechanics-->
<h2><a name="htoc16">3</a>&nbsp;&nbsp;Contest Mechanics</h2><!--SEC END -->
<!--TOC subsection Contest Worlds-->
<h3><a name="htoc17">3.1</a>&nbsp;&nbsp;Contest Worlds</h3><!--SEC END -->
<a name="contestworlds"></a>
The design of effective strategies for this game is quite sensitive to
several specific parameters---the size of the world, the number of
ants, the amount and density of food available in the world, and the
sorts of obstacles that may be encountered.<br>
<br>
The worlds used for judging will be randomly generated, according to the
following rules:
<ul><li>
The dimensions of the world are always 100 × 100 cells.
</li><li>The cells on the perimeter are always rocky.
</li><li>Every world contains exactly the same <i>elements</i>, of particular shapes: two
anthills, ten rocks, and eight blobs of
food. The anthills, in particular, are hexagons with sides of length 6.
Also, a food blob is always a 3-by-4 rectangle, with each cell containing 5
food particles.
</li><li>The positions and orientations of the elements are chosen
randomly, subject to the constraint that there is always at least
one empty cell between non-food elements. Also, no elements overlap.
(The anthill elements are 6-ways-symmetric, so their orientation
actually does not matter. All ants are initially facing in direction 0.)
</li></ul>
A collection of random worlds satisfying these specifications can be
found on the contest web site at
<a href="http://icfpcontest.org/worlds/"><tt>http://icfpcontest.org/worlds/</tt></a>. Here is one of them:
<blockquote>
<pre><font size="1">
100
100
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . - - - - - - . . . . . . . . . . . . . + + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . - - - - - - - . . . . . . . . . . . . + + + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . - - - - - - - - . . . . . . . . . . . + + + + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . - - - - - - - - - . . . . . . . . . . . + + + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . - - - - - - - - - - . . . . . . . . . . . + + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . - - - - - - - - - - - . . . . . . . . . . . + + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . - - - - - - - - - - . . . . . . . . . . . . + + + + + + + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . - - - - - - - - - . . . . . . . . . . . . . + + + + + + . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . - - - - - - - - . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . - - - - - - - . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . - - - - - - . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . #
# . . . . . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . # # . . . . . . . . . . . . #
# . . . . . . . . . . . . 5 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . # # . . . . . . . . . . . . . #
# . . . . . . . . . . . . 5 5 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . # # . . . . . . . . . . . . . . # # . . . . . . . . . . . . . #
# . . . . . . . . . . . 5 5 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . # # # . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . #
# . . . . . . . . . . . . 5 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . # # # . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . #
# . . . . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . # # . . . . . . . . . . . . . . # # # # # # # # # . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . # # # . . . . . . . . . . . . . # # # # # # # # # # . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . # # # # . . . . . . . . . . . . # # . . . . . . # # . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . # # . # # . . . # . . . . . . . # # . . . . . . # # . . . . . 5 5 5 #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # # . . # # . . # # . . . . . . # # # # # # # # # # . . . . . 5 5 5 . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . # # . # # . . . . . . # # # # # # # # # . . . . . . 5 5 5 . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . # # # # . . . . . . . . . . . . . . . . . . . . . 5 5 5 . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . # . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . # # # # # # # # . . . . . . . . . . # # . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . # # # # # # # # # # . . . . . . . . . # # . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . # # . . . . . . # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . # # . . . . . . # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . # # . . . . # . # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . # # . . . # . . # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . # # . . # . . . # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . # # . # . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . # # . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . # # . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . # . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . 5 5 5 5 . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . # . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . # # . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . # # . . . . . . # # . . . . . . . . . . . . . . . . . . # . . . . . . . . . # # # # # # # # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . # . . . . . . # # . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . # # . . . . . # # . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . # # . . . . # # . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . 5 5 . . . . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . # # . . . # # . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . 5 5 5 . 5 . . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . # # . . # # . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . 5 5 5 . 5 5 . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . # # . # # . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . 5 5 . 5 5 5 . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # . . . . . . 5 . . 5 5 5 . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . 5 5 5 5 . . . . . . . . . . . . . . # # . . . . . . . . . 5 5 . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . # # . . . . . . . . 5 5 5 5 . . . . . . . . . . . . . . # # . . . . . . . . . 5 . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 5 . . . . . . . . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
</font></pre><font size="1">
</font>
</blockquote>
<!--TOC subsection Judging-->
<h3><a name="htoc18">3.2</a>&nbsp;&nbsp;Judging</h3><!--SEC END -->
<a name="judging"></a>
During the tournament, each pair of submissions is pitted against each
other <em>twice</em> on each of the contest worlds---once with the first
submission playing red and the second black, and once with the first
playing black and the second red. A submission gains 2 points for
each game it wins, and 1 point for each draw. The submission with the
most points wins the tournament. The number of the worlds used during
the tournament is unspecified, but will be large enough for
determining a clear winner. If there is nevertheless no clear winner,
the tournament is repeated with a certain number of finalist
submissions.
The seed used by the random number generator is unspecified.<br>
<br>
<!--TOC subsection General Information and Submission Instructions-->
<h3><a name="htoc19">3.3</a>&nbsp;&nbsp;General Information and Submission Instructions</h3><!--SEC END -->
See
<a href="http://icfpcontest.org/rules.php"><tt>http://icfpcontest.org/rules.php</tt></a>
and
<a href="http://icfpcontest.org/submit.php"><tt>http://icfpcontest.org/submit.php</tt></a>
for the contest rules and submission instructions.<br>
<br>
<!--TOC section Change Log-->
<h2><a name="htoc20">4</a>&nbsp;&nbsp;Change Log</h2><!--SEC END -->
<ol type="1"><li>
Initial release.
</li><li>Typo fixed in a URL.
</li><li>The concrete syntax of ant instructions clarified (the last itemization in Section&nbsp;<a href="#antsyn">2.8</a>).
</li><li>Miscellaneous non-critical clarifications and fixes:
shape of food blobs (Section&nbsp;<a href="#contestworlds">3.1</a>),
random seed for tournaments (Section&nbsp;<a href="#judging">3.2</a>),
meaning of ``Round 0'' in the dump files (Section&nbsp;<a href="#testing">2.13</a>),
a variable bound in the <tt>Flip</tt> case of <tt>step</tt> function does not
anymore shadow the earlier binding for <tt>p</tt> (Section&nbsp;<a href="#step">2.11</a>),
removed 0 from the grammar for <i>p</i> (Section&nbsp;<a href="#antsyn">2.8</a>) and
noticed that <tt>randomint</tt> expects a positive argument
(Section&nbsp;<a href="#random">2.10</a>).
<a name="currentversion"></a></li></ol>
<!--BEGIN NOTES document-->
<hr size="1" width="50%"><dl><dt><a name="note1" href="#text1"><font size="5">1</font></a></dt><dd>
Malo Denielou,
Nate Foster,
Vladimir Gapeyev,
Michael Levin,
Benjamin Pierce,
Eijiro Sumii,
Stephen Tse,
Dimitrios Vytiniotis,
Geoff Washburn,
Stephanie Weirich,
and
Steve Zdancewic
</dd></dl>
<!--END NOTES-->
<!--HTMLFOOT-->
<!--ENDHTML-->
<!--FOOTER-->
<hr size="2">
<blockquote><em>This document was translated from L<sup>A</sup>T<sub>E</sub>X by
</em><a href="http://pauillac.inria.fr/%7Emaranget/hevea/index.html"><em>H<font size="2"><sup>E</sup></font>V<font size="2"><sup>E</sup></font>A</em></a><em>.
</em></blockquote>
</body></html>