What is this?
-------------

A submission, written in Perl, to the ICFP 2002 Programming Contest,
developed by Joerg Rathlev <joerg@joergrathlev.de>.

See http://icfpcontest.cse.ogi.edu/ for more information about the
contest.


How good is the player?
-----------------------

Well, at least it doesn't crash that much. :-)

The player has a good pathfining algorithm and a not-quite-optimal
algorithm for deciding which packets to pick up, so it should perform
reasonably well in single player games.

In multiplayer games, it doesn't really have a good strategy for
deciding how much to bid, and where to move, in order to avoid getting
pushed by other robots.  It's quite likely that in maps with lots of
water tiles, other players will have no problems pushing this player's
robot into the water.  The player doesn't have any randomness in its
behavior (except when it doesn't know what to do next), so especially
when playing against itself, the robots will often keep pushing each
other again and again because they both want to do exactly the same
thing.


Algorithms and strategy used by the player
------------------------------------------

The player uses a very simple strategy to control the robot, based on
the following goals (ordered by priority):
1. survive
2. deliver packets
3. pick up packets
4. move to a packet's destination (when carrying packets)
5. move to a homebase

To survive, the player uses two tactics: if it is at a tile which is
next to a water tile, and there is an opponent that might push the
player's robot into the water, it will make a high bid, trying to
escape.  It will prefer to continue it's pre-calculated path, however,
if that would put the robot on a tile where it were threatened by
another robot, it will attempt to push away the adjacent robot
instead.

The second survival tactic used is that if the robot is supposed to
move, but it would be threatened on the destination tile, it makes a
somewhat lower bid to increase the chance that the other robot moves
first.

The player never attempts to deliberately push other robots into the
water.

To deliver packets, the player will drop packets whenever the robot
arrives at their destination.

To pick up packets, whenever the robot is on a tile where packets are
available, it will try to pick up as many packets as possible.  The
most useful packets are picked up first, where usefulness is increased
by a high weight (i.e. resulting in a high score when delivered) and
decreased by a distant destination (i.e. resulting in higher delivery
costs).  The algorithm is however a greedy one, so while it will
prefer more useful packets, it will not find the best combination of
packets to pick up.

When the robot cannot pick up or deliver any packets, it will move.
When it is carrying packets, it will move to the nearest destination
for delivery (note that this is not a very good strategy if it is
carrying only one packet and standing right next to a homebase),
otherwise, it will move to the nearest homebase.  If the robot is
standing at a homebase and there are no packets to pick up, the
homebase is removed from the map and replaced with an open space tile
because no new packets will appear anyway (other robots might drop
packets, but then they also might do that on any other tile).

If the robot doesn't carry anything and there are no homebases left,
it just moves around randomly.  This is really stupid, but
unfortunately I didn't have time to write a better algorithm :-(

The pathfinding algorithm is an A* algorithm, the costs of moving to a
tile depend on the number of other players in the game, the more other
players there are, the more expensive moving close to the water
becomes.  When there are no other players, all open spaces / homebases
have the same cost.
