Mario AI Competition 110
togelius writes "We're running a competition to see who can program the best AI for a version of Super Mario Bros. It's about deciding what to do at each time step — run, jump, shoot etc. — based on a description of the platforms, items and enemies around Mario. This is hard. It's so hard we believe that some sort of machine learning algorithm will be necessary to reach good playing performance. But really, any approach is fair game. We welcome hard-coded submissions, commercial AI programmers, academics and amateurs alike. Whoever wins, it will be really interesting. The competition is associated with two IEEE conferences, and there are cash prizes available for the best submissions."
This is hard (Score:5, Interesting)
First, I would teach the AI to move around on flat surfaces. Then I would teach it how to navigate over holes. Then I would add pipes and things it would need to jump over. Finally I would add random bricks. These are hard because if you jump underneath them, you might bump your head and change your trajectory.
Secondly I would start adding bad guys. Start with goombas, then add green turtles, then red turtles, then piranha plants, then bullets.
This is hard, the AI will need to learn to recognize certain features of the landscape, which is something humans are really good at doing. It will have to learn things like, "if I stand next to a tube, the piranha plant will not come out." It will have to learn that sometimes a short hop is appropriate, and sometimes a long jump is better. It will have to recognize that if a red turtle is on a ledge, it doesn't need to worry about it falling, and it can run underneath at full speed.
Heh, maybe I'll enter. How hard can it be?
Re:Uhhhh (Score:4, Interesting)
Brute forcing this is not really feasible, but there are probably a large number of states that you can treat as equivalent. For example, you don't care about whether a block is destructible if you are above it, you don't care about the state of any tile under the one you are standing on, and so on.
Re:Shard of glass in my delicious pie! *gruff* (Score:3, Interesting)
This competition is about algorithms. The implementation language is largely irrelevant. Java is far from my favourite language, but it's expressive enough for a project of this nature.
Neat! (Score:2, Interesting)
However, I've yet to see a such a contest in which the successful entries used AI techniques rather than handcoded decision-making. My money says the winners of this will be handcoded and possibly tuned automatically, and not based on neural networks or genetic programming or whatever. I suspect this is true because these games are set up so that the game mechanics and the outlines of good strategy are very intuitive to humans, and so it's most efficient for the human programmer to encode that knowledge into the controller. Then if there's some minor detail that the programmer doesn't know how to optimize, like "what is the exact threshold from which I should switch from strategy X to strategy Y", then that can be found by running a lot of games automatically.
That's how I'll be working, at least; in any case, I don't think I could write a decent learning algorithm for something like this in a month (or probably even given a lot more time).
I hope this isn't considered spam, but those interested in this might like to know about some other programming games I've enjoyed:
http://jrobots.sf.net/ [sf.net] (Java clone of CRobots)
http://robocode.sourceforge.net/ [sourceforge.net] (More complicated version of above)
http://sillysoft.net/ [sillysoft.net] (Risk game that accepts AI plugins)
Just how random is random? (Score:1, Interesting)
Just how random is the 'random' level generator. If the AI is beaten by weaker AI because another team managed to exploit pattens in pseudo-randomness, then your competition results wouldn't really mean anything
2009 Reinforcement Learning Competition (Score:3, Interesting)
We also used Infinite Mario Bros, but combined it with the RL-glue coding framework to make the interface easier. That way, a well-coded agent is automatically compatible with any other domain that is RL-glue compatible.
The prizes were also comparable: ~$450 for the first place team, ~$250 for the second place team.
The results were interesting: far from developing interesting and novel RL algorithms, most competitors used clever feature engineering combined with dimensionality reduction to reduce the full Mario problem to a simpler one that could be solved efficiently using existing RL algorithms that are robust and well understood.
One of the big lessons that we took away from this was that we haven't solved the mechanism design problem of competitions in AI. While Mario sounds like a good "grand challenge" problem for RL / AI, it turns out that simple heuristics work pretty well. I think this is a common problem for most of these competitions -- there's the Trading Agent Competition, there's Netflix, there's the General Game Playing Competition, etc. They all have the same goals, and they all have the same problem: competitors engineer algorithms to solve the competition, not to spur progress in general AI. These games are all a proxy for what we really care about (like the Turing test), and the proxy isn't perfect (like the Turing test).
I think the only way to get around this is to craft a domain that mimics the real world, because then if anyone "solves the competition," you've made progress on what you really care about.
It would be interesting to design a competition with these goals in mind. Maybe an extraordinary complex simulator based on a physics engine (Bullet or Havok) would be a step in the right direction -- different objects with continuous, high-dimensional state spaces and complex material properties (some are soft, some are rigid, some break, etc); interesting physical interactions between objects (collisions, joints, hinges, stacking, breaking, etc.); multiple levels of spatio-temporal abstraction (from low-level motor control to abstract tasks) and a strong vision component. Now that would be a cool competition!
David Wingate
wingated@mit.edu