Egér a Marson - ICFP contest 2008 (v1.01)

We were a team of two, let's call them B and H (this document is written by H). It was our second ICFP contest. There were 2 more people interested, but they were abroad during the contest or something like that. The name "Egér a Marson" was suggested by B after reading the task description; it means "Mouse on Mars" in hungarian, and was the title of an animated cartoon from our childhood (see on youtube; the music is absolutely great!).

We used Haskell, Python and a few lines of plain C. H basically forced the use of Haskell (the letters are a coincidence); while Haskell was all good and very suitable for the contest, it meant that H wrote most of the actual code, as B was not comfortable enough around Haskell. Well, maybe next year (hmm, we thought the same last year...).

The contest started at 9 PM, Friday local time (GMT+2); B arrived at H's flat about half an hour before, we went to shopping (beers and energy drinks and snacks) and got a the LAN working in that 30 minutes. I felt quite lucky as all the languages we planned to possibly use were on the LiveCD, and I had a spare machine with almost the same processor the organizers' test config had, and it even had Linux installed. In the end, it didn't matter much; the LiveCD crashed with 50% probability, had no graphics when worked, the GHC on the LiveCD missed the extralibs (fair enough: a full GHC install would require ~350 megabytes, half of a CD), and the spare machine ran Windows and a music player most of the time :)

Unfortunately, H had some other event to attend in the middle of the contest, so the compromise was that we suspend working from ~2 PM Saturday until Sunday evening. I think we did quite well in the light of this; however at the end we really missed that 24 hours. Other than that, we pulled two all-nighters (H actually slept only once from Friday midday to Monday evening), consuming way too much of these energy drink type stuff (coffee and beers, too). After quickly implementing the network protocol (import Network ; import Text.ParserCombinators.Parsec), an OpenGL visualisation and a manual rover control, we fancied the idea of submitting a 18 hours lightning entry, but we didn't succeed in that.

