IPSJ Programming Contest Committee
This document gives the rules of the SamurAI Dig Here 2020 game, played in the programming contest SamurAI Coding 2020-21 organized by Information Processing Society of Japan.
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.
The game field has a square shape, divided into small squares called cells 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 the maximum is twenty.
The figure to the right is a bird’s eye view of the square game field from a diagonal direction.
Both teams have two agents each, one samurai and one dog.
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.
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.
In one step of a game, a dog agent can move to one of the eight neighboring cells, that is, those cell that share one or two corners with the cell the dog is in. Samurai agents can move to any of the eight neighboring cells in the very first step of a game and steps immediately following one taking a rest, but in other steps, they can move only to one of the four neighboring cells, that are, those cells that share an edge, and diagonal moves to other four cells are not possible. They can also stay in the cell they are in.
When planned plays are not viable, for example, when two or more agents are instructed to move to the same cell, none of the agents can make their moves and all such agents are kept in their original positions. Details are described in the section Viability Judgment Procedure below.
Some of the cells in the field may have a hole 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 neighboring cells. Samurai can also dig new holes in one of the neighboring cells. The cell to dig/plug a hole can be any of the eight neighboring cells in a step immediately taking a rest; otherwise the target cell is limited to one of 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.
No holes are in the cells where agents are initially in.
Some of the cells in the field may have buried treasure 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, and the total of the buried treasure does not exceed 109.
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 not 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 all the other agents. Not only the colleague samurai but also the opponent samurai and the opponent dog hear the bark.
Treasures are not buried in the initial positions of agents nor in the cells with holes.
A game is played in a step-wise manner. When a game step starts, all the agents make their play plans of the step simultaneously. The play plans are checked their validity and also collated to detect conflicts between them, resulting in a set of actions the agents can actually take. The actions are then carried out and the field state is updated.
Game steps are repeated until the predefined maximum number of steps are played or all the buried treasures have been excavated.
The contestant should provide a player program for controlling two agents, a samurai and a dog, belonging to the team.
The game management system starts two player processes 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.
The player processes have no direct communication paths between them; the only communication possible is with the game management system.
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.
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.
The play plans are the plans of agents' plays sent by the player programs, and the actions are the plays actually taken by the agents decided by the game management system after validity and conflict checks.
Play plans are called invalid if the plan can be judged to be impossible with the state of the field. Play plans that might have been possible only considering the state of the field, but have been made impossible because of conflicts with moves of other agents are called not viable. For example, if an agent plans to move to a cell with a hole in it, the plan is invalid. On the other hand, if two agents' play plans tell to move to the same cell, their plans conflict with each other and thus are not viable.
Play plans are not carried out when they are invalid or not viable. The difference is that invalid play plans are treated the same as a play plan specifying to take a rest. Valid but not viable play plans are recorded as they are in the play plan items in the game state information sent to the agents in the next step, while an invalid play plan is recorded as taking a rest. This prevents information exchange between agents by specifying an invalid plan. This also enables the samurai's moves to or digs/plugs in the diagonally neighboring cells in the directly following step, the same as taking a rest is specified.
Each of play plans and actions is represented as an integer m (-1 ≤ m ≤ 23), meaning the following.
Dogs cannot dig or plug a hole. A play plan of a dog less than −1 or greater than 7 is invalid.
Moving to, or trying to dig or plug a hole outside of the field, digging a hole in a cell already with a hole or plugging a non-existent hole, and moving to or digging/plugging a hole in a cell where another agent is in at the start of a step are all invalid.
Valid play plans can be judged not viable due to conflicts with other agents' play plans. Details are described in the next section.
Play plans are judged invalid, viable, or not viable according to the following procedure, applied in this order.
Assume that agents are positioned as shown in the figure to the right and the following play plans are indicated.
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.
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.
All the items describes as lists 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.
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.
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.
|3||// Agent ID|
|10||// Field size|
|1||// Step number|
|100||// Max. number of steps|
|6 5 1 7 3 7 0 8 1 6 0 5 2||// Cells with holes|
|1 6 6 6||// Known treasure|
|1 2 7 8||// Hidden treasure detected|
|9 6 2 4 5 3 1 6||// Agent positions|
|0 0 7 7||// Play plans|
|0 0 7 7||// Actions taken in prev. step|
|0 0||// Scores|
|50||// Remaining treasure|
|299941||// Think time left|
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.
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.
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.
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.
When this time limit is exceeded, the player process is assumed to respond with −1 (take a rest) for all the remaining steps.
The value of the think time limit is given for each game.
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.