11 ms·
Programmer Creates An AI To (Not Quite) Beat NES Games
- shmageggy 14y agoMuch better article here: http://www.wired.co.uk/news/archive/2013-04/12/super-mario-solved http://www.wired.co.uk/news/archive/2013-04/12/super-mario-s... The video is long but worth all 16 minutes. I like how he isolated such a dead simple heuristic for success in video games. It's not surprising, in retrospect, that "numbers going up" would correlate with winning, but to prove it in practice is pretty neat.
- jstanley 14y agoHe isn't very explicit about it, but the "time travel" that is mentioned basically allows it to go back in time if things turn out badly. This is what allows it to make such unbelievable trick moves: in short timespans it is almost a brute-force search, but over the longer term it can't backtrack as much. If that makes sense.
- ok_craig 14y agoPausing Tetris to avoid losing was hilarious.
- niggler 14y ago"The only way to win is not to play"
- acchow 14y ago"The only winning move is not to play." The author is humorous, poetic, and brilliant.
- keeran 14y agoand possibly a fan of WarGames :)
- alan_cx 14y agoExactly what I thought. I even think it was a clever way to end, and a point he might have been making as a sort of subtext.
- acchow 14y agoI've never seen WarGames. After reading the synopsis, the subtext is undeniably intentional.
- alan_cx 14y ago30 year old movie spoiler alert!!!! War Games: Very, very basically, from deep, deep memory... A computer about to launch a global nuclear war is played at tic-tac-toe to learn it cant win. It deduces that the only way to win a nuclear war is not to start the thing in the first place. Any other strategy is a lose, or what we call mutually assured destruction. Its obviously more complicated than that. Even though its 30 odd years old, it worth a watch.
- Ntrails 14y agohttp://i.imgur.com/fSBsN7c.png http://i.imgur.com/fSBsN7c.png want to play?
- tvirot 14y agoNot sure if people notice the last sentence in the article: "Murphy ran a few other games through it, including Tetris, and found that the program would eventually just pause itself rather than continue playing and lose, a tactic shared by annoying, over-competitive cousins around the world since 1985."
- pmb 14y agoIf your numbers are going up, it means you are having more fun! http://radgeek.com/gt/2006/04/28/antieconometrix_comix/ http://radgeek.com/gt/2006/04/28/antieconometrix_comix/ It's too bad that game that need more lookahead - Tetris, etc, are not amenable to this approach.
- chc 14y agoIt sounds to me like it's basically how deterministic a game is that determines whether this works. For a Tetris with a defined order that the pieces appear in, I bet this algorithm could do pretty well.
- deleted 14y ago[deleted]
- yew 14y agoIt seems like the problem is more that it can't look far enough into the future to see that grabbing lots of points now (by stacking blocks) is canceled out by losing (that is, not gaining) points later. It would be interesting to see how it responded when the 'Pause' function was disabled. It seems like it would need to track 'past future' state to find a solution. Edit: Or maybe try to filter out 'constant' sources of increasing value. Treat the stacking points as noise.
- jerf 14y agoFor the purposes of this AI player, all NES games are fully deterministic. Even what hardware the NES had that could be used for random number generation is under the control of the emulator and being run deterministically. There's no "random" in the usual sense here.
- smd4 14y ago"This game is mostly a go to the right and jump and throw hammers at birds..." Classic delivery. I love this guy.
- acchow 14y agoHe made me laugh repeatedly.
- camus 14y agoi hope i live until the day when robots can beat games without any prior knowledge of the game logic,well actually it would be quite scary
- pbhjpbhj 14y agoScary indeed. Those robots might be very good at ... Thermonuclear War.
- deleted 14y ago[deleted]
- sethbannon 14y agoFYI the video is worth a full watch. The author of the paper is painfully funny.
- dvanduzer 14y agoCrikey, just read the paper: """ On a scale from "the title starts with Toward" to "Donald Knuth has finally finished the 8th volume on the subject," this work is a 3. """
- acchow 14y agoBoth the video and paper are well worth going through! The Abstract is 16 words. The introduction begins with "The Nintendo Entertainment System is probably the best video game console, citation not needed." Need we say more? Also, I wish non-programming fields of media would also adopt pythonic triple-quotation marks.
- mitchty 14y agoEww, why would you want triple quotation marks being adopted anywhere? What overlying function in print would they serve exactly?
- saurik 14y agoMany people forget that using inch marks in place of quotation marks (which don't have neating issues) is an ASCII-only phenomenon.
- TazeTSchnitzel 14y agoThey aren't "inch marks". They're straight double quote marks. The prime (used for feet, arc minutes), double prime (used for inches, arc seconds) and ditto mark are all distinct.
- shurcooL 14y agoI can confirm it was well worth my 16 mins. This really makes me want to go back to my game and play some more with AI. Although, at the same time I realize that's the mistake I made - making the game/platform for creating AI. It really takes a toll. This guy uses existing NES games, which allows him to focus on the AI and even generic game learning. Brilliant. You can clearly see the advantages of AI in the short-term play (think in the order of milliseconds, exact frame-by-frame button presses) over anything a human could ever achieve. Imagine combining the short-term button-mashing of said AI with the long-term planning of human players...
- jaredsohn 14y agoDirect link to paper: http://www.cs.cmu.edu/~tom7/mario/mario.pdf http://www.cs.cmu.edu/~tom7/mario/mario.pdf Direct link to video: http://www.youtube.com/watch?feature=player_embedded&v=xOCurBYI_gY http://www.youtube.com/watch?feature=player_embedded&v=x...
- jal278 14y agoJust to note that the AI has complete access to the NES's RAM (and also backtracks whenever it gets into trouble), which is not quite fair to compare to other approaches to AI or playing against a human. I'd be pretty damned good at battleship if I could see your board and rewind whenever I missed.
- Falling3 14y agoAnd that's probably why he didn't showcase playfun on Battleship. I do agree with you though.
- pyre 14y agoBut the AI isn't making strategic decisions. It's making brain-dead ones. It analyses a play-through looking to find sections of RAM that increase as time increases. It them locks in on these sections of RAM and says "increasing the values in these sections of RAM is how I determine success." It them brute-forces a play-through with the ability to rewind time (to try a different set of inputs). This is why he mentions that Karate Kid didn't work well, because one of the factors of a successful play-through was that your opponents health is decreasing, which is something that this AI doesn't look for. The ability to rewind time wouldn't make for a very interesting play-through of Battleship, but depending on how game state is stored, it might not even be able to accurately deduce a good game state from a bad one.
- jayrobin 14y agoThis is why he mentions that Karate Kid didn't work well, because one of the factors of a successful play-through was that your opponents health is decreasing, which is something that this AI doesn't look for. I don't believe that was the case. From the video he mentioned it using the power kicks up all on the first enemy because they produced the most favorable outcome for that game, at the expense of later games when more powerful moves are needed (since the AI can't plan that far ahead).
- tverlinden 14y ago
- marvin 14y agoPardon me if I'm really ignorant of the AI field here, but doesn't this look like the beginning of more general artificial intelligence? The organic feel of some of these moves is almost scary to me.
- wmf 14y agoKeep in mind that it's using time travel to do those moves. In the real world time travel is not currently available.
- JoshTriplett 14y agoSimulation and models often are, though.
- alecbenzer 14y agoWhat exactly does "time travel" mean in this context? That the simulation makes some moves, sees what happened, and then has the ability to undo its moves and go back to its old state, and then try new moves?
- bryanh 14y agoYes, exactly.
- allenu 14y agoYes. It's basically a brute-force Groundhog Day approach to finding the best move.
- schackbrian 14y agoAnother movie analogy would be Next. Cris Johnson can see two minutes into the future and redo anything that has a bad outcome. http://en.wikipedia.org/wiki/Next_(2007_film) http://en.wikipedia.org/wiki/Next_(2007_film)
- raldi 14y ago
- aaron695 14y agoVery funny video and worth watching. But it's not even close to beating NES Games. I'm not a expert in AI but I'm not sure it actually achieves anything. I'd consider it more an art project than a computer science project.
- ijk 14y agoNote that it was published as part of SIGBOVIK. This paper definitely falls within the approaches to computer science exemplified by the illustrious, eponymous Harry Q. Bovik.
- TallboyOne 14y agoYou must not be very fun at parties.
- yew 14y agoDepends on what sort of parties you like.
- kragen 14y agoYou will be amused to learn that the author, Tom 7, also wrote the Crap Art Manifesto at http://crapart.spacebar.org/ http://crapart.spacebar.org/, which is equally funny and even more thought-provoking.
- michaelochurch 14y agoUninformed speculative question here: could the algorithm be improved with some sort of momentum term in the input selection? It seems to succeed with move-to-the-right (position counter) but fall into what looks like Brownian motion on Pac-Man. It seems to me that putting momentum into its strategy (and changing when the objective function declined) might reduce the implicit branching tree. What it simulates, then, is the tendency for people to fall into "a groove" and depart from it when their objective function ceases increasing.
- raldi 14y agoI'd really like to see a fuller analysis of what Pac-Man was doing there. As I understand the algorithm, it should have seen into the future where the dot gets eaten, and not turned back. But maybe the program failed to discover the bytes which hold the score, and so it didn't think eating dots was a particular notable activity.
- LordLandon 14y agoMaybe it gets distracted increasing the pac-scent? There's certainly a lot more of that around in memory
- nate_martin 14y agoI wonder how this would handle an NES golf game.
- rcfox 14y agoIn "NES Open", you earned money depending on how you placed. So, given long enough jumps back in time, there is a way to track an increasing score. Either way though, I think the results would be sub-par.
- anonfunction 14y agoslowclap.gif
- deleted 14y ago[deleted]
- anonfunction 14y agoIf I had named it golfclap maybe you would understand. Thanks for being a dick.
- drakaal 14y agoConsidering there are bots to beat you at Call Of Duty, and Quake, this is not such a feat. I can't find a reference but I recall an Emulator for NES that used to be able to be player 2 for something like 40 NES games.
- icebraining 14y agoI think you missed the point somewhat. Those bots were coded just for those games, with human-made models and strategies adapted to them. This bot, on the other hand, understands nothing about the games themselves besides the input keys and the score number(s). It's playing blind.
- drakaal 14y agoHaving written real AI's this aint one. 4 directions and two buttons. You could point a crappy machine learning algo at it, and it would figure it out. That is far fewer variables to manipulate than what a Quake bot has to deal with. I would bet money I could zap a pigeon every time it died in mario and it would learn to be a master in 12 hours. It won't master CoD anytime soon.
- jaredsohn 14y agoHow would it figure out what it means to be "winning"? It might be possible, but would require using OCR to read the 'score' (and guessing as what is meant by the score) and would also need some way to determine if the goal is to "go to the right", etc. (also possible). Doing this would be interesting and more practical in that it could work with games where you do not have access to the memory, but seems like it would require more work in interpreting how the game's state has changed and wouldn't allow going back in time. A Quake bot is easier to develop because it is written for a specific game. I accept that bet for training a pigeon to play SMB :), although the scenario you described isn't comparable (it is only one game and you would be giving the pigeon extra feedback about how to play it. It still seems hard and I think it would be notable if you achieved it.)
- 14y ago
- jmyc 14y agoRelated: genetic algorithms to play video games. I can't find the exact one I read about before, which was for Super Mario Bros., but searching for "mario genetic algorithm" leads to a number of papers, videos, &c.
- ihsw 14y agoThere are a[1] couple[2] on YouTube. [1] http://www.youtube.com/watch?v=qYluZRwrw9w http://www.youtube.com/watch?v=qYluZRwrw9w [2] http://www.youtube.com/watch?v=DlkMs4ZHHr8 http://www.youtube.com/watch?v=DlkMs4ZHHr8
- pudquick 14y agohttp://julian.togelius.com/mariocompetition2009/ http://julian.togelius.com/mariocompetition2009/ Similar, but more interesting
- jamesjporter 14y agoVideo is hilarious and worth watching the whole thing as others have mentioned, but there's some great stuff in the paper also. He mentions some really interesting future directions, e.g. obviating the need for the training data set of a human playing the game by having the computer initially try different sets of random inputs and continuously improving on those that do the "best" according to it's objective function. The bit about the computer trying to play "dinosaur coloring" is fantastic also.
- raldi 14y agoSounds to me like the next big improvement would be to give the algorithm a concept of boredom: If the numbers haven't gone up in a while, consider that very bad. Try progressively more crazy things. For example, unpausing Tetris. Or having Mario run left.
- skore 14y ago> Try progressively more crazy things. Teaching a computer various concepts of 'crazy' must be tons of fun! :-D
- hhaidar 14y agoThe ending is very poetic in a way.
- fiatmoney 14y agoThen they taught it to make paperclips, and ended up with one of these: http://wiki.lesswrong.com/wiki/Paperclip_maximizer http://wiki.lesswrong.com/wiki/Paperclip_maximizer
- Houshalter 14y agoUntil it finds a glitch in the matrix that allows it to pause real life.
- anonymfus 14y agoBruteforcing all states of NES game could result in finding vulnerability in NES emulator and then to fill memory of emulator with FFs via changing settings it could make mess from accessible file system or, some life spans of universe later, find vulnerabilities in OS, hardware or connected network.
- minikomi 14y agoNo need. In order to maximize score, two NES's are better than one.. and three are better than two..
- sequoia 14y agoHa! This shows up in pop culture in the game Star Control II (awesome game btw): spoiler alert | You are travelling thru space encountering an ever-increasing number of what appear to be robotic ships with whom you can briefly interact before they end communication and attack you. Long story short: a planet-bound race, the Slylandro, purchased a robotic ship for exploration and to establish friendly contact with other races. The ship had the power to self-replicate; it also carried a small defensive weapon and a powerful lightning-bolt type tool for breaking-down and gathering resources for ship replication. The Slylandro wanted more probes faster so they turned the replication priority up to 11, overriding all other priorities. When a ship meets you, it attempts to initiate contact but is quickly forced into resource-gathering/replication mode & proceeds with breaking apart your ship into raw components. It is, essentially, a paper-clip maximizer. :) http://wiki.uqm.stack.nl/Probe http://wiki.uqm.stack.nl/Probe
- anonfunction 14y agoMy favorite part was how the program finds glitches and uses them ruthlessly.
- DanWaterworth 14y agoI wonder if a more advanced version could be used as a bug finding tool for modern games.
- fudged71 14y agoI love that idea! What seem to us to be implausible, to the code it looks like nothing other than a legitimate strategy. The issue for modern games is the amount of memory used.
- blauwbilgorgel 14y agoAt university we had a contest with programmable tanks. Many wrote elaborate algorithms and tried to find the optimal strategy, but the winner was very crude: It tried to get a little bit more life than its opponent, and if it was ahead it would immediately start spawning threads, until the play server couldn't handle it anymore and crashed -- Winning by default.
- keeperofdakeys 14y agoI had a similar kind of assignment, using a java system called robocode. I ended up writing a system that could track a tank moving in a static arc, while moving itself, which worked surprisingly well.
- keithwhor 14y agoThe day has come, "AI rage quits, passes Turing test."
- repler 14y ago... sooo, that's not really a great application of a GA. Perhaps not even a great implementation. Akin to making things out of Legos at best. (ie: "because!")
- gjm11 14y agoIt's not an application of a GA at all. Before dismissing something, it's best to understand it.
- nokya 14y agoI love the fact that a newspaper can still publish this without fear of losing viewers. It's like eating at a restaurant that everyone qualifies for dog food but... well...we go anyway :)
- gnarbarian 14y agoUsing A* does a much better job: http://www.youtube.com/watch?v=DlkMs4ZHHr8 http://www.youtube.com/watch?v=DlkMs4ZHHr8 Look at that AI play. It's godly.
- jitl 14y agoThe paper uses an approach general enough for any game on the NES, which is what makes it exceptional. The humor is killer, too.
- Houshalter 14y agoThe goal isn't to beat mario as efficiently as possible, but to create a program that can learn to play literally any game. Also what is that AI doing when it decides to jump into the pit at 0:45? It clearly sees the path to jump over it, but it chooses the one that jumps into it. Watching it frame by frame it seems to figure out a path to jump out of the pit several times, but chooses not to, until eventually it finally does.
- wiremine 14y agoMore authors should make videos like. Well done!
- bicknergseng 14y agoThe only winning move... is not to play.