Kicking koopas and stomping goombas, for Science!

August 6, 2009 6:20 AM

A couple of professors, in collaboration with two upcoming IEEE conferences, have organized a Mario A.I. Competition (via), inviting programmers to create controllers for a modified version of Infinite Mario Brothers (previously). One contender has stepped up and posted a demo of his controller in action.

Overview (from the site):

"This competition is about learning, or otherwise developing, the best controller (agent) for a version of Super Mario Bros. The controller's job is to win as many levels (of increasing difficulty) as possible. Each time step (24 per second in simualated time) the controller has to decide what action to take (left, right, jump etc) in response to the environment around Mario.

We are basing the competition on a heavily modified version of the Infinite Mario Bros game by Markus Persson. That game is an all-Java tribute to the Nintendo's seminal Super Mario Bros game, with the added benefit of endless random level generation. We believe that playing this game well is a challenge worthy of the best players, the best programmers and the best learning algorithms alike."

posted by tybeet (42 comments total)

From the YT comments "I'd love to see this tackle Asshole Mario".
posted by tybeet at 6:26 AM on August 6, 2009 [3 favorites]

Back in MY day, we had to spend HOURS on the couch in the basement working on hard Mario levels. Kids today have it so easy.
posted by DU at 6:28 AM on August 6, 2009 [1 favorite]

But seriously, this is amazingly awesome. What a great way to engage people from both inside and outside the field.
posted by DU at 6:30 AM on August 6, 2009

Ha! Asshole Mario is great.... but the Mario AI is awesome. Very cool!
posted by molecicco at 6:31 AM on August 6, 2009

This was impressive... then he falls in a hole and manages to jump out again. *jawdrop*
posted by paulesque at 6:35 AM on August 6, 2009 [1 favorite]

Yes, I hope all those people who scoff at the possibility of genuine AI see this video and observe humanity's nascent master learning to jump out of holes. Visions of Terminator armies are not new, but imagine them exploiting bugs in reality, bunny-hopping across wastelands of skulls at terrifying speeds, camping our makeshift maternity wards...
posted by No-sword at 6:54 AM on August 6, 2009 [4 favorites]

Holy shit. Thanks for my morning dose of awesome sauce.
posted by middleclasstool at 7:05 AM on August 6, 2009

Yeah, how did Mario jump out of the hole in the "controller in action" video (:45)?
posted by starman at 7:15 AM on August 6, 2009

From the YT comments "I'd love to see this tackle Asshole Mario ".

Ha! The hidden coin block was the best thing ever to happen to level editors.
posted by Demogorgon at 7:17 AM on August 6, 2009

Yeah, how did Mario jump out of the hole in the "controller in action" video (:45)?

Apparently, this version of Mario features wall jumps.
posted by graventy at 7:35 AM on August 6, 2009

We are so fucked.
posted by dirtdirt at 7:40 AM on August 6, 2009

Is this sort of like those chess computers, where they have all the moves memorized? Does it actually learn or does it store a list of various enemy movements and simply build a path based off that?
posted by geoff. at 8:23 AM on August 6, 2009

They say in the Youtube description that it's only using information on screen, so it's nothing that a human couldn't theoretically do.
posted by echo target at 8:39 AM on August 6, 2009

How to exploit Super Mario World glitches, including a demo of the wall jump at 0:25.
posted by Plutor at 8:46 AM on August 6, 2009 [3 favorites]

Judging by the video (and the pretty red lines) it seems to have a projected path, and when something gets in the way of the path, it recalculates some alternatives on the fly.

But yeah, the jumping out of the hole thing? I don't think the physics are any different, but I suspect (WARNING! ARMCHAIR GAME PHYSICS ANALYSIS!) there's a split-second moment when the collision with the wall flips the $canjump switch to true (or whatever), and this is able to pick up on that. Theoretically, if humans had the reaction time to exploit it, we could.

I had the exact same reaction when I saw it, by the way. First it was "Awesome!" then, almost immediately thereafter, "How long until my toaster grills my face while I sleep?"
posted by SpiffyRob at 8:49 AM on August 6, 2009 [1 favorite]

And on non-preview, judging by Plutor's link, it seems some humans can!
posted by SpiffyRob at 8:51 AM on August 6, 2009

