Going from emulator input to video is easy, but being able to go the other way would be interesting too. This would be a much simpler problem than trying to brute-force the game, since one would have a large set of video frames to compare with - one knows the input is incorrect at the first video frame mismatch. So a brute force algorithm could be something like this:
* At a given frame, systematically select a test input for this frame.
* Compare the resulting screen with the corresponding frame from the video.
* If they differ, step back and try a new input. If all combinations have been tried for the frame, step back one more frame, and so on.
* Otherwise, keep the input for now and try the next frame.
However, even though this is enormously simpler than trying to brute force the shortest input for the game, I am afraid that this still is far too heavy to be practical. Responses from many inputs are delayed - sometimes by just a few frames, but sometimes by much more - and the time needed for this operation would be O(nframe*2^(nbutton*nlookback)), where nlookback is the number of frames typically needed to see the effect of a button press.
Still, it would be fun to try with a short game with fast responses to input. Any thoughts on this?
Luck manipulation just can not go right this way. It's a nice idea, but whenever I think of any rpg I shudder. Perhaps you'd even manage to get the first 3 crits right in a completely different way and then... well, lets just that nlookback would be very, very, very large.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
It's easy to determine the minimum time it takes for a game to respond to input, so this shouldn't be a problem. Try a large range of inputs and then determine the shortest time the game takes to respond, then the algorithm could take far fewer computations because you wouldn't need to brute force anything initially. You could theoretically process the video in linear time, if every input corresponded to a different rendered frame or piece of music.
However, if it doesn't then this quickly becomes and exponential algorithm. Let's take an example: a cutscene or loading screen. The algorithm would then have a large period of uncertain input. If any luck manipulation or something required, then there would be ensuing problems. But for simple games that don't respond during periods of uncertainty, then I can see such a technique being theoretically possible.
I just had a go at this with Super Mario World, and got stuck when pressing start at the screen where you select the number of players, since there is a delayed fade-out there. And that was when I restricted the input to only the start button too. So the naive version of this seems pretty hopeless.
A possible improvement would be first search up to X frames back for a single frame with 1 button changed, and if that doesn't work, try to search some smaller Y frames back for 2 changed buttons, and so on. If none of those work, extend the search windows and continue. That would be much more difficult to implement, but I expect it would give a huge speedup. But probably still not enough to be useful.
Oh well, it was fun to think about, at least. What I really wanted this for was to recreate the input for the Super Metroid Redesign run, since Saturn has vanished after publishing only the videos.
* At a given frame, systematically select a test input for this frame.
* Compare the resulting screen with the corresponding frame from the video.
* If they differ, step back and try a new input. If all combinations have been tried for the frame, step back one more frame, and so on.
* Otherwise, keep the input for now and try the next frame.
The major problem with this is that if there are some "invisible" key presses being done in the video (which affect the RNG or whatever), the difference they make might become apparent only much later, eg. hundreds or even thousands of frames later. The more frames between the "invisible" key presses and their effect, the (exponentially) longer the algorithm would take to find it.
However, even though this is enormously simpler than trying to brute force the shortest input for the game, I am afraid that this still is far too heavy to be practical. Responses from many inputs are delayed - sometimes by just a few frames, but sometimes by much more - and the time needed for this operation would be O(nframe*2^(nbutton*nlookback)), where nlookback is the number of frames typically needed to see the effect of a button press.
Warp wrote:
The major problem with this is that if there are some "invisible" key presses being done in the video (which affect the RNG or whatever), the difference they make might become apparent only much later, eg. hundreds or even thousands of frames later. The more frames between the "invisible" key presses and their effect, the (exponentially) longer the algorithm would take to find it.
Isn't that just what I said? Anyway, I agree, and I think this brute-force input recreation would only be possible on the very few games where every keypress has a quick, visual response.
Joined: 8/14/2009
Posts: 4083
Location: The Netherlands
Even without an RNG, in a game like SMB as you mention, what about subpixel values? The bot would not see the difference on the screen, but in the game the subpixel values could end up differently which would screw it over sooner or later.
http://www.youtube.com/Noxxa
<dwangoAC> This is a TAS (...). Not suitable for all audiences. May cause undesirable side-effects. May contain emulator abuse. Emulator may be abusive. This product contains glitches known to the state of California to cause egg defects.
<Masterjun> I'm just a guy arranging bits in a sequence which could potentially amuse other people looking at these bits
<adelikat> In Oregon Trail, I sacrificed my own family to save time. In Star trek, I killed helpless comrades in escape pods to save time. Here, I kill my allies to save time. I think I need help.
