
   $Revision: 1.1.1.1 $, $Date: 2002/08/30 19:36:39 $

                 ICFP 2002 Programming Contest Challenge Task

Document Version 1

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

     * ICFP 2002 Programming Contest Challenge Task
          + [1]The world
          + [2]The robots
               o [3]Pushing and Bidding 
          + [4]The packages
     * [5]The game protocol
          + [6]Initialization
               o [7]Transmitting the board
               o [8]Transmitting the configuration
          + [9]Game play
               o [10]Transmitting the list of packages
               o [11]Commands for the robots
               o [12]Server's reply to commands
               o [13]The end of the game
     * [14]Scoring

     [15]Physical resource limitations

     [16]Changes since version 1

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 maximum carrying capacity, and a
   sum of money for bidding.

   The player controls the robot by issuing commands.
     * The Move command moves the robot to an adjacent square, in one of
       the four directions north, east, south or west.
     * The 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 when the
       robot gets to execute its command (for example if it got pushed).
     * The Drop command is used to drop packages. Packages are always
       dropped.

   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 [17]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.

The packages

   Every package has a unique identifier, a weight and a destination. If
   a robot dies, its packages are lost.

                               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 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 string 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
     * a unique identifier,
     * the maximum carrying capacity,
     * the initial amount of money (used for bidding)

   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:
     * Move direction
     * Pick list of package IDs
     * Drop list of package IDs

     * A direction is one of: N E S W
     * A package ID is an integer
     * A list of package IDs consists of integers separated by space

   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.

  Server's reply to commands

   At the end of each turn the server will send an individualized reply
   to each player showing what happened to all robots during the turn.

   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:
     * N The robot moved north.
     * S The robot moved south.
     * E The robot moved east.
     * W The robot moved west.
     * P id The robot picked up package with id id.
     * D id The robot dropped package with id id.
     * X num The robots x-coordinate is set to num.
     * Y num The robots y-coordinate is set to num.

   Example:

   #2 E #1 N Robot 2 moved east and robot 1 moved north.
   #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. 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 robot which
   wins the most games.

   Some games will have a single robot others will have multiple robots.
   The sizes of the maps may vary between 1x1 and 1000x1000 squares. Here
   are [18]some sample maps. The number of packages will vary between 1
   and 10,000. The maximum amount of money robots will 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...

                         Physical resource limitations

   A player should use a reasonable amount of resources. Aim for:
     * not use more than 64 MB of memory at any point in a game,
     * not consume more than 1 CPU second per move on average in a game
       on our 1.5GHz Pentium 4 processor.

                            Changes since version 1

   None (yet).
     _________________________________________________________________

   [19]ICFP Programming Contest 2002

References

   1. file://localhost/tmp/task.html#world
   2. file://localhost/tmp/task.html#robots
   3. file://localhost/tmp/task.html#pushing
   4. file://localhost/tmp/task.html#packages
   5. file://localhost/tmp/task.html#gameprotocol
   6. file://localhost/tmp/task.html#initializaton
   7. file://localhost/tmp/task.html#transmittingboard
   8. file://localhost/tmp/task.html#transmittingconfiguration
   9. file://localhost/tmp/task.html#gameplay
  10. file://localhost/tmp/task.html#transmittingpackages
  11. file://localhost/tmp/task.html#commands
  12. file://localhost/tmp/task.html#reply
  13. file://localhost/tmp/task.html#endofgame
  14. file://localhost/tmp/task.html#scoring
  15. file://localhost/tmp/task.html#physical
  16. file://localhost/tmp/task.html#changes
  17. file://localhost/tmp/task.html#transmittingboard
  18. http://icfpcontest.cse.ogi.edu/maps.html
  19. http://icfpcontest.cse.ogi.edu/