We tried some trivial obstacle-avoiding thing like most of the teams. This forced us to realize that we need some kind of path-finding algorithm; but we didn't bother to look up A* and all these on the net, as my naive conception of these was that they all work on a regular grid, which seemed the wrong thing to do. Also it was obvious that we should use some spatial data structure, but these are somewhat nontrivial to implement, and the situtation was uncommon enought that we didn't find any ready-to-use libraries immediately; so we postponed the problem. In the end it looked that the 10^3 craters/boulders (the organizers told us we shouldn't expect much more) are just within the limits of the bruteforce solutions we cooked up (well, at least on my more modern CPU; see also below...). Later a friend suggested using shortest path in a weighted graph stuff, but at that time we had working greedy heuristics and also I couldn't see how to get a graph out of the map.

So instead all the "correct way" scientific solution, in the lack of more well-formed ideas, we decided to do some kind of heuristics. One nice idea come from discussing things on paper, when a drawing looked like the solar system (so we have SolarSystem.hs in the code :). The following screenshot should illustrate the point:

the mighty "solar system"

which is that we look in all direction near the rover (or any other point on the map, actually), and find intervals of angles which are free of obstacles (within some radius). So H started to implement this a few hours before the mid-contest break. If my memories are correct, we also had some crude and buggy estimation of the hidden acceleration/braking parameteres by this time. I planned to add the rotational acceleration and weed out the bugs later, but it never happened.

(The acceleration measurement was actually pretty funny. I wrote some code, first it was numerically unstable but when I corrected it, it still gave very wrong numbers. Then some sudden struck of half-formed idea came, and I inserted a factor of two somewhere, and magically I got good answers. Then I realized that the reason was that the physical time resolution of the server was ~10 times better than the telemetry time resolution of the rover, so there is a crude numerical integration going between the two.)

So after 17 hours, just before the middle-contest break, we had working protocol, visualisation (the Linux sample server's visualisation did not work for us, and the OSX sample server was uploaded much later), manual control, random test map generation written in Python by B, some buggy and stupid control code, buggy estimation of acceleration and braking, finally an interesting idea and a half-baked untested implementation of it.

Fast-forward to Sunday evening (note that the contest ended on Monday 9 PM in local time, so we still had 24 hours). B is in some serious highway traffic jam somewhere, and H is fighting with some serious hangover. Not very good :).

By the time B arrived, H managed to get the "solar system" picture seen above, and was quite happy with it. Then some serious hacking followed to exclude the gaps which are too small for the rover to fit (it was not totally trivial, as the same angle gap can be big enough far from the rover, but too small near, however, it is possible that it is not yet a gap near, because the occluding objects are between the two). Then the implementation of some heuristic path-finding followed, which was planned to be global but actually was greedy (and that's a good thing, as the corresponding global algorithm would require the lifetime of the universe to run...). Somewhere at this point I ran into something which is quite possibly a GHC bug (programs with trivially the same semantics produced very different time behaviours); I will try and see if I can reproduce that.

(note that this screenshot was made after the contest, and code is quite different - actually worse - than what we had at that time; it can serve as an illustration however)

This heuristics performed surprisingly well on the test maps after some tweaking (all the decisions are based on horribly wrong and impossible-to-tune weighted sums of ad-hoc "goodness" functions, but hey, it worked on the test maps :); but it was clear the we need more precise local control. So H implemented a physics simulation based on the estimated parameters and 10 ms time resolution the organizers told us not to rely on, and B fell asleep. This was the only non-Haskell code in the submitted entry (written in C instead), as Haskell is pretty bad in this type of numerical simulation problems. Fortunately, the Haskell FFI (foreign function interface) is very good and relatively easy to use (also it helped a lot that I used it before a few times :).

(Actually, first I went for an exact solution, as that would be faster, but Maple gave the solution of the corresponding differential equation in an integral form, and judging from the shape it was probably not exactly integrable, so a direct simulation was both easier and faster to do than numerically integrate the solution).

This local control overtook from the heuristics if it predicted that we will crash into something in the near future; in that case, it tried all the 3x5=15 possible control states, extrapolated from each of these, and choose one out these. (The martians are ignored. We planned to include them, figured that it would be easy to do, so postponed it until the end where we had no time to do it). This 'precise local control + heuristic "global" control' combination work very well, depending on the impossible-to-tune parameters of course. H was quite happy, apart from the already realized fact that the present goodness function are impossible to get right. Also made lots of small and ad-hoc finetuning, like slowing down before the home base to avoid overshooting (which happened before).

Then B woke up, generated some maps where the greedy strategy won't work, and insisted that we had a global a pathfinding algorithm too. And the gates of hell swung wide open... H tried to patch the current code, and realized that his Haskell-fu is good enough to write the most ugly, obfuscated, convoluted and of course impossible-to-maintain mess of code within a pretty large radius circle (in the case we put the sources on the net, don't ever try the look into Strategy.hs, for sake of the well-being of the world, thanks). He also became very irritated in the process (the lack of sleep and too much energy drink didn't help either). The deadline was too close, we were tired, and the code was totally fucked up. Note that we didn't use any kind of version control system, which caused no problems before, but at this time I really wished we used one. While H panicked, B still insisted on a global strategy so we won't get stuck on maze-like maps. There were unpleasant quarrels too, fuelled by all this.

Finally 2 hours before the deadline H decided that first we should upload something, and then we can care about global pathfinding if we still have time. So he patched the code back into a more-or-less working state (which already performed worse than before...). We booted up the Linux on the spare machine, and hoped that what we compile will be binary compatible with the LiveCD environment (as the LiveCD missed the extralibs, we didn't even bother to try to compile with the LiveCD running). This wasn't unreasonable, as GHC linked everything statically (I hoped), and the processor was an AMD Athlon XP 2400+, almost the same the organizers had. And we can still test the binary with the LiveCD. And then the surprise came: The code didn't work! Well, it ran properly, and steered the rover right into the middle of the first big crater... To add insult to injury, the OpenGL visualisation didn't work at all on this Linux environment; so we had no idea what is happening, but it looked like a latency problem (we have seen that before, when we flooded the server with ";" commands). H thought that his bruteforce computations are simply too slow (he used a Macbook for the development, which has a more modern CPU), and B thought it's a network latency problem (the code received the boulder crash messages more than 5 seconds late). So we did two things: put the network communication, local strategy and global strategy into 3 separate threads, and made ad-hoc changes to some parameters which should result in faster computation (and worse control). And it still did not work. Then the idea came that we should try it on B's laptop (which is way more slower than the other two machines), and it worked on that, so after all it was a probably a networking problem.

We managed to submit this crippled and untested (both the ad-hoc parameter changes and the multithreading was untested) version 5 minutes before deadline, but we had much better behaving versions, say 8 hours before the deadline.

Anyway, it was fun (mostly), we learned from it, we did better than last year, and I dare to think that we could put together something pretty good if we had that extra 24 hours in the middle. And of course big thanks to the organizers for putting together this nice contest for us!

update: We were eliminated in the 10th round (out of 11), probably because of the lack of global pathfinding.