Recently I was fortunate enough to be brought aboard a student-driven game design project by Jake Ross and some other students who are members of Texas A&M’s Visualization Lab (you should really check them out, they send a lot of animators to studios like Pixar and Dreamworks). Together, with a core team of about 8, we spent a year building an iPad game in our free time and named it Titan Ph.D. I built the AI (artificial intelligence), and this is the first of a 3-post series on how I did it.
Computers can seem pretty dumb sometimes, can’t they? Why can’t they just learn how to do things like we do? Learning comes so effortlessly to us humans; we don’t even remember learning something as extraordinarily complicated as speech – it just sort of happened. If I showed you 10 pictures, 5 with cats in them and 5 without (actually this is the internet, so 11 of those 10 pictures would have cats in them, but bear with me) you could easily identify which images contained cats. Because computers are basically math machines, unless you can very precisely define what a cat is, then a computer will not be very good at such a task. That’s where neural networks come in – what if we could simulate a human brain? And like a human brain, what if we could purpose our simulation to only look at cats?
Imagine you have a point, a single little dot on a piece of paper. What’s the quickest way to go from that point to another point on the piece of paper? You (the reader) sigh and answer ”A straight line” because it’s completely obvious; even first graders know that. Now let’s imagine you have an open parking lot, with a human standing in it. What’s the quickest way for the human to get from one side of the parking lot to the other? The answer is again obvious to you, so you get a little annoyed and half-shout ”A straight-line again, duh!”. Okay, okay, enough toss-up questions. Now what if I gave you a car in the parking lot and asked you what was the quickest way for that car to get into a parking spot? Hmm, a little harder now.
You can’t say a straight line because what if the car isn’t facing directly towards the parking space? Cars don’t just slide horizontally and then turn in place, so planning for them seems to be a lot more difficult than for a human. But! We can make planning for a car just about as easy as for a human if we consider the car to be a special type of car we’ll call a Dubin’s Car. Interested in knowing how? Then read on!
In August 2009, Sergey Karakovskiy and Julian Togelius held a competition on behalf of the ICE-GIC (IEEE Consumer Electronics Society Games Innovation Conference) for contestants to build a soft-bot that played Super Mario.
The Super Mario Engine they used was a modified version of one built in Java by the one and only Markus Persson , a.k.a. “Notch” of Minecraft fame. The Engine is named Infinite Mario Bros., and is still playable online for free. Entrants into the competition had to build an agent who would tell the engine Mario’s next move every 40 milliseconds.
The competition was held in 2009, and again in 2010. Robin Baumgarten won this competition with his bot, AStarAgent, both years. I stumbled upon this competition in late August 2010 and was immediately intrigued. I had wanted to build an agent that played a known game –any game, really—for some time. A modern first person shooter like Halo or RTS like Starcraft would be mind-blowing, exciting, and most of all, recognizable to family and friends.
For a fun little final project in my AI course, the class was split into teams that were to take a Lego Mindstorms NXT 2.0 robot kit and build a creative robot to do…something! Really, it was a cool way to finish a really interesting course. There were robots that could walk to a bucket and sort colored balls, one to traverse a maze, one that transforms from a rover into a walker…. and ours, which solves Rubik’s Cubes.
I won’t question your adeptness at a favorite childhood game, but my bot Herbert will. Myself and a few other guys developed Herbert for our final project in AI class, and he is frustratingly unbeatable. After a game or two against him, you might consider an early retirement from the Connect 4 world. [Update 3/3/2012 I have uploaded Herbert for you to download and play against. See details at bottom of this post for more]