"Not Last Place": A War Story

25 Sep 2014 by Adam Allevato

Originally published September 25, 2014.

I’m not a computer scientist. I’m just a mechanical engineer.

But I’m a very competitive mechanical engineer. When I took mechatronics, my goal was “to make it onto the professor’s list of Top 10 Projects of All Time.” In our fiendishly difficult materials science course, my goal was “to get 100% on a test, because no one ever has before.”

So when I heard about the Windward Studios Code War, where we could pit our programming skills against other students, my reaction was: “sign me up for that thing ASAP.” I didn’t even consider the fact that we would be going up against computer science majors, people with far more programming knowledge than myself. If there was going to be a competition, I was going to be part of it. Oh, it was an AI competition? Even better. I had read a book on that. No problem.

As our team (myself, Kyle Smith, and Parker Malenke) did a bit of preparation, we realized that our competition had taken semester-long classes on optimization and algorithms. This was a bit of a buzzkill for us. “Here’s our plan,” we told ourselves reassuringly, “we have no CS majors on our team, and so we’re just going to consider it a victory if we don’t end up in last place.” We thought that maybe, with some luck, we could beat out one team.

And so we headed to the Colorado State University Computer Science building on a Saturday morning. Little did we know what the day had in store for us. All we brought was our laptops and the reassuring thought that even though we were going to be hopelessly lost, we weren’t CS majors, so it didn’t matter how we did.

It’s difficult to describe a hackathon (or, in this case, a code war) to people who aren’t nerds. Imagine a small startup company atmosphere, but with 10 times the urgency, and infused with the excitement of a sports tournament. In our case, it really did feel like a war. Windward made a very fun, challenging problem for us to solve (navigating a mythical city road map to transport passengers and earn points), and our AI had to choose an approach, anticipate our opponents, and generally beat our opponents’ AIs in each battle until the war had been won and the game was over.

We quickly realized that there were two main problems to solve: pathfinding and decision making. Our car had to be able to get around the city efficiently, but it also had to be able to choose which passenger to transport, and when. As it turned out, decision making was the easy part for our team. Because of our limited programming experience, we jumped straight in to give ourselves as much time as possible to get the code right. This meant that instead of trying to optimize a strategy, we just put some “magic constants” into our code to weight different goals differently.

As we continued testing throughout the day, we tweaked our constants for the best performance we could muster.

For example, our AI ended up being twice as likely to pursue a passenger that would reward us 3x the points. Why not 3x as likely? We came to the conclusion that other cars would go for those passengers, and rather than fight with 7 other taxis over a single passenger, we could just go for the smaller rewards unhindered. This is just one example of the many tweaks we made.

The pathfinding algorithm for our AI quickly became the nastiest part of the day. After happily wolfing down free pizza provided by Morgan Stanley (take note of that, it will be important later), the three of us sat down and stared at our A* algorithm for a solid 3 hours until it was working correctly. This was where our programming prowess really hit a wall, but in the end we persevered and got a good (if not great) pathing system. When combined with our fine-tuned decision engine, we had created quite a powerful AI. But we didn’t even realize it yet.

Finally we began matching our AI against others. It was time to see some results, and try to “not get last place.” But as we watched the little cars zip around the little city on the giant projector screen, we realized that we weren’t failing. We were winning. In fact, we were dominating. We won our first test heat without breaking a sweat, by a huge point margin. Parker, Kyle and I looked at each other, unable to believe that our AI, the spawn of a mechanical engineer, a biomedical engineer, and a biochemist, had just handily beaten two systems that had been created by computer science majors.

We hesitantly returned to our desk and tweaked some more constants to get everything we could out of our algorithm, and then it was time for the official CSU match. We shouted with glee as we won round after round, and glowed with exuberance when we emerged victorious. We had beaten not just every team at CSU, but had also surpassed our wildest expectations.

When our AI got 5th place nationally, we hardly cared that we were only a few points from winning a prize, having already progressed so far beyond what we thought possible. My confidence was boosted so much that I decided to apply for a job at Morgan Stanley (after they had graciously provided us with free pizza). Three months later I was in New York City programming software for financial analysts.

The Code War turned me into a real, dyed-in-the-wool programmer, and showed me what I was capable of. Now I know that I may just be an engineer, but I can write code with the computer scientists.

This was an entry in the Windward Studios Great Game Giveaway.