I’ve been meaning to write a post about the 2015 Simulated Car Racing Championships but I’m still a bit burned out on the topic. The reason is that I am this year’s bronze medalist. Yea for me. Although that earned me 100 Australian dollars I did sink a lot of time and energy into this project. It had its ups and downs. It was definitely a keen learning experience and a formidable challenge. After placing in the middle of the pack in 2013 I had already started to assiduously prepare for 2014… which was the year they stopped having the competition. Grr. As if to mess with me, they started it up again for Summer 2015 under different management. Scrambling to get my entry ready in time, I gave it a go.
Basically this competition involves writing software to control a simulated race car and then racing it. Even though the car and its track environment are simulated, I think the contest would be more correctly called the Simulated Car Driver Racing Championships. In 2013, I created a very nice framework for people who wanted to enter this competition using Python. This was called SnakeOil. This approach does a good job of getting a car around the track and providing a great starting point to dream up fancy driving mechanics. This is great if you like Python, but don’t be discouraged with C or other languages (even Java) if that’s what you prefer. I chose Python because it was what I could easily use to come up with a lot of new ideas quickly with minimal fuss, especially when it comes to the inordinate amount of text processing required to handle the server messages. However, this may have been a wrong approach. Here is my important conclusion: I now believe almost all success in this sport comes from optimization. Perhaps this isn’t any surprise to the computer science researchers who participate in AI (optimization) conferences which feature these contests, but it was a learning moment for me to realize this the hard way.
My bot was, I believe, the most complex of the bunch. This sounds overly grand, but here’s the thing - it doesn’t much matter and can even be counter-productive to have such a baroque system. For example, I spent a lot of time perfecting realistic clutch action on my bot; on the other hand, Autopia, the perennial grand champion (which aspirants should study closely), never touched the clutch. When I realized this I thought, how can this be? This brilliant winner is essentially stupid! The answer is that in what little it did implement, it didn’t make any goofy mistakes and its creator optimized the hell out of all coefficients. Actually, that was my second year strategy. Autopia only has a dozen or so optimized coefficients. I had 57.
This brings us to the real work of the project. You have your bot and you’ve carefully separated out all of the tweakable values into a "parameter file" or some such package. Now you need to divine optimal parameters. Like my ancestors, I used a process of mutation and subsequent mating of the "genomes" of my most successful specimens (simplified, top performer got 100 chances to mate, 2nd got 99, etc). My big innovation to genetic algorithms was encoding not just the value of the parameter in question, but also encoding in the genome the order of magnitude by which it was safe to mutate this value. This, in theory, allowed values that should only be adjusted very finely to encode that information in with the genetic parameters themselves. While I am sort of timidly proposing that this may be an effective way to implement genetic algorithms, I’m not sure my project constituted a serious enough test of that conjecture. It was not a complete failure and it still seems like a neat idea. For all we know, biological genetics works that way, although I am definitely not seriously conjecturing that.
I downloaded the entire corpus of about six thousand tracks, which was quite tricky. Don’t ask how that trade secret works. In any optimization problem you can’t help but train "for the exam" to some extent. This means maximal diversity in tracks is good. This year’s competition found my car at a loss when races were run on classes of tracks I’d never heard of and, even after requesting more information, still know nothing about. Not much to be done about that I’m afraid.
Once you have diverse track environments and a way to mutate your bot’s genome, you must simulate typical life cycles to elicit a representative level of fitness. Here’s where the creative Python approach starts to break down. Python allows you to quickly and creatively add very fancy (i.e. human inspired) logic in a mostly reliable bug-free way. Python can easily keep up with the performance demands at a human scale. But to effectively breed winners you must condense time so that your army of possible contenders are racing billions of test kms orders of magnitude faster than humans can observe them. Suddenly Python finds itself in danger of being the weak link in the chain. It can be done, but I now think it is ultimately a slightly suboptimal choice.
I may have addressed this problem more seriously, but just getting this whole simulation environment to run smoothly in a non-interactive way is a huge tedious distraction. (My notes on such things.) My advice is to study the other entries. If you really want to win, just implement Autopia with your own optimized parameters. And good luck because Autopia did a damn good job of it. If you just want to play around with a bot that drives very strategically and uses a lot of fancy interesting human inspired logic my SnakeOil is a good platform to explore. Also keep an eye on curious things like Ahoora. In 2013, this bot was panned as last place and near worthless as a competitor. For this reason I completely overlooked it. Then one day wanting to see what an "ordinary" entry looked like against mine, I set up a race and was amazed to see last place Ahoora crush not just my humble entry but Autopia as well. Crush. I tried some more tracks and it was completely and universally dominant. Confused, I then set out to recreate the 2013 competition and observe for myself this enigmatic entry. Only then did I discover that it could not drive with noisy sensors, one of the two required regimes of the contest. While noisy sensors were a minor inconvenience to Autopia and most other bots, including mine, for some reason Ahoora was nearly completely paralyzed by unreliable inputs. The lesson is clear that the competitions feature more than a bit of pure luck and many great ideas and much good work is missed by the competition format. An example is having the bot figure out the general coefficient of friction of the track as it proceeds and then dynamically adopting a parameter set bred for those conditions. I think Ahoora did something like that and in hindsight its the best idea I did not think to implement.
I found the actual competition to often be a bit arbitrary and frustrating. Not knowing what type of tracks to expect was definitely a severe limitation to non-luck-based approaches. What the competition did do was provide a structured deadline for getting something working reasonably well. The greatest pleasure I took from this experience was when I would test the best of a new generation of cars against the best competitors and the race was close. Mostly my cars didn’t beat the best but sometimes they did. But when they were perfectly matched, it was quite a thrilling spectator sport to watch the battle and think to myself, wow, I made your mind.