$Revision: 1.50 $, $Date: 2002/09/03 05:29:06 $
http://icfpcontest.cse.ogi.edu/task.html
The challenge is to implement a program that acts as a player in a multi-player robot game. Contributed programs will play against each other in a tournament, which will determine the winner of the programming contest.
In the game, simulated robots deliver packages in a simulated world. Each player controls one robot. The simulation proceeds in discrete steps. At every step, each robot executes one command, which may move the robot, pick up packages or drop packages. Robots win points for successfully delivering packages to their destination. The winner of a game is the robot who finishes the game with the most points (but see the tournament rules later).
Home bases are where packages are initially located. All robots compete for the same set of packages.
Coordinates on the board are pairs of integers, ranging from (1,1) to (width, height), where (1,1) is the southwest corner of the board.
The player controls the robot by issuing commands.
Move
command moves the robot to an adjacent square,
in one of the four directions north, east, south or west.
Pick
command is used to pick packages. Packages
are initially available from home bases.
Packages may not be picked up if they are too heavy, or if there are no
packages available.
Drop
command is used to drop packages.
Packages are always dropped.
Robots may push each other. Robot 1
is said to push
robot 2
if 1
tries to move onto 2
's
location. Typically that will result in 2
moving to the
adjacent square in the direction it was pushed. If this happens
to be a lethal square 2
will die. If it happens to be
a wall neither robot will move, but 2
is still considered
to be pushed. Pushing is transitive in the sense that if
1
pushes 2
, that may result in 2
pushing 3
. Both 2
and 3
are
considered to have been pushed, and (again) the robots will only move
if all of them can move.
When a robot is pushed it gets rebooted. While rebooting no command can be executed. A reboot lasts until the end of the current turn. As a result if a robot gets pushed before executing its command, the robot will not execute its command.
When a robot is pushed it drops a random package if it has at least one and then is moved to its new location (if possible).
Example: Assume there are robots 1,2,3
located as in
the Before column below. 1
wants to move
east and 2
wants to move north. 3
will
not move in the scenarios.
The table illustrates different scenarios. # is a wall, .
is empty space (see the transmitting the board)
Before | If 1 moves first
| If 2 moves first
|
... 1.. .2. |
.1. .2. ... |
... .12 ... |
... .1. .2. |
... .21 ... |
.1. .2. ... |
.#. .1. .2. |
.#. .21 ... |
.#. .1. .2. |
... .3. .1. .2. |
... .3. .21 ... |
.3. .1. .2. ... |
Bids are used to control the order of moves. Every command has a bid, and the commands are executed in order of decreasing bids. Commands with the same bid are executed in a random order.
Bids may be positive or negative, but not 0. Positive bids increase the chance of a robot executing its command before other robots, while a negative bid increases the chance of its command being executed after other robots. Both of those are useful in certain situations. The cost of a bid is its absolute value. For example bidding -50 will still decrease the robot's balance by 50 units of money.
If a robot did not execute its command because it was rebooting the bid still is deducted from its money.
Bidding more than the robot's budget results in its death. For every command a robot must spend at least 1 unit of money.
Example: If a robot starts with 1000 units of money, and its policy is to spend 1 unit per command, it can participate in at most 1000 turns of the game, as on the 1001st first move it will over-spend and die.
A robot that dies disappear from the game.
'\n'
(ASCII code 10).
Integers are also sent as
text, for example the number 1765 is sent as 4 consecutive characters:
'1', '7', '6', '5'.
The clients and server communicate with each other via TCP/IP sockets. The host name where the server is located and the port number on which it is listening for connections will be provided as the first two command line arguments of a client.
The game proceeds in two phases: an initialization phase, and the actual game play.
The dimensions are two integers, the first one indicating the width (i.e. the number of columns), and the second one the height (i.e. the number of rows) on the board.
Once the dimensions are transmitted, the server sends one line for every row of the board. The first line corresponds to the row with vertical coordinate 1, i.e. the board is sent from south to north.
Every row consists of a number of characters, indicating the type of tile at the corresponding position in the row. The first character corresponds to horizontal position 1, i.e. each row is sent from west to east. This is the encoding for the different tile types:
plain | . (a dot) |
lethal (water) | ~ (a tilde) |
impassable (wall) | # (a hash) |
home base | @ (an at) |
Example: Here is a (very small) example board:
7 5 ..@.... ....... ##.~~~~ ...~~~~ .......This map has a home base (@) at position (3,1). Note that since row 1 is transmitted first, the north direction of the board is down.
Example: Here is an example of the initialization information send by the server to a client who happens to be controlling robot 3, who can carry at most 25 units of weight, and starts with 1000 units of money at location (1,1). In this particular game there was also robot 2 at location (2,1) and a robot 1 at location (1,2).
7 5 ..@.... ....... ##.~~~~ ...~~~~ ....... 3 25 1000 #2 X 2 Y 1 #1 X 1 Y 2 #3 X 1 Y 1
Note that the position of the players are transmitted in standard server response line, described below.
Example: If there are 2 packages, package 17 to be delivered to position (133,28) weighing 50 units, and package 89 to be delivered to position (11,57) weighing 78 units, the server will send the following line:
17 133 28 50 89 11 57 78
Note, that if there are no packages at a location the server will send just a blank line.
Example: Here are some example commands:
1 Move N
200 Pick 17 89
29 Move W
-8 Move S
57 Drop 11
1 Drop
Any malformed command will kill the robot.
The format of the response is list of robot updates. Each robot update is of the form #robot_id and then the actions in the order they happened. A robot is listed if and only if it was alive at the beginning of the turn. The following actions are possible:
Example:
#2 E #3 #1 N | Robot 2 moved east, robot 1 moved north, and robot 3 did not move at all. |
#1 W #2 P 0 P 1 | Robot 2 picked up package 0 and 1 and robot 1 moved west. |
#2 E #1 W E | Robot 2 moved east and robot 1 moved west and then east (i.e. robot 1 was pushed). |
#1 X 1 Y 1 E #2 E | Robot 2 moved east and robot 1 appeared at location (1,1) and moved east. |
Some games will have a single robot others will have multiple robots. Robots should strive to get the highest score, irregardless of the presence of other robots. The sizes of the maps may vary between 1x1 and 1000x1000 squares. Here are some sample maps. The number of packages will vary between 1 and 10,000. The maximum amount of money robots might be given is 1,000,000,000. The weight of a package will be between 1 and 1,000,000,000. The maximum carrying capacity a robot might be given is 1,000,000,000.
Throughout the competition participants are encouraged to submit maps to the judges. Judges could be impressed by interesting maps... Mail them to icfp-judges@cse.ogi.edu with the words My maps in the subject line.