technology from back to front

ICFP Contest 2009

What is fast becoming a regular fixture in my diary is my entry with a few friends into the ICFP Programming Contest each year. This is a three day programming competition in which you can write in any language to solve the problems given. The competition is still in progress, though my team’s decided to stop — we’ve had enough fun for one year, and there’s only so far you can go with very little sleep and shockingly poor maths — but we’ve done much better than last year, learning from our previous mistakes…

Last year, the competition was to write a controller for a Martian Robot. You were given the simulator and the scenario files for it and had to write a controller to direct it to avoid boulders, rocks, and 7-fingered martians. Control was a little tricky, our path finding frequently never terminated fast enough and we never actually figured out how hard it was to direct the Robot until about an hour before the finish — and yes, we went the whole 72 hour distance then. We were totally wiped out, realised we’d solved the wrong question, or at least not spotted where the difficulty lay until it was far far too late and ended up doing very badly — somewhere below 250th position. In the course of the three days we wrote about 9000 lines of Haskell and almost every commit comment was either a single letter or a curse of some sort. A friend of ours wrote a very simple controller (in C++) and did very much better than us.

We learnt several things from that experience. One was to really think about the problem and work out where the difficulties lie before getting bogged down in a broken implementation. The other was the value of writing tools — namely visualisers so that you could see what’s going on. A picture really does paint a thousand words, and Haskell has some nice GTK+/Cairo bindings so it’s pretty easy to knock out a good visualiser. Last year, because communication with the simulator was via network sockets, we also used this to dump out data to be visualised. We had to run the simulator in real time (though some teams did work out how to hack it so it would run much much faster) and so it made sense to run the visualiser in real time too — it was pretty cool to watch what our rover was doing and we also dumped out our graph for route finding which we overlaid too. However, because it was so timing sensitive, we found that our rover behaved differently if it was running with the visualiser or not — the extra cost of dumping out debug information altered its behaviour!

This year, the task involved moving satellites between different orbits. We were given only the compiled scenarios, and a spec of the VM which they were to run on. So step one was implementing the VM. This was pretty straight forward, though we immediately spotted we want this to run as fast as possible because a valid solution could be up to 3,000,000 “seconds” long and there’s no way we’re sitting around for that! — 3,000,000 seconds is 833 hours which is about 11.5 times longer than the whole competition was due to last! So I pretty much treated Haskell as C, got out the bit masks, and had the whole thing running in my CPU cache (ok, I have a 12MB L3 cache, so it’s not as impressive as it sounds!). I was quite pleased — with a bit of maths I worked out I was spending about 250 CPU cycles per VM instruction — about 8 million instructions per second. We were getting through the 3,000,000 “seconds” in under 2 minutes and this was clearly very usable. We were also dumping out to a file all sorts of debug information which we would later parse and build a visualiser for. Sadly, that same friend I mentioned earlier also wrote a VM in C++ and got to about 35 CPU cycles per VM instruction. Still, within a factor of 10 is quite good for Haskell — both of us used pretty much every trick we knew to make it go fast. I guess there’s still work to be done for the GHC developers!

Next task was writing the visualiser. Again, Haskell, GTK+/Cairo, a nice slider to allow us to step through each frame, plotting the output, and a textual dump of the information we capture in each frame. Also, quick navigation to the next “interesting” event — eg when we fire thrusters — searching for events like these amongst 3 million frames is a little frustrating, so quickly being able to jump computationally was a good extra feature. It suddenly became very cool to rapidly step through every 100 frames and get a primitive video of our satellite moving about, and gravity playing havoc with its every move!

And now to the problem itself. There’s a thing called a Hohmann Transfer which allows you to change between different orbits using two burns. You use one burn to push you out of your current orbit and to go into an elliptical orbit, and then 180° later you do another burn which puts you back into your target circular orbit. Task one was simply doing this maths, getting it right, and going from one circular orbit to another. Sometimes the orbit would be further out, sometimes further in. This was reasonably straight forward.

