I participated in the coding world championships, or Hello World Open, 2014. The challenge was to write an artificial intelligence for a slot-car racing game.
I wrote my bot in Haskell, and managed to rank 11 out of 856 competitors in the first qualification round, and 78 out of 203 in the second qualification round.
Read on for some general thoughts and a bit of analysis on the algorithms my bot used.
Thoughts on the competition
I’m quite happy with my placement in the competition, as I figured if I manage to reach top 100 that ought to be pretty good, as I haven’t done a whole lot of AI and there were a lot of really smart people participating.
From a technical point of view, the competition worked quite well. I don’t recall there having been many technical hiccups beyond some initial slowness with the test servers. Although some mentioned the tech specs did change along the way, it never presented a big problem for me at least, as any changes were announced by email and were quite minor for the most part. The addition of the turbo was perhaps the largest change to which people had to adapt unexpectedly.
Something I would have personally enjoyed more was a wider variety of tactics. In the simulation there were relatively few choices to make beyond changing lane, adjusting speed and using the turbo. Even lane changes were only possible to do at predefined points in the track. This seemed to turn the competition into a reverse-engineering competition rather than coding, as the best way to win was to be the absolute fastest bot on the track. Thus people with good understanding of physics, math and the formulas and algorithms involved, had a significant edge over other competitors.
As none of the formulas used to calculate things were given out, the person who was able to most accurately reverse-engineer them would be able to go fastest around the track. Therefore it did not seem to be so much about your ability to write code, but your ability to collect statistics and analyze the statistics to come up with the formulas for the physics.
However, coming up with an easy to pick up, yet deep enough to have enough challenge, simulation for a competition like that is probably very difficult. If the game had been more involved (perhaps without the going-on-rails aspect), it could have made the whole system so much more complex that it would have been too hard for many to compete, and the required server infrastructure for the competition could have been much harder (and costlier) to maintain.
It would also be very difficult to predict beforehand what would happen in the actual competition, especially as this was the first large-scale competition the organizers held in this format.
All that being said, I think the competition was still very interesting and fun, and I’m definitely planning on participating next year if they decide to hold another competition.
Overall approaches I used for my bot
My initial approach was to build a bot which would try to learn the track by driving around it and collecting data. Typically what this meant was the bot would drive around at a certain speed until it crashed, and then flagged that location for lower speed. Next time around, it would reduce speed. If it still crashed, it would reduce speed even further. Repeat until it no longer crashed.
However, it became apparent that this would not work. In the qualifications there would be only a short amount of time to drive around the track before the race, and this approach took way too long. Even though I had to come up with a different approach, this hadn’t been a complete waste. I had been able to collect data and information on the physics, which helped in understanding the game better.
The approach used by the fastest bots was based on the actual physics of the game. The devs had reverse-engineered the physics and written algorithms that would attempt to predict the maximum speed the car could take through a certain section of the track. This worked extremely well for many, but personally I lacked the full understanding of the physics involved and I wasn’t able to come up with a working model.
As I wasn’t able to build a physics model from the game, I was messing around with a more reactive approach where the bot would attempt to do some estimation on the speeds it could take, and then react dynamically to things like slip angle and such. Although I had a crude method to do this, it wasn’t very effective. Thankfully I got a lot of help from spion, who came up with a method to use a PID controller -style approach to regulating the bot’s speed during cornering. He also came up with a better algorithm for estimating the maximum speed for a corner.
Some other things I experimented with before the qualification rounds was using the turbo to ram other cars off the track. As a joke, I called this feature “rambo”, a portmanteau of ramming and turbo. Rambo was very effective at knocking out cars, but more often than actually being useful and knocking someone off the track, it would cause my own car to go off the track due to too much speed. In the end, I decided to disable the feature, as it was mostly up to luck whether it was good or not.
It’s kind of sad that many of the bots did not seem to utilize turbo in this way. Knocking off cars was quite fun when it actually managed to do that during test races, but perhaps it was too difficult to effectively regulate when this would occur without risking running off the track, which in most cases would have caused you to lose several positions in the race.
Was Haskell a good choice?
There weren’t a lot of Haskell bots. I think mine was the best performing bot written in Haskell, but I’m not entirely sure as they didn’t release a lot of programming language statistics at least not yet.
I didn’t encounter any problems with the choice, which really goes on with my experience with Haskell in general – despite what many seem to think, the language is perfectly suitable for pretty much any task you would use any other language for.
What did happen was some benefits from the choice. The bot was very stable. If I had written it in say JavaScript, it would probably have ended up being much more unstable. Despite this, if I hadn’t been able to use Haskell, JavaScript would probably have been my second choice of language though.
The full bot code is available on Github, under jhartikainen/hwo2014bot. I did clean it up a little, but it’s probably still kinda messy. It’s built on top of the skeleton application provided by the organizers, I might have done things a bit differently myself. I didn’t end up changing the base much, so it was a quite good skeleton nevertheless.
Some interesting bits in the code:
I used an infinite list for some calculations. Although I’ve used Haskell for a variety of things, I hadn’t really written algorithms like this much, so I had some concerns on whether this made any sense or not. Essentially the code was lazily generating an infinite list of results for some calculations, but apparently this is a perfectly valid approach to use in Haskell.
The relevant function for that is Brain.hs line 314. The iterate function is generating the infinite list.
The Haskell application was mainly built on top of the BotM monad transformer. This kept the bot configurations in a Reader monad (as they never changed during runtime) and the dynamic bot state in a State monad. This worked pretty well and there were no immutability issues or anything involved. The only “problem” if you can call it that was that the Brain data type which held all the state kept growing and growing. I don’t think there’s really any way out of it, since all that data would need to be carried around anyway.
Some of the bloat for the Brain type would probably have been possible to avoid by using different representations for the data that was carried around. There were some things that had to be tracked due to it being difficult to otherwise perform calculations, and some of them probably would have made sense to be stored with another data type.
Since the code was using a lot of state, I decided to try using the lens package with it. It’s weird how it actually makes the code read like code in some imperative language where you have mutable variables. This is especially visible in some of the message handling code, where they mostly assign some values to the state using lens.
In closing
Overall this was a pretty fun experience. Congratulations to the winners and thanks to the organizers. I definitely intend to participate again next year!