Judging by the video (and the pretty red lines) it seems to have a projected path, and when something gets in the way of the path, it recalculates some alternatives on the fly.

Yeah, I think the red lines are a kind of visualized decision-tree based on what obstacles are on the screen, Mario's position, and what possible moves can be made, going forward at any given instant - hence some of the areas where there's a whole range of different paths.
posted by tybeet at 9:02 AM on August 6, 2009

My girlfriend is borrowing her sister's Wii, and they've made a bunch of Wii Arcade purchases (which is really what the Wii is for, as far as I'm concerned), so I started playing through Super Mario World, something which I've been wanting to do for about six months now, and only the fact that my Super Nintendo is in storage has stopped me.

I had forgotten just how challenging that game is. Nintendo didn't really fuck around back in the day. So this is pretty fucking crazy.
posted by Caduceus at 9:22 AM on August 6, 2009

I should clarify, from what I've read, and the poster's explanation of it on reddit, this version of Mario features walljumps. Kind of like New Super Mario Brothers on the DS.
posted by graventy at 9:24 AM on August 6, 2009

tybeet: "I think the red lines are a kind of visualized decision-tree based on what obstacles are on the screen, Mario's position, and what possible moves can be made, going forward at any given instant - hence some of the areas where there's a whole range of different paths."

According to the page for the project's developer, it uses an A* search trying to optimize the speed to get to the right hand side of the screen without getting hurt.
posted by Plutor at 9:25 AM on August 6, 2009

I had forgotten just how challenging that game is. Nintendo didn't really fuck around back in the day.

Nintendo Hard
posted by kmz at 10:00 AM on August 6, 2009

We are so fucked.

Not because of this, but his other pet project is a DEFCON AI bot.

Joshua?
posted by cloax at 10:46 AM on August 6, 2009

they've made a bunch of Wii Arcade purchases (which is really what the Wii is for, as far as I'm concerned)

Wii Sports Resort is simple and fantastic, but I'll end my derail there.

That AI run video was dizzying and amazing. I'm looking forward to AI runs through 3D realms, in FPS or fighting games. There are some amazing people, but truly split-second decisions are dazzling.
posted by filthy light thief at 10:47 AM on August 6, 2009

it intrigues me how it leaves so many blocks and coins behind...i guess the impulse to 'get stuff' (whether you need it or not) in video games is purely human...of course, if you're good enough to play infinite mario for infinite time, you're going to end up with infinite coins (whether you want them or not).
posted by sexyrobot at 11:13 AM on August 6, 2009

That AI run video was dizzying and amazing. I'm looking forward to AI runs through 3D realms, in FPS or fighting games.

What will be really cool is to see is A.I. that approaches SMB with the same sensory information that we humans do. This Mario A.I. uses information that is largely behind the scenes, but can you imagine if it were done with a camera processing the visual scene and making decisions based on identified patterns? I guess, sorta like Splashbot, the Guitar Hero robot. It might not even be that hard from an engineering standpoint, since it's a 2D sprite-based game, the patterns are fairly discrete.
posted by tybeet at 11:26 AM on August 6, 2009

sexyrobot: "if you're good enough to play infinite mario for infinite time, you're going to end up with infinite coins"

That reminds me of a paradox I heard once (I can't figure out if it has a name, but it's similar to other supertask paradoxes, like The diary of Tristram Shandy and The Ross-Littlewood paradox.)

You die and go to hell. When you get there, you find out that the devil is actually running a business. You must work for him forever. But at the end of each day, he will pay you ten dollars for your labor, and tax you one dollar for room and board (and heating, one assumes). He gives you a choice of the exact mechanics of the transaction. One choice is that he will give you ten dollars, which you put into your (infinite) wallet. He will then take one dollar at random out of your wallet. The second choice is that he will simply give you nine dollars at the end of the day. Which do you choose? (Think for a moment before reading on.)

===

Since you'll be in hell forever (not just a really long time, but actually infinity), you want to choose method two. By the first plan, every dollar bill that goes into your wallet will eventually come back out, so none of the dollars are ever actually yours.
posted by Plutor at 11:30 AM on August 6, 2009