The second task was not only changing orbits, but also meeting up with another satellite in the target orbit. You had to stay within 1km of the target satellite for 900 seconds to pass. So, between two steps, you could use your position and your target’s position to calculate enough information to solve the necessary equations. You would know how long you needed to sleep for (i.e. carry on in the current orbit), how much you needed to burn, how long the transfer between orbits would take, and what the final burn would be.

In this task, there were four scenarios. Three of them we got quite quickly, but the fourth eluded us for a long time (in fact, although we got a solution, we don’t have a single piece of code that can do all four tasks, so it doesn’t really count). The problem with the fourth scenario is that the target satellite is a VERY long way out. Our equations are for continuous maths, but the simulator is discrete. So when we calculate exactly how long to sleep for (which is the number of VM steps, or “seconds” to sleep for), that value has a fraction, but you can’t sleep for fractions. So this means that you either burn a bit early, or a bit late, or you try to spread the burn over two steps. Either way, you burn at the wrong time, and so you arrive in the wrong place (exactly the same rounding issue happens with the transfer time (i.e. the amount of time to spend in the elliptical orbit), and so you either try to come out of the elliptical orbit early or late). For close to earth, as three of the four problems were, this inaccuracy doesn’t matter too much — the perimeter of the circles you’re landing on is small enough that if you’re out by a few fractions of degrees, you’re still in real terms close enough to the target satellite to be within 1km and score points. When you’re going a long way from the earth, these few fractions of degrees correspond to a long distance — the closest I could reliably get was just under 10km away from the target. Not good enough.

We tried going too far out and ahead of the target, and then trying again in the hope that it’d be easier to be more accurate if we were closer to the target to start with. We tried going just not far enough and behind the target and trying again, all to no avail. The problem there is that when you’re a long way out, each step of the simulator counts for several thousand miles, and if your window of when you need to fire your thruster to hit the target is quite small, you can frequently miss it between two steps. We actually discovered that it was much much better to try going out, if you miss it, come all the way back in to, say an orbit of 1.025 * EarthRadius and then going back out — this was faster and gave us many more attempts, and as we were orbiting the Earth so quickly, we could afford to wait until the stars were in alignment, a particular simulator step showed us that we were really really close to the ideal time to fire, and to try again. Sadly, again due to the differences between the continuous maths we were doing and the discrete maths of the simulator, after a few outs and ins, we noticed we were very much not in a circular orbit around Earth when we thought we were. Rounding errors had rather crept up on us.

So that is where we got stuck. We spent many hours arguing about maths and angles. About the only maths we didn’t argue about was vectors, but then we’d previously (re-)written (several dozen) vector maths libraries as a result of games we’ve written (or attempted) so those libraries are reasonably solid. The visualiser worked really really well — our friend with the uber-fast C++ VM didn’t have one, and it showed, when he was staring at columns of numbers not understanding what his satellite was doing. Really, we needed to throw all our maths away, and implement an iterative solver — effectively cloning the maths the simulator was doing. Only this way could we be accurate enough. But neither of us have maths strong enough to solve those equations, or at least enough clue to work out where to start. Nevertheless, at one point, we were in 52nd position, which is a stunning improvement from last year, though we have dropped back a bit now as other teams are still working on it. It finishes at 7pm BST today, though we’re not going to do any further work on it.

For those interested, the 3rd part of the question was the same as the 2nd part — i.e. meet up with a different satellite, except that now the target satellite can be in an elliptical orbit, and you can start in an elliptical orbit too. The fourth part was to add in an element of AI so that you can visit several randomly positioned satellites, stopping at a special refueling satellite if necessary to refill, and doing it as fast as possible. Oh yes, and the Moon makes an appearance in the fourth part, adding much more fun to your equations (figure-of-eight orbits around the Earth and Moon anyone?!).

We took it at a much more relaxed pace this year, I even had to go out to play in a concert at one point, though it was mercifully brief, but had more fun than last year, did better, and didn’t make anywhere near as spectacular mistakes!

by
matthew
on
29/06/09
 
 


× 6 = eighteen

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us