
	     ICFP 2002 Programming Contest Challenge Task


Team name:        MxG&B  (Mexican Girls & Boys)
Program name:     PLTbot
Language used:    PLT Scheme (coast to coast)

Contact:          Francisco Solsona <solsona@acm.org>

Team Members:

	Karla Ramrez <karla@ciencias.unam.mx>
	Ivan Hernndez <ivanx@ciencias.unam.mx>
	Arturo Vzquez <vaz@ciencias.unam.mx>
	Francisco Solsona <solsona@ciencias.unam.mx>



Our try at solving the challenge task is based on a set of techniques
to improve the performance:

   1.  World representation: 

   the world is stored as association lists of obstacles stored in a
   vector.
   
   we maintain separate structures for homebases, packages, and
   robots.  Some are simple lists, some are sets, some are a mixture
   of association lists with sets.  And other auxiliar structures to
   aid in the decision making process, such as a fixed length (during
   a simple expansion of possible paths) list to avoid going in
   cycles.

   
   2. Game strategy:

   Ala alpha-beta, minimax kind of thing, we try to maximize the
   points our robot can make.  given the complexity and mixture of our
   structures it is hard to pin-point the places where this is try to
   be accomplished, but here is pretty much what is going on:

      - After initialization, for every turn our Robot does:

        * updates its vision of the world based on the information
          returned by the server.  Among other things, this allow us
          to keep accurate information on possible `new' homebases
          (locations at which there was a Drop).

	* We evaluate our current position in the following order:

	    - Danger situation (we don't want, and will not let other
          robots push us into water for instance).
	    - Drop situation (we value, of course, more than most
          other moves, except the ones in which our live depend, to
          drop a package if we can)
	    - Pick situation (picking eventually becomes dropping, you
          do the math :)
	    - Move situation (this is the less profitable, and by far
          de hardest one to make... so we try, hard, really hard, to
          make as `informed' a decision as we can.)

	* We select our move, we place a bidding on it and return to
          the server... and we loop.

   Due to the partial information at every moment, and the size, and
   complexity of the world, and our robot fellowships we try to be as
   careful as we can while making a decision.  Danger, drop, and pick
   situations are complex, but can be readily maximize in almost any
   given situation.  Moves (and robot hunting to make them drop a
   package) are a whole different history:

      - To move effectively, we recognize the following two phases:

	 Exploration: we do some sort of alpha-beta (BFS) exploration
   from our current position, and go pruning branches that lead to a
   dead end, or other not so nice situations.  We don't have a hard
   depth to go to, actually, we do explore as far as our money can
   take us!

   We tried several approaches, but we could always find a "kind" of
   world that would fool the working, of our exploration, and value
   assessment routines.

   During this exploration we keep, a structure with the nodes we have
   visited, and penalize a route if its to come repeating nodes along
   the way.

         Decision making: once we have a set of paths that look
   promising, we go from end to origin passing the news, updating the
   value (assigning blame) of a given node, until we have a value for
   the immediate neighboring tiles, and then, we aim for the highest
   one.

   This blame assignment is non-standard, that takes into
   consideration the following:

   (positive) the Hamming distance (disregarding obstacles) to the
   actual target from the new position, and our current one.  This is
   a "rough" approximation of how close we are getting.

   (positive) the Promise gain we'll get (delivering a package (or in
   other words earning some point) or picking a juicy package).  This
   is multiplied by some factors, that make clearer the difference
   between several reachable targets.

   (negative) the cost to pursue this path (length of the path, depth
   of the search, etc.)


   3. The bid

   Once we have assigned a value to a given action (drop, pick, move),
   we put our money where our mouthalgorithm is, and place the
   bid.


   4. Conclusions

   We will write a more detailed specification later, once we get some
   sleep.  :-)

   Anyway, we want to congratulate the organizers for their great job,
   and the 72hours of fun.

Thanks!