[2014-05-04] Hello World Open 2014

I had not heard of the Hello World Open coding challenge until I came across a Hacker News post about it. It seemed somewhat similar to the ICFP contests, albeit with much more time available for coding (14 days versus 3 days for the ICFP contests), and therefore for fun. So I decided to take part in it and it did turn out to be fun, though I remained true to form and did not finish coding before the time-limit expired.

The contest involved creating the controlling logic for a slot-car racing against other slot-cars controlled by other teams. The races happened on a number of different tracks. These slot-cars just had a single throttle control for changing their speeds around the track (no braking, no steering, no shifting gears). The tracks varied in structure and the physics of the simulation kept changing across races, even for the same track. The main challenge for a team was to learn the physics of the simulation during a race and to use that to win a race without slipping off the track on bends. Since a slot-car is confined to a lane and cannot switch lanes except in designated places, it becomes difficult for it to overtake competitors and to avoid getting bumped off the track by other cars behind it.

It appears that most teams spent a lot of time trying to figure out the physics of the racing simulation so that they could finish a lap in the shortest time without de-slotting around bends. The main approaches to this problem seemed to be one of the following:

I first tried to reverse-engineer the physical formulas of relevance to the simulation by reading up whatever I could on this topic, including the excellent “The Physics of Racing” series of articles by Brian Beckman. Quite embarrassingly, I did not know what a “slot-car” was (and had not noticed the term in the technical specification) until a few days into the contest and hence was puzzled by the behavior of the car on the track, especially around bends. Even then, it proved quite difficult to reverse-engineer the physics of the simulation to a reasonable degree of accuracy, not helped at all by my tendency to punt on tackling the difficult problems by refactoring code again and again. I tried to write a controller following the old car-racing adage of “slow in, fast out” for tackling corners on the track, but without figuring out the physics, this didn't yield much success.

During the second week of the contest, I decided to try the simple linear regression technique from machine-learning to see if it helped. This decision was driven more by my desire to apply my new-found machine-learning skills from the Coursera Machine Learning course taught by Andrew Ng, rather than its inherent suitability to this task. As it turns out, it was useful - not as accurate as reverse-engineering the physical formulas of relevance to the simulation, but good enough to predict the speed and slippage of the car with a decent margin-of-safety given a particular throttle-power. As I noted earlier, I never actually got around to using the predictions from the derived model to control the car as I ran out of time.

Some of the key machine-learning insights reinforced for me during this process include:

If you are interested in this topic, the paper “A Few Useful Things To Know About Machine Learning” (PDF) by Pedro Domingos is a good read full of practical advice.

I chose C as the implementation language. I had started off with Go, but wasn't very sure how its garbage-collector would behave with lots of tiny objects being created and discarded rapidly, as the controller processed and responded to around 60 messages per second from the server - I didn't want the garbage-collector to pause my program at inappropriate times. The C implementation used cJSON to parse and construct JSON messages used to talk to the server - cJSON is remarkably small, easy to integrate, has a reasonable API and is fairly fast. Given the constraints on response-times, I thought that JSON-processing would be a big overhead, but it turned out that Nagle's Algorithm was a bigger bottleneck - setting TCP_NODELAY fixed the latency caused by this. It was also fairly straightforward to implement linear regression in C, though I really missed the simple and efficient matrix operations provided by GNU Octave.

Some notable things about this contest:

All in all, I enjoyed taking part in this contest and thank the organizers (Reaktor of Finland) for all the fun. I look forward to next year's contest and hope to perform better than this time.

Other Posts from 2014