HWO2014: the speed of the electric sheep

Did you know that the best opportunity for having fun with AI programming and wasting two weeks of your time comes from Finland? Reaktor and Supercell organized a programming competition, the coding world championships as they called it. The goal was to build an AI for a racing car. The cars were simple slot car like things controlled by only the throttle and lane switching commands. The car with the best programmed computer driver would eventually win lots of fame and some fortune (5000€).

All the races were visualized in the official website

The prophecy

I’m a pretty competitive person and also fond of artificial intelligence challenges. I was not supposed to have any extra time during the two weeks coding period of the competition, yet I saw no choice but to participate. Also, I was lucky to get Antti Ajanki to join my team. He is a cool guy and a D.Sc. in machine learning, basically a perfect match for the journey. Our team got the name Electric Sheep. We stole it from Philip K. Dick, the idea being that the electric sheep from the dreams of the androids had provided us the vision of a perfect algorithm.

The name of our team was Electric Sheep

When we saw the technical rules we dwelled in optimism. We were anticipating a harder challenge, cars with the steering and whatnot. Now the competition looked just like a somewhat difficult physics exercise. What else could there be with the simple slot cars than reverse engineering the physics of the game? How hard could that be? And if that failed for some reason, our pet weapon, machine learning, should save us in the tough spots.

Making it worth the vision

With our approach the solution was basically always in two parts: first we had to figure out what was the system behind the game that made the cars act like they did. We collected data from the races and plotted it. After this wasn’t enough, we made educated guesses based on the real world physics and tried to gain more insight from there. In the second phase, after we had acquired the understanding of the physics, we needed to apply the knowledge for finding the most optimal instructions for the car. This was done preferably with math and, only when that didn’t work, with programming. Math can give direct answers in places where a recursive algorithm might simply be too slow.

We used mainly matplotlib Python library for plotting the data

We started with plotting the speed, acceleration and throttle on the straights. With a little trial and error we managed to get this part right already on the first day. We managed to do the math and in a couple of days we had a constant time algorithm that told us the maximum throttle in any position on a straight, given that we knew which speed was the optimal in the start of the next curve.

The curves were obviously a lot harder than the straights. Finding the right physics model took much longer this time.  For applying the physics, mathematical solution suddenly looked difficult if not impossible and we chose to start with coding first. At this point, I thought we were in a good position and had a slim but a realistic chance to make it to the top.

Never trust a prophet who says baa

After Antti got the algorithm to calculate few steps ahead, we were in for a surprise. The results were all wrong – apparently the physics model we had predicted was somehow incorrect anyway. And we were already getting tight on time! One option could have been to create a machine learning model for the physics, the second best thing after the exact solution. We didn’t know, however, how perfectly we could even utilize it. After analyzing the options, we knew that we had just lost the race. The tasks ahead would require our best effort, all the remaining time sanctioned for the competition and some luck. We were not up for that and decided to option out for a compromise, the creation of a simple model that would predict the maximum constant speed for the curves.

The visualization of the insufficiency of our bot

The Futu way of racing

Generally within Futurice the competition got a decent level of notion.  We were eight Futu teams participating, plus one that had a former Futuricean member. Sometimes it scares me how hard it is to escape this company. Crafty people from one of our teams from Tampere quickly built a standings table for the nine Futurice teams and a chat channel was opened for the company level discussion.

Minimalistic standings table for showing the results of the teams from Futurice

Of course we had to organize few internal competitions, which we called the FutuRaces. I felt embarrassed taking part: our car was still really broken. Such ego issues! Anyhow, it was time to make the bot to be able to join the races of multiple cars and after the quick fixes we were set to go. It turned out that no one was yet that ready. One particular bot was driving really slowly and most of the cars aligned behind it, unable to perform the bypass. Then there were those that kept on crashing. All in all, it was huge fun and even useful for the competition, helping us to realize issues with the bypassing. For the final solution, I implemented heuristics that made the bot to prefer the lanes without slow traffic.

The moment of truth

When the qualification day came, I wasn’t expecting much. After all, we had been only middle class or slightly above in the FutuRaces, and we understood all too well how far from optimal our bot was. The qualifications were like mini seasons. They consisted from multiple competitions in totally new tracks. A competition first had the time trial for determining the starting order. After that, the real race could begin. It was always a new ten rounds long fierce battle where driving too fast and getting off the track was penalized heavily.

Then, I guess we got slightly lucky. The new tracks were tricky and other bots started flying off the track one after another. Our secret sauce was Antti’s implementation of auto-correction for the maximum curve speed: if we flew off the track, car would learn to avoid flying the next time. With this jewel and the mediocre general speed, we actually ended up being the best team from Futurice and 29th from Europe & Africa region! A respectable result but still not what we were after.

Antti and I had a solid retro and the project got a proper closure. We didn’t quite become the champions of the world, but at least we learned a lot and had some good times.

The competition was organized extremely well. Awesome job, Reaktor and Supercell! There were some minor issues with the templates and some of our clean code purists ended up rewriting it all from the scratch. For me though, Python not being my most familiar language, the template seemed just fine. I’m already looking forward to the next year’s competition. We now know, that to reach the absolute world class, we need even more than the speed of the electric sheep.