I wouldn't mind even if the entire movie (still talking about the keypad input) is computer generated. Actually, that could be exciting to see :)
This is actually something I've been thinking about for a while now.
Even a short game, like a 5-minute-or-less run through SMB1, has 4.6 million possible combinations of controller input. A few of them might beat the human-assisted record; almost all the rest will feature Mario blindly walking into the first Goomba on level 1-1. The trick in finding an efficient way to create computer-generated game runs will be finding that needle in the haystack, and not wasting time on hay.
I have a few ideas about how this might be accomplished, and they draw on all the three semesters of Computer Science I didn't really pay attention during when I was in college. Has anyone else given any thought to this kind of thing?
Even a short game, like a 5-minute-or-less run through SMB1, has 4.6 million possible combinations of controller input.
Yes, that's correct. If you are counting just the first three frames. 256^n
Thus, brute forcing is obviously out of the question. The only way to do this would be to to mess around with the rom, figure out the randomization, look at the engine, a.i., etc.....
It has been discussed before several times on the forums.
Uh, I'm pretty sure it's more than anything million...
There are 8 buttons on the controller, for a grand total of 256 possible key combos every frame...and 5 minutes is 18000 frames...
So, 256 to the 18000th power...Windows Calculator gives me a grand total of (2.0862945006843350017504841464267 times 10 to the 43348th power)...o_O
I'm pretty sure what Bisqwit was talking about wasn't a randomly generated sequence of buttons which may be the fastest route through the game. I think he was talking more about manually editing the .fmv (or .smv or .gmv or whatever) instead of having to go into the emulator and record as most people do it. This kind of thing would be extremely useful for editing movies, as right now for most people if you find a trick to speed things up near the beginning of the game, you'd have to redo the whole run. By editing the fmv you could just change the input that needed to changed. There's the whole randomness factor to deal with, though, which really complicates things.
That is not what he meant, though I'm sure he didn't mean trying every possibility either. What you are descibing, hex editing, is already a semi-common practice. He's talking about using a computer to find out the keypresses that beat the game the fastest (but not by doing a search tree of every possible combination). Probably what I was taking about before with analyzing the rom. But I know nothing of roms, so I don't know how practical this is.
prower, I do hope you realize, that at 500,000 frames per second, that would take approx~2.44 x 10^4336 centuries?
That would be interesting.
You could rule out select though, it doesn't do anything....
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
You realize that nothing, and I mean nothing, perhaps except for real life, displays 500,000 frames per second? All current rerecording emulators used on this site are 60 fps. There is not a computer in existance that could refresh at such a speed.
Well, you could look at how a game is coded and try to break it down into subproblems. ...Which is basically what people do when they play games for real.
put yourself in my rocketpack if that poochie is one outrageous dude
Much more insteresting than having a computer analyze code, would be to have it analyze the video output and press buttons according to that. The lab I'm currently sitting in does mostly control systems research, including visual feedback systems. This would be interesting to try...
... but it's near impossible. Games are designed by humans for humans. Just take any platformer. What is the object, how do you win? To any human this is obvious - run to the right. To a computer not so. Why should going right be better than any other action? Computers have amazing calculation speed but worthless pattern recogniction, humans are their complete opposites.
Aw jeez, you guys are right. I was thinking the permutation total was 256 * 18000, when in fact it's 256 to the power of 18000.
Even if you take impossible key combinations out of consideration, even if you break the game up into 20-second level-by-level tasks, even if you have a supercomputer capable of emulating 60,000,000 frames per second, it's still going to take until the end of time to exhaust all possible combinations. Just goes to show that humans are still smarter than computers.
I thought some engineers at MIT actually did something like this for The Legend of Zelda. As a result of the output, it was believed that the lowest possible time to complete the first quest for a human was 34:50 (This until a guy named Tom Votava basically came along and said "%*&^ you MIT engineers" and got it down to 34:05. TSA and co. may now be down even lower than that.).
I'll have to search out the topic on Twin Galaxies concerning this.
EDIT: TSA mentions it at http://www.twingalaxies.com/forums/viewtopic.php?t=1288, (Guess it wasn't MIT) but I know there was further discussion on it...
EDIT2: Bah, can't find it now. Of course.
Emptyeye.com- Come for the music, stay for the blog.
I thought some engineers at MIT actually did something like this for The Legend of Zelda. As a result of the output, it was believed that the lowest possible time to complete the first quest for a human was 34:50 (This until a guy named Tom Votava basically came along and said "%*&^ you MIT engineers" and got it down to 34:05. TSA and co. may now be down even lower than that.).
That wasn't brute-force-random. That was an AI.
someone is out there who will like you. take off your mask so they can find you faster.
I support the new Nekketsu Kouha Kunio-kun.
True, though I would personally still classify it as "computer generated input".
Ah well.
EDIT: Some people at a college also built a robot that could play the first level of SMB. I don't recall if it was AI, brute-force-random, or if they simply hard-coded the proper sequence of button-presses, though I think it was the latter.
Emptyeye.com- Come for the music, stay for the blog.
Could be done using pattern recognition copmbined with a re-feedback system (Along the lines of: "See enemy, jump over enemy, try to kill enemy, avoiod fireball, etc.), and since NES games are very low res, an AI could be trained to "see" enemies and try to scan for a possible place to land, then give it the basic rules of the game, and allow it to perfect a combination via evolution. Then leave it be for some time and see what it comes up with.
But the coding involved would be zany, if rather doable with today's techniques.
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
Joined: 3/11/2004
Posts: 1058
Location: Reykjavík, Ísland
Wow, I never realized brute-forcing would be so ridiculusly impossible. It isn't even fesible to brute-force ONE SECOND.
I guess we'll have to wait until we have infinite (litereally) processing power to do that, then.