Browsing around hacked ROM videos on youtube I stumbled upon Board 2 a rom hacking forum.
posted by wcfields at 11:42 AM on August 6, 2009

Nintendo Hard

Can we please not link to tvtropes? I know it seems clever at first, but I have seen many forums go down that god forsaken path and it is not pretty.
posted by afu at 12:07 PM on August 6, 2009

What path? The path of awesome?
posted by Pronoiac at 1:41 PM on August 6, 2009

What's wrong with tvtropes?

Wii Sports Resort is simple and fantastic, but I'll end my derail there.

Let me continue that derail. Wii Sports Resort is a sequel to the number one played game on the Wii. That's why it was made, to hopefully recapture and capitalize on that market. Good nonetheless though.
posted by P.o.B. at 1:51 PM on August 6, 2009

Plutor: Since you'll be in hell forever (not just a really long time, but actually infinity), you want to choose method two. By the first plan, every dollar bill that goes into your wallet will eventually come back out, so none of the dollars are ever actually yours.

This of course assumes that there is a time t=infinity; since there is not, at any particular time in the future, both results are identical. Yes, every individual dollar eventually leaves, but only to be replaced by nine more per day.
posted by vernondalhart at 3:57 PM on August 6, 2009

P.o.B.: "What's wrong with tvtropes?"

The fact that I just lost several hours of my life there.
posted by mindless progress at 4:12 PM on August 6, 2009 [1 favorite]

Several hours? Quitter.
posted by Pronoiac at 4:20 PM on August 6, 2009

What's wrong with tvtropes?

The problem is that tvtropes is has so many entries, that basically any narrative structure can be found there. This leads to people just linking to to tvtropes when there is any vague relation between the topic and the and one of the tropes. This is lazy, degrades the topic of conversation as a mere trope and tends to derail the discussion into whether the linked trope is appropriate or not.

I'm probably a little bit sensitive because a web comic forum I used to participate in was pretty much ruined for me because almost every thread had a link to tvtropes, which caused all manner of derails and flameouts.
posted by afu at 6:48 PM on August 6, 2009

and here I am derailing this thread, I'll stop now sorry.
posted by afu at 6:48 PM on August 6, 2009

Asshole Mario reminds me of Mega Man on normal difficulty. Seriously, I downloaded Mega Man 9 on my PS3, and couldn't get through one level. I've never been the most amazing achievement oriented gamer, but I've finished a number of games in my time, including a number of the Super Mario games, and I used to be a reasonably accomplished Quake 3 / Half-Life multiplayer deathmatch player when those games were in vogue, so I had the twitch thing down.

But Mega Man 9 used me to wipe the floor and then threw me in the trash when it was done with me...dunno if it's old age or laziness (from old age)...
posted by dubitable at 7:42 PM on August 6, 2009

Jesus, we are doomed.
posted by uncleozzy at 11:42 AM on August 7, 2009

I think you left out the link, uncleozzy, though it's amusing without one.
posted by Pronoiac at 12:54 PM on August 7, 2009

Bollocks. Here it is.
posted by uncleozzy at 12:56 PM on August 7, 2009 [1 favorite]

uncleozzy: Bollocks. Here it is.

Whoa. I like how distinctly you can see the A* search tree. The slow-motion version is neat too. From a gaming point of view, it's a lot like auto-aiming in Counter-Strike. I mean, you're still directing the action, right?

Pronoiac: I think you left out the link, uncleozzy, though it's amusing without one.
I thought it was a self-reference/recursion A.I. joke.
posted by tybeet at 1:07 PM on August 7, 2009

the results (PDF) have been posted.
posted by Pronoiac at 1:20 PM on August 27, 2009

I'm a member of the third place team (for the ICE-GIC part at least, the final round is on Sep 3). The videos linked above are RobinB's agent, the current first place competitor.

Our team was made up of folks who got together in the #marioai IRC channel after I posted a video of my rather braindead AI to programming.reddit. After working on it for a little while (thanks largely to a1k0n's amazing contributions) we found ourselves unexpectedly competitive and we made our github repository private. That link will be live again in a couple days once the submission deadline for the final competition passes.

However if you just want some eye candy you can run our AI on your machine here: http://rictic.com/marioai
posted by Rictic at 12:21 AM on September 2, 2009