Forgot your password?
typodupeerror
Programming Entertainment Games IT Technology

Mario AI Competition 110

Posted by Soulskill
from the must-be-on-mushrooms-when-you-write-the-code dept.
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 discussion has been archived. No new comments can be posted.

Mario AI Competition

Comments Filter:
  • Uhhhh (Score:1, Redundant)

    by Idiomatick (976696)
    Can I keylog myself beat the whole game on an emulator and submit the log? ... Seems kinda silly having ai for games that have nothing random in it.
    • Re:Uhhhh (Score:4, Informative)

      by Toridas (742267) on Wednesday August 05, 2009 @04:03AM (#28953221)
      If you had read TFA you'd know that they are using the game Infinite Mario Bros, which has randomly generated levels.
      • Re:Uhhhh (Score:4, Interesting)

        by TheRaven64 (641858) on Wednesday August 05, 2009 @07:31AM (#28954755) Journal
        Note, however, that mario levels are composed of blocks of something like 15x20 visible at one time. Each of these has a small number of relevant states (wall, enemy, hazard, tube), let's say 8 possible states. That gives 8^300 possible states for the visible game. From each of these states, you have a small number of options. This means that infinite Mario is really finite Mario with a really large set of levels.

        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.

        • by jerep (794296)

          You dont need Mario to explore every last block in the game, alls you need is for him to finish the level, and if the AI is smart, it will do it without the use of items (stars, mushrooms, etc). You could just use a simple pathfinding algorithm with detection for enemies and obstacles, and let mario complete the entire level while running and stopping only to wait for certain events (such as those stairs moving up or down).

          8^300 states is a lot of data and would never perform well in realtime AI calculation

        • I think exploring some various state machine configurations would help here.
        • Re: (Score:3, Informative)

          Here is one guy doing it. Pretty impressive... http://www.youtube.com/watch?v=0s3d1LfjWCI [youtube.com]
  • by VinylRecords (1292374) on Wednesday August 05, 2009 @04:11AM (#28953283)

    http://tasvideos.org/ [tasvideos.org]

    TAS = Tool Assisted Speed Runs. Basically you program controller inputs (at very slow speeds) and then play them back at 1:1 speeds and you watch a pre-programmed controller run through an entire game as quickly as possible. There are runs for basically most of the more popular NES and SNES games as well as other games. Pretty interesting stuff and usually a daunting task is creating a TAS of a game.

    • Re: (Score:3, Insightful)

      by Sockatume (732728)

      I'm doubt that would count, seeing as you've just got a human doing the decisions. It's "artificial intelligence" not "artificial fingers".

    • True, but TFA states that they are running "with the added benefit of endless random level generation".
  • by BadAnalogyGuy (945258) <BadAnalogyGuy@gmail.com> on Wednesday August 05, 2009 @04:20AM (#28953345)

    500 dollars for the winner, but you are expecting evolutionary neural nets, genetic programming, fuzzy logic, and temporal difference learning.

    The temporal difference between the effort to build such an AI and 500 bucks seems a little too great.

    • Re: (Score:2, Informative)

      by Anonymous Coward

      I love how you included fuzzy logic in your list of otherwise hard to pull of AI functions.

    • Re: (Score:2, Funny)

      Not to mention that you need to be present at the conference to claim your prize. Otherwise you just get a certificate.
      • Not to mention that you need to be present at the conference to claim your prize. Otherwise you just get a certificate.

        In that case, the prize might not even cover airfare and a hotel stay.

        • by xtracto (837672)

          And the worst thing is that the price might not even cover the conference registration fee!

          But for the scientific value is quite interesting, moreover this is more aimed at the scientific community where researchers usually get sponsored by their institutions when publishing a paper and going at conferences

    • Re: (Score:3, Insightful)

      by Sockatume (732728)

      On the other hand offering a larger prize for a competition of this nature is pointless. I doubt that you'd get MIT to devote a research grant even if it was offering up $500,000.

    • A cash prize like that is more like a recognition of the achievement than an incentive to compete. Same way no-one goes after the Fields medal for the money.

    • by jtogel (840879) <julian@togelius.com> on Wednesday August 05, 2009 @07:57AM (#28954975) Homepage Journal
      Actually, this is not true. The competition is mainly aimed at academic researchers, who work with these techniques anyway, and for whom 500 dollars (into your own pocket, not your research fund) is not a completely insignificant amount. But of course, the main motivation for researchers to take part is of course the recognition. And of course others than academics are very welcome to take part as well! We're very much looking to broaden the participation.
    • The temporal difference between the effort to build such an AI and 500 bucks seems a little too great.

      Sure, because nobody's spending hundreds of millions of dollars in research and development for the 1-million dollar purse in the various X-Prize competitions (launch vehicles, lunar landers, autonomous vehicles, genomics, etc)

      Oh, wait...

  • by risinganger (586395) on Wednesday August 05, 2009 @04:41AM (#28953471)

    We welcome hard-coded submissions, commercial AI programmers, academics and amateurs alike.

    Yet you only post this on slashdot with 13 days before the deadline. You couldn't have posted it here back in May? (the earliest date a post seems to have in your google group).

  • This is hard (Score:5, Interesting)

    by phantomfive (622387) on Wednesday August 05, 2009 @04:47AM (#28953507) Journal
    This is hard. I think if I were going to do it, I would break it up into steps.

    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?
    • by jtogel (840879)
      Yeah, please enter! You can set the level difficulty from 0 to 10, and choose whether to have enemies in or not (with the world paused/unpaused option), so basically you can evaluate your solutions first on a paused level with difficulty 0 (few holes and few obstacles) and then incrementally increase the difficulty.
    • by Lisandro (799651)

      Heh, maybe I'll enter. How hard can it be?

      Very. As in "really fucking hard".

  • First thought: "WOAH, this seems awesome! Can't wait to see what kind of crazy awesome stuff people come up with! Perhaps something like Air Man versus Genetic Algorithm [youtube.com]?"

    Second though: "Hmm.. Emulating keypresses is easy as cake, but I wonder how their game passes info about Mario's environment to the controller? After all, this is a contest of skill and creativity, so there should be a system in place to allow code monkeys and 1337 programmers to contribute, regardless of their tools of choice."

    Still thin

    • by Arthurio (1392181)
      get eclipse http://www.eclipse.org/downloads/ [eclipse.org] and jdk - that's it. happy coding!
      • by andi75 (84413)

        While I think Eclipse is great, I believe NetBeans [netbeans.org] is even better these days, at least for someone just picking up Java. The advanced features don't get in your way as much as with Eclipse.

        • by WarpGiGA (647974)

          Netbeans.org all the way! (or eclipse if you wanna be like that)...

    • by RegularFry (137639) on Wednesday August 05, 2009 @07:21AM (#28954679)

      "Java only? What the hell !?"

      Um... no.

      Controllers written in any language are welcome, as long as they can be interfaced to an unmodified version of the marioai package - directly if written in Java, through the TCP interface otherwise. In any case, the controllers must be able to run in real time on an Intel machine running either Mac OS X (preferred), Ubuntu Linux or Windows XP.

      • by plastbox (1577037)

        Uuuh! Awesome! Seriously, how the hell did I not see that? It's not like that site is all that content heavy. o_O

        I might just suffer from some sort of sneaky invisible ninja selective blindness but I can't seem to find any info on this TCP interface. Curse you, sneaky invisible ninja selective blindness!

    • Re: (Score:3, Interesting)

      by TheRaven64 (641858)
      Java is a language. It's a descendant of Smalltalk via StrongTalk/Objective-C with syntax inspired by C++.

      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.

      • Not only is it expressive, but there are lots of useful AI and Machine Learning libraries written in it. Java may get a bad reputation from a lot of people, but it is heavily used by academics.

    • by jtogel (840879) <julian@togelius.com> on Wednesday August 05, 2009 @08:18AM (#28955239) Homepage Journal
      Personally, I love Java, but I recognize that not everybody does. As another poster has already commented below, any language is permitted as long it can somehow interface to the game code. To begin with, there are several languages other than Java that run on the JVM (Scala, for example) and these can interface directly to the code. You can also interface via the provided TCP interface; we've included a Python example. Or via JNI (Java Native Interface) for c programs.
      • by plastbox (1577037)

        Ok ok, I was too quick to post. I get it *wanders off to corder with both feet firmly lodged in mouth*

        Luckily, I never cared much about making an ass of myself, "thinking before speaking is like wiping your ass before you.. well, you get the idea" and all. So I'll just ask and hope I get an answer and not a painful reaming.

        How do I launch the network agent? I've tried everything I can find here [google.com] but at best it launches the game in keyboard control mode. Do I just suck? Should it be blatantly obvious how to g

        • thinking before speaking is like wiping your ass before you.. well, you get the idea

          It sounds like whoever coined that idea really should have thought before they spoke. Unless they were being intentionally ironic.

  • too short. (Score:5, Insightful)

    by tetha (1612425) on Wednesday August 05, 2009 @06:14AM (#28954207)

    I highly like this competitions idea, but I won't participate, because the deadline is far, far too soon.

    I mean, I am supposed to understand their framework and implement, test and tweak an artificial intelligence for a pretty complicated task like this in a month (let alone, 2 weeks), with my rusty java, rusty AI-knowledge (I'd try emergent behaviour, probably)? Sorry, but this is just plain impossible, since there is enough work to do from the university and other hobby projects. Give me until, like. Christmas and I'd try.

    Plus, the time shortens even further, as it appears that there are documentation issues, so one would probably have to work out how the game state is given to the AI.

    So overall: very interesting, but too short for someone who actually has other work to do

    • Re: (Score:2, Insightful)

      by WarpGiGA (647974)

      Consider just doing it for fun then, the $500 price isn't worth whining about anyways.

    • by jtogel (840879)
      The CIG deadline is September 3, which is almost a month away (you don't need to submit to the first phase). Plus, if the competition is a success, it will run next year as well.

      While I admit the documentation is a bit on the short side, it should be perfectly enough to get started. All you need to do is look at the Agent interface, and there you have the format of the data the game is giving to you.
    • by xtracto (837672)

      It is amazing [youtube.com] what less whining and more working can achieve.

  • I'm running a competition to see who can program an AI that will create the game Super Mario Bros, by analyzing the behavior patterns of human subjects.
  • I assume this competition will end before New Super Mario Bros. Wii comes out. But when it does, someone should try to get that AI to work on the game for this competition. The AI I am speaking of is the new feature where if something is too difficult you can press start, select an option, and it will complete the area for you.
    • Unfortunately, New Super Mario Bros. Wii is using a fixed level... So it's not so much AI as it is preprogrammed response. It likely wouldn't know how to deal with a randomly generated level.

  • Neat! (Score:2, Interesting)

    by The_Duck271 (1494641)
    Programming games are fun!

    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 programme
  • But really, any approach is fair game

  • by Anonymous Coward

    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

  • by gizmoguy4242 (262865) on Wednesday August 05, 2009 @09:24AM (#28956117)
    Just thought I'd point out that we also did this in the 2009 Reinforcement Learning Competition (I was the general chair):

    http://2009.rl-competition.org [rl-competition.org]

    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

    • by CnlPepper (140772)

      It would be more interesting to make a more complex game/simulator, however the problem with this is it rapidly raises the bar for entry into the competition. Amatures without the necessary computing power could end up being rather left out.

      A game where the input space is larger and less predictable, which also has scope for live tactical and/or strategic decisions would be interesting. How about a 3D, fully Newtonian physics space combat simulator in a chaotic asteroid field. Basically robocode++. The agen

  • Asteroids played by robots. Contest: http://www.heise.de/ct/projekte/machmit/asteroids/ [heise.de] Results: http://www.heise.de/ct/creativ/08/02/ergebnisse/ [heise.de] (push on the play buttons to see the videos)

  • Can humans even do this reasonably? By that what I mean is, when we play, we don't play based off what we see on the current screen. I doubt many people have beaten the game on their first play through. Most of us had multiple tries, seen more of the level and honed our timing in tricky spots.
    • by jerep (794296)

      An AI could have some memory of the level too, its really not hard to just save the actions up to where it died, keep a state of what the area looked like and then plan ahead for its second try.

    • Re: (Score:3, Insightful)

      by Bakkster (1529253)

      Can humans even do this reasonably?

      No, but shouldn't a computer be able to do it better? Perfect concentration, perfect timing, the ability to make split-second decisions, no visual limitations of how much of the screen can be seen; computers have the potential to do far better. Isn't that the idea?

  • A few words of advice from someone who is in a similar marriage and has been since 1974. The most difficult years in marriage are after the wedding. :-) I say that because so many people think that marriage will bring eternal bliss. It doesn't. But it doesn't have to be a living hell, either. Marriage isn't so much about how compatible you are but how well you deal with incompatibility. It helps to find common interests that you can share in together. Look at disagreements as a challenge to work out toge

Receiving a million dollars tax free will make you feel better than being flat broke and having a stomach ache. -- Dolph Sharp, "I'm O.K., You're Not So Hot"

Working...