documents/rules.html

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <link rel="stylesheet" href="samuraidocs.css" >
    <title>SamurAI Dig Here Game Rules</title>
  </head>
  <body>
    <span style="float:left">
      <a href="rules-jp.html" target="_blank">日本語</a>
    </span>
    <h1>SamurAI Dig Here Game Rules</h1>
    <center>
      <p>
	IPSJ Programming Contest Committee<br>
	2019/12/06
      </p>
      <p style="width:70%">
	This document gives the rules of the <em>SamurAI Dig Here</em> game,
	played in the programming contest <em>SamurAI Coding 2019-20</em>
	organized by Information Processing Society of Japan.
      </p>
    </center>

    <h2>Game Overview</h2>
    <p>
      The game is a zero-sum game with imperfect information,
      played by two teams each with two player agents controlled by
      programs provided by the contestants.
      The objective of the game is to dig out as much treasure buried in
      the game field as possible.
    </p>

    <img src="screenShots/small-field.png" width="50%" class="figure">
    <h3>Game Field</h3>
    <p>
      The game field has a square shape, divided into small squares
      called <em>cells</em> aligned in a square lattice.  The size of
      the game field, that is, the number of cells in one side of the
      field may differ from one game to another.  The minimum size is
      six.
    </p>
    <p>
      The figure to the right is a bird’s eye view of the square game
      field from a diagonal direction.
    </p>

    <h3>Game Agents</h3>
    <p>
      Both teams have two agents each, one <em>samurai</em> and
      one <em>dog.</em>
    </p>
    <p>
      Game agents are controlled by programs provided by the
      contestants.  A single program is run as two separate processes,
      one for controlling the samurai and one for the dog of a team.
      They share only those information provided by the game
      management system.  No other communication is possible.
    </p>
    <p>
      When the game starts, agents are positioned in some distinct cells
      in the field.  More than one agents cannot be in the same cell at
      a time throughout a game.
    </p>
    <p>
      In one step of a game, a samurai agent can move to one of
      the <em>four</em> neighboring cells, that is, those cells that
      share a edge with the cell the samurai is in.  A dog agent can
      move to one of the <em>eight</em> neighboring cells, that is,
      those cell that share one or two corners with the cell the dog
      is in.  They can also stay in the cell they are in.
    </p>
    <p>
      When two or more agents are instructed to move to the same cell,
      none of the agents can make their moves.
      All such agents are kept in their original positions.
    </p>

    <h3>Holes</h3>
    <p>
      Some of the cells in the field may have a <em>hole</em> in them,
      preventing game agents to step into.  A samurai agents can,
      however, instead of making a move, plug a hole in one of the
      four neighboring cells.  Samurai can also dig new holes in the
      four neighboring cells.  Digging a new hole is not possible if
      another agent is already in the cell or moves to the cell in the
      same step.
    </p>
    <p>
      No holes are in the cells where a agents are initially in.
    </p>

    <h3>Buried Treasures</h3>
    <p>
      Some of the cells in the field may have <em>buried treasure</em> in them.
      Digging a new hole in a cell with buried treasure digs it out.
      If samurai of both teams dig a hole in the same cell in the same step,
      the treasure dug out is halved and shared by the two teams.
      The amounts of buried treasure are always an even number.
    </p>
    <p>
      A dog in one of the eight neighboring cells of the cell with
      buried treasure can sense the position as well as its amount, but
      they are <em>not</em> informed to the rest of agents.
      Dogs bark when they step into a cell with buried treasure,
      making the treasure position and its amount known to <em>all</em>
      the other agents.
      Not only the colleague samurai but also the opponent samurai
      and the opponent dog hear the bark.
    </p>
    <p>
      Treasures are not buried in the initial positions of agents
      nor in the cells with holes.
    </p>

    <h3>Game Steps</h3>
    <p>
      A game is played in a step-wise manner.  When a game step
      starts, all the agents make their <em>play plans</em> of the
      step simultaneously.  The play plans are checked their validity
      and also collated to detect conflicts between them, resulting in
      a set of <em>actions</em> the agents can actually take.  The
      actions are then carried out and the field state is updated.
    </p>
    <p>
      Game steps are repeated until the predefined maximum number of
      steps are played or all the buried treasures have been excavated.
    </p>

    <h2>Player Programs</h2>
    <h3>Player Processes</h3>
    <p>
      The contestant should provide a <em>player program</em> for
      controlling two agents, a samurai and a dog, belonging to the
      team.
    </p>
    <p>
      The game management system starts two <em>player processes</em>
      for each of the two teams.  The two player processes of one
      teams execute the same program, one of which controls the
      samurai and the other the dog of the team.  Which agent to
      control is informed by the game management system after the
      processes are started.
    </p>
    <p>
      The player processes have no direct communication paths between
      them; the only communication possible is with the game
      management system.
    </p>

    <h3>Input and Output</h3>
    <p>
      At the start of each of the game step,
      the game management system sends information on the game state
      to those player processes.
      Each player process should receive the information and respond with
      a play plan for the corresponding agent.
    </p>
    <p>
      The game state information sent from the game manager can be read
      from the standard input of the player process.
      The play plan in its response should be sent to the standard output.
    </p>

    <h3>Play Plans and Actions</h3>
    <p>
      The <em>play plans</em> are the plans of agents' plays sent by the
      player programs, and the <em>actions</em> are the plays actually
      taken by the agents decided by the game management system after
      validity conflict checks.
    </p>
    <p>
      For example, if two agents' play plans tell to move to the same
      cell, their plans conflict each other, and thus the game
      management system makes both of the agents stop.
      If a samurai plans to dig a new hole in a cell and another agent
      plans to move to the same cell, the move has the precedence and
      the digging will be unsuccessful.
      If, however, two other agents plan to move to the cell in which
      a dig is planned, the moves conflict with each other and are
      canceled, and the dig will be effective.
    </p>
    <p>
      Each of play plans and actions is represented as an
      integer <var>m</var> (-1 &leq; <var>m</var> &leq; 23), meaning
      the following.
      <div class="figure">
	<table class="bordered">
	  <tr>
	    <th></th>
	    <th><var>x</var>&minus;1</th>
	    <th><var>x</var></th>
	    <th><var>x</var>&plus;1</th>
	  </tr>
	  <tr>
	    <th><var>y</var>&minus;1</th>
	    <td>3</td><td>4</td><td>5</td>
	  </tr>
	  <tr>
	    <th><var>y</var></th>
	    <td>2</td><td></td><td>6</td>
	  </tr>
	  <tr>
	    <th><var>y</var>&plus;1</th>
	    <td>1</td><td>0</td><td>7</td>
	  </tr>
	</table>
	<center>
	  <caption>Designated Cells</caption>
	</center>
      </div>
      <dl>
	<dt>&minus;1</dt>
	<dd>Stay in the cell the agent is located without any move.</dd>
	<dt>0, &hellip;, 7</dt>
	<dd>Move to one of the neighboring cells.</dd>
	<dt>8, &hellip;, 15</dt>
	<dd>Dig a new hole in one of the neighboring cells.</dd>
	<dt>16, &hellip;, 23</dt>
	<dd>Plug the hole in one of the neighboring cells.</dd>
      </dl>
      The coordinates of the target cell, that is the agent moves to or
      the cell to dig or plug a hole, is indicated by <var>d</var>
      &equals; <var>m</var> modulo 8.
      The neighboring cells designated by <var>d</var> are
      shown in the table to the right.
    </p>
    <p>
      Samurai can move to or dig/plug a hole in one of four
      neighboring cells.  Thus <var>d</var> above must be even.  A
      play plans of a samurai is called <em>invalid</em> if it is
      neither a non-negative even number less than or equal to 22 nor
      &minus;1.
    </p>
    <p>
      Dog cannot dig or plug a hole.
      A play plan of a dog less than &minus;1 or greater than 7
      is <em>invalid.</em>
    </p>
    <p>
      Invalid play plans are treated the same as &minus;1.  Not only
      the action of the agent becomes &minus;1, but also the play
      plan recorded in the game state information, described below,
      becomes &minus;1 <a href="#invalid plan">[1]</a>.
    </p>
    <p>
      On the other hand, if a play plan cannot be carried out because
      of cell states and/or positions and moves of agents, the plans
      are <em>inoperable.</em>
    </p>
    <p>
      Moving to, or trying to dig or plug a hole outside of the field
      is inoperable.
      Digging a hole in a cell already with a hole or plugging a
      non-existent hole is inoperable.
      Moving to or digging/plugging a hole in a cell where another
      agent is in at the start of a step is also inoperable.
    <p>
      When two or more agents plan to move to the same cell in the
      same step, all such moves are inoperable.
      Digging a hole in a cell to which another agent moves to in the
      same step is inoperable.
      Digging a hole in a cell can be carried out, however, when two
      or more agents plan to move to the cell and their moves are
      inoperable.
    </p>
    <p>
      The action taken for an inoperable plan also becomes &minus;1,
      but, unlike invalid plans, the play plan is recorded in the game
      state information as it is.
    </p>
    <h3>Game State Information</h3>
    <p>
      The game state information sent from the game management system to
      the player processes at the beginning of each step contains the
      following items, in this order.
      <ul>
	<li>
	  The agent ID of the agent controlled by the player
	  process receiving the information.
	  0 for one of the samurai, 1 for its opponent samurai,
	  2 for the friend dog of the samurai numbered 0,
	  and 3 for the opponent dog.
	</li>
	<li>
	  Field size, that is, the number of cells in one side of the
	  field (integer).
	</li>
	<li>
	  Current game step number (integer).
	  The step number starts with 0.
	</li>
	<li>Maximum number of game steps (integer).</li>
	<li>
	  List of positions of cells with holes.
	</li>
	<li>
	  List of buried treasures already known to all the agents.
	  Treasures already excavated are not in the list.
	</li>
	<li>
	  For a dog agent, list of the buried treasures in eight
	  neighboring cells and not made known to all the agents.
	  For a samurai agent, an empty list.
	</li>
	<li>
	  Positions of the four agents, in the order of agent numbers.
	</li>
	<li>
	  Play plans of the agents in the previous step, in the order
	  of agent numbers.  As stated above, invalid play plans
	  are recorded as &minus;1.  For the first step of a game, all
	  will be &minus;1.
	</li>
	<li>
	  Actions taken by the agents in the previous step, in the
	  order of agent numbers.  For the first step of a game, all
	  will be &minus;1.
	</li>
	<li>
	  Scores, that are, the total amount of treasure already dug
	  out by the previous step (two integers).  The score of the
	  team of agents 0 and 2 comes first, followed by that of the
	  opponent team.
	</li>
	<li>
	  The total amount of treasure not excavated yet (an integer).
	</li>
	<li>
	  <a href="#timeLimit">Think time</a> left (an integer in milliseconds).
	</li>
      </ul>
    </p>
    <p>
      All the items in the game state information are given as
      integers.  A newline is placed between the items in the itemized
      list above, and when two or more integers in an item, they are
      separated by a space.  A newline follows the last item.
    </p>
    <p>
      All the items describes as <em>lists</em> above start with the
      number of items in the list (an integer).  For an empty list, it
      is 0.  Descriptions of items in the list, if any, follow it.
      Each item may consist of one or more integers.
    </p>
    <p>
      Positions of cells are represented by two integers,
      meaning the x- and y-coordinates of the cell.
      The coordinate values are non-negative integers less than the field size.
    </p>
    <p>
      Buried treasures are represented by three integers.
      The first two of them are the coordinates of the cell the treasure
      is buried in, and the third is the amount of the treasure,
      which is an even positive integer.
    </p>
    <div class="exampleText">
      <table class="shrunk">
	<tr><td><tt>3</tt></td><td>// Agent ID</td></tr>
	<tr><td><tt>10</tt></td><td>// Field size</td></tr>
	<tr><td><tt>1</tt></td><td>// Step number</td></tr>
	<tr><td><tt>100</tt></td><td>// Max. number of steps</td></tr>
	<tr><td><tt>6 5 1 7 3 7 0 8 1 6 0 5 2</tt></td>
	  <td>// Cells with holes</td></tr>
	<tr><td><tt>1 6 6 6</tt></td><td>// Known treasure</td></tr>
	<tr><td><tt>1 2 7 8</tt></td><td>// Hidden treasure detected</td></tr>
	<tr><td><tt>9 6 2 4 5 3 1 6</tt></td><td>// Agent positions</td></tr>
	<tr><td><tt>0 0 7 7</tt></td><td>// Play plans</td></tr>
	<tr><td><tt>0 0 7 7</tt></td><td>// Actions taken in prev. step</td></tr>
	<tr><td><tt>0 0</tt></td><td>// Scores</td></tr>
	<tr><td><tt>50</tt></td><td>// Remaining treasure</td></tr>
	<tr><td><tt>299941</tt></td><td>// Think time left</td></tr>
      </table>
    </div>
    <p>
      An example of game state information is shown in the figure on
      the right.  The notes beginning with "//" are for explanation
      here and are not actually sent to player processes.
      <ul>
	<li>
	  This information is sent to for player ID 3, the dog of one team.
	</li>
	<li>
	  The field consists of ten by ten cells.
	</li>
	<li>
	  The game step number is 1.
	</li>
	<li>
	  The maximum number of steps is 100 in this game.
	</li>
	<li>
	  There are 6 cells with a hole in them, located at
	  coordinates (5, 1), (7, 3), (7, 0), (8, 1), (6, 0), and (5, 2).
	</li>
	<li>
	  There is one publicly known buried treasure at (6, 6) with
	  the amount of 6.
	</li>
	<li>
	  The dog agent this information is sent detected hidden
	  treasure at (2, 7) of the amount of 8.
	</li>
	<li>
	  The four agents are at (9, 6), (2, 4), (5, 3), and (1, 6).
	</li>
	<li>
	  The play plans of the agents in the previous step were 0, 0,
	  7, and 7.
	</li>
	<li>
	  The actions taken by the agents in the previous step were 0,
	  0, 7, and 7, that is, all the plans were carried out as
	  specified.
	</li>
	<li>
	  No treasure has been dug out yet.
	</li>
	<li>
	  The total amount treasure yet to be dug out is 50.
	</li>
	<li>
	  The think time left for this agent is 299941 msec.
	</li>
      </ul>
    </p>
    <h3>Play Plans</h3>
    <p>
      In response to the game state information received,
      the player program should send a play plan
      for the correspondent agent.
      The play plan is an integer with the meaning described above.
      A newline should follow the play plan.
    </p>

    <h3 id="timeLimit">Think Time Limit</h3>
    <p>
      A limit is set on the total think time of player processes.
      The think time is the period of time between when the game
      state information is sent to the player process and when its
      response, a play plan, is received by the game management system.
      Note that it is wallclock time rather than CPU time.
      The think time of each step is accumulated and the limit is set on
      the total.
    </p>
    <p>
      The think time limit is set for each of the player processes;
      think times of the samurai and the dog of the same team are
      accumulated independently.
    </p>
    <p>
      When this time limit is exceeded, the player process is assumed to
      respond with &minus;1 (stay in the same position) for all the
      remaining steps.
    </p>
    <p>
      The value of the think time limit is given for each game.
    </p>

    <h2>Match</h2>
    <p>
      One match between two teams consists of two games with the
      same initial configuration except that the initial positions of
      the agents are swapped between two teams.
      The result of the match is judged by the total amounts of
      treasure dug out in two games.
    </p>
    <hr>
    <ul class="footnotes">
      <li id="invalid plan">
	Because invalid play plans recorded in the game state information
	would allow information exchange between agents.
      </li>
    </p>
  </body>
</html>