The Team
--------
Otaniemi Lisp User Team
* Lasse Rasinen    (lrasinen@iki.fi)
* Sampo Smolander  (sampo.smolander@helsinki.fi)
* Antti Rasinen    (ars@iki.fi)
* Antti Sykri     (sykari@iki.fi)

All the team members are students at the Helsinki University of
Technology in Finland.

(The team wishes their mail addresses be kept off any web pages,
 as spamming is a major problem these days.)

Lasse was the primary coder and Sampo did lot of the thinking work. The
Anttis had a smaller role than the first two members of the team due to
time constraints. They concentrated on support and helpful hints.

We have included a JPG image of Lasse and Sampo (L to R).
The Anttis were not available for the picture, sorry.

The Program
-----------
Named "Karhu" (Finnish; "Bear"), the software is implemented using ANSI
Common Lisp, and developed and targeted specifically for the CMU Common
Lisp (for system-dependant parts)

The software uses small shell scripts to start the compile process and
running the program.


Strategy
--------

The program algorithm is quite simple. The robot isn't particulary
aggressive, and pushes other robots only if they stand in the way or have
all the remaining packages in the game. During more peaceful times our
robot assigns a score for its targets by their weight and distance on the map.

If the robot isn't carrying anything, it will seek the best package or
homebase using this algorithm. For those packages we know nothing about,
we keep an estimate, based on earlier information about packages/bases.

If the package is dropped, we check whether there was another bot nearby.
If this is the case, the package was most likely dropped by pushing, and
we reduce the package's interest factor only slightly. This is done
every time the package is dropped; if there is a push-pick-drop war
around the package, it becomes less interesting to us.

However, if there was no-one nearby, we assume the package was delivered,
and therefore it gets a very low interest factor. These interest factors
allow the robot to consider more lucrative options.

Finally, if the robot is carrying something, it will assign a score to the
packages it is carrying (based again on the distance and weight) and
will deliver the closest one. Therefore the algorithm is greedy.
It may also deviate from its course to pick up a nice package that it
passes by, if it is near enough and small enough.

The greediness of the robot is also evident in the pickup algorithm. The
robot always tries to pick up the largest possible package that fits, then
the next largest package that fits, etc.

The routes are searched using the industry standard A* algorithm. Since it
is hazardous to go near the water, squares near the water have a higher
cost than normal squares.

If there are no packages or homebases to check, the program starts chasing
other players in short bursts of activity. Having found one

Technical side
--------------
Lots of hash tables, lists, if clauses, loops, etc.
The code is not the cleanest in the world.

File by file overview:
* astar.lisp
  - The A* algorithm, implementations both for local searching and large scale
   searching. Local searching is used when chasing
* communication.lisp
  - The code that reads standard input (ie. the network) and
    converts the flat text to Lisp structures
* compile.lisp, compile-impl.lisp
  - A lightweight mechanism to take care of in what orders the
   files will be compiled and loaded. 
* game.lisp
  - Takes the Lisp structures generated in communication.lisp
    and uses them to update the world-view.
* homebases.lisp
  - Data structure and helper functions to manipulate homebases
* main.lisp
  - Sets up the connection to the server, reads initial information
    and loops around the strategy selector/implementor.
    The latter two are heavily intertwined.
* packages.lisp
  - Data structure and helper functions to manipulate packages
* robots.lisp
  - Data structure <blah blah blah> manipulate robots
* strategy.lisp
  - The scoring functions, target selection and assorted
    helper functions
* variables.lisp
  - Some of the data is kept in global parameters, as there's no use
    to pass the world map from function to function, just if someone
    found it useful.

The parameters are passed through environment variables. This is a kludge:
When the bit in question was written, thex CMUCL manual happened to be open
on the page where environment variables were described ;)

The Compile Process
-------------------
The Lisp files are first compiled to so called FASL files, with
the extension x86f. These are akin to .o files in the C world.

These are then loaded into a Lisp image, which is then dumped
to the disk for faster startup.

Upon startup, the core file is loaded and the program can start.


Flaws
-----
The greedy package pick-up algorithm is vulnerable to a "Hansel and Gretel" 
attack:

- Leave bedcrums (large packages) near water (marked x)
- Lurk on the spot marked y (There is land underneath)
- When our bot goes past y, move behind it
- Surprise the bot, currently at x, completely unawares.

~~~y~~
....x~
~~~~~~

Of course, our tactic relies on the fact that other robots aren't evil
enough to set traps to others ;)

The robot may get into a war over one package. We blame the other guy for
its unsocial behaviour ;)

Netcat
------
The netcat software is responsible for changing the boring problem of
network communication to simple reading and writing to stdin/stdout.

The netcat software is freeware (according to its Freshmeat page anyway)
and has been slightly modified (the define HAVE_BIND was taken out) to
make sure it compiles everywhere.

Note: This is not written by the team, but adapted for service in this
contest. The original author is "hobbit@atstake.com".
