This is an outline of the bot that myself and Leon Brocard came up with for the London.pm entry to the ICFP Programming Contest 2002.
Here's the overview, shamelessly stolen from our README, and complete with gratuitous LotR quote:
"Sam sat on the ground and put his head in his hands. 'I wish I had never
come here, and I don't want to see no more magic,' he said, and fell silent."
This is the London.pm entry to the The Fifth ICFP Programming Contest
(http://icfpcontest.cse.ogi.edu/). It's called Marvin.
*** BASICS
Marvin is written in pure Perl 5. It doesn't depend on any non-core modules.
*** HOW DOES IT WORK?
Path-finding:
Marvin implements an iterative solution of the popular A* algorithm.
Package selection:
Marvin uses two techniques to decide which packages to fetch from a base:
- First, choose packages that are all going to the same destination.
- Second, choose packages with lower weights that might not fit our
capacity optimally, rather than filling our capacity completely with
heavier packages. (Which isn't only very hard, but is also not a great
idea in a game with combat - if we're going to drop a package, it makes
sense to drop one weighing a small amount, affecting our points less.)
Combat:
Marvin makes no attempts to engage or avoid combat.
So you want to see how Marvin works but you can't be bothered to download the server and try it yourself? Well, through the wonders of Perl, the Imager module, netpbm, and gifsicle, we can present animated GIFs of Marvin running.
The first movie (11K, 290 frames) shows Marvin's A*-based pathfinding. Marvin starts at the bottom right and attempts to find a path to the "T". We put a 'v' for each location that the path finding algorithm has visited.
The second movie (86K, 296 frames) shows Marvin trundling around towards home bases, picking up packages, going to their destination, dropping them, and starting all over again. Note the score go up when we drop packages and the fact that Marvin can carry more than one package at a time.
In the final movie (168K, 222 frames) I've pitted Marvin against some other bots from the competition: entries by Bernd Paysan, Berkeley State Machines Incorporated and Simon Funk. Marvin is 'M', other robots are 'R'. They have to pick packages up in the middle and deposit them at the bottom left and top right while avoiding the water '~'. Note that when a robot gets bumped it can drop a package which another robot may pick up. Also note that some of the other robots seems to have less effective path finding and that sometimes robots get stuck in a loop. One robot has overbid by the end, run out of fuel and is out of the game. Cute, huh?
Well, poorly. We didn't start work until half way through Saturday; almost a day after the competition started. We didn't get to work on it as much as we'd have liked on Monday, because we were both at work. And we actually went to sleep during the competition, which I'm told is incredibly poor form.
We coded Marvin in Perl, perhaps a controversial choice. We're both Perl coders (and members of Perl Mongers) so it was the obvious choice for us. It was also good for the network and data munging. We did worry about the speed issue, but it turned out not to be a problem at all: we didn't even worry about optimising or caching our path finding.
We read up around the problem and built a client library which encapsulated all the client-server communication and returned changes back to us as data structures. We also built a Curses frontend so that we could check what was going on. Once we had the basic framework, we had the tools to build and test the rest.
Leon found a Java implementation of A* and got to work porting it to Perl, while I wrote up a class to read the map from the server and return a data structure from it - these ended up as Maze::AStar and Maze::Map respectively. In a very short amount of time (around two hours from our start time) we had a decent traversal algorithm going, and moved on to looking at packages.
Here's an overview of how packages in the contest worked. You get told the location of 'home bases' on each map by the server. These may or may not contain package(s). On top of that, robots on the map may drop packages when they're pushed. In both cases, you know where the packages are, and when you're on top of them you know their weight, and the co-ordinates of their destination.
The problems of choosing which packages to pick up from a base are representative of two larger problems, which seem to be the real guts of the competition - the Travelling Salesman and Knapsack problems. Travelling Salesman is involved because the order of which packages you pick up has an effect on the route you're taking, and whether it's an optimal one; how long you stay in the game depends on how well you use your fuel, and so there's a correlation to your score. As each package has a weight, and you have a maximum capacity, the Knapsack problem involves choosing which packages to take to maximise your use of your capacity. Both of these problems are in NP-space, and the differences we see in competition bots will involve different heuristics being used to simplify the problems.
As for Marvin, we went the very simple way. Our choice of which packages to deliver is limited to picking up packages going to the same place if multiple destinations are present in the package pile. In the best case, this involves a number of trips equivalent to the number of destinations in the package pile, rather than equivalent to the number of packages.
Deciding how to fill our capacity with packages bound for the same place was a much harder problem. We looked at using a Monte Carlo Simulation before having an epiphany over what we really wanted from package selection. Here's what we decided:
Having a small number of 'heavy' packages that optimally fill your capacity is not as valuable as having a large number of less heavy packages.
The rationale is that you can get pushed by other robots during the game. When this happens, you drop one random package. We'd rather drop a light package than a heavy one, since the weight is proportional to points.
We also pick up packages we run over while on a route somewhere if we have extra capacity.
Bidding was a late entry in our bot. Marvin bids "1" most of the time. Marvin bids higher when dropping a package on its destination. If (and only if) there's another robot in the four squares surrounding us, we bid to the value of the packages we're carrying. We also bid high if there is water and a robot around us.
If we'd had more time or more people on our team there are a couple of more things we would have added. These include: keeping track of dropped packages, keeping track of home bases with packages, more intelligent pathfinding (avoid water edges or other robots), push robots into the water if we have the chance, minimax searching to guess what robots around us would do, and more. The whole point of Marvin is to be simple, and not waste fuel trying to be clever.
I've been told I didn't make this clear enough. The reason our bot sucks is that we wimped out of the real challenge - working out particularly clever solutions to the two main problems of base-selection and object packing. Another reason is that we just ignore combat completely, and there's plenty of room for strategy; not going near water when there's danger of you being pushed into it, for example, or just avoidance techniques in general.
The code comes in two versions - the light version that was
submitted, and our development version, which
includes a UI. To use the development version, you'll need Perl's Storable
module and Curses wrapper installed. Be warned that they unpack in the
current directory, since that was the judges' preferred archive layout.
If that all sounds like too much work, I
have a screenshot of an
early version of marvin running, and some of the code. In the shot, the
v characters represent A*'s search path, and the P
characters represent the critical path found.
I think that's about everything. Our bot represents a combined number of man-hours of somewhere under 20, so it's well prepared to be beaten by just about everyone. It's been a fun experience all the same.
Chris Ball 2002-09-04 http://printf.net/
