$Revision: 1.50 $, $Date: 2002/09/03 05:29:06 $

ICFP 2002 Programming Contest Challenge Task

Document Version 3

This document describes the ICFP 2002 Programming Contest Challenge Task. Its home is at 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).

The world

The world is a rectangular area of square tiles. Each tile is either open space, a wall, water or a home base. Robots can walk in open space and on home bases. Walls are impassable. If a robot steps on water, it drowns. The edges of the world behave as if there were walls beyond them.

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 robots

A robot has a unique identifier (a positive integer), a maximum carrying capacity, and a sum of money for bidding.

The player controls the robot by issuing commands.

In each step of the game each robot executes one command. The order in which these commands is executed is important, as robots can push each other.

Pushing and Bidding

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.

The packages

Every package has a unique identifier (a non-negative integer), a weight and a destination. If a robot dies, its packages disappear. Packages disappear when they are delivered to their destination. If a package is dropped at a location different from its destination, it just stays there until someone picks it up.

The game protocol

The protocol works in text mode, using ASCII characters. The server and clients send each other lines of text. We use the UNIX convention of what a line is, i.e. a line is terminated by a single new line character '\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.

Initialization

The initialization phase occurs as soon as a client joins a game. The protocol is as follows:
  1. Client: send the line Player
  2. Server: send board
  3. Server: send player's configuration
  4. Server: send initial server response (with the initial location of all players)

Transmitting the board

The board is transmitted in the following format:
  1. Server: board dimensions
  2. Server: board row 1 ...
  3. Server: ... other rows ...
  4. Server: board row n

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.

Transmitting the configuration

The configuration consists of These are all integers and are sent on one line, separated by spaces, in the above order.

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.

Game play

The game is made up of a number of turns. A turn looks as follows:
  1. Server: a list of packages available at the player's current location
  2. Client: issue a command to the robot
  3. Server: server responds with what happened during the turn
At the beginning of each round the server sends a list of all the packages (if any) available at the player's position. The client is then expected to respond with a command for its robot to execute. The server then says what happened to all robots during the turn.

Transmitting the list of packages

For every available package the server will send 4 integers: the package ID, the horizontal position of its destination, the vertical position of its destination, and the package weight.

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.

Commands for the robots

A command to a robot consists of two parts: the bid and the action. The bid is an integer, the action is one of:

Example: Here are some example commands:
1 Move N
200 Pick 17 89
29 Move W
-8 Move S
57 Drop 11
1 Drop

The package_id list to Pick and Drop can be empty. It is also OK to pick packages which are not there and drop packages which you are not carrying. In both cases the packages that are valid will be dropped or picked.

Any malformed command will kill the robot.

Server's reply to commands

At the end of each turn the server will send each player a reply showing what happened to all robots during the turn. All the players will receive the same information.

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 NRobot 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.

The end of the game

The game ends either when all packages have been delivered or all robots are dead.

Scoring

A correctly delivered package scores the player an amount equal to the weight of the package. Each robot will participate in a number of games. In each game all the robots will be given the same carrying capacity and the same amount of money. The winner of a game is the robot who has the highest score at the end of the game. The winner of the competition is the player with the highest total score over all games.

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.

Physical resource limitations

A player should use a reasonable amount of resources. Aim for:

Changes since version 1


ICFP Programming Contest 2002