Alpha version 0.5 is out! The latest version of the script can be found here.Purpose:
To minimize the input in an existing movie file. Minimal input is a secondary goal (at best), but I personally find it aesthetically pleasing. I also know it can be very frustrating to minimize a movie's input while making it. It is much easier to hold a direction or set a button to auto-fire than it is to find the exact frame in which to press a button. This script removes all button presses that don't affect a movie's sync.
The script:Download InputMin.lua
Language: lua
localfunctiongetinput()local buttons={}local state1=savestate.create()
savestate.save(state1)for i=emu.framecount(),movie.length()do
emu.frameadvance()-- The address picks up the input set on the PREVIOUS frame.local frame=emu.framecount()-1
buttons[frame]=joypad.get(1)end
savestate.load(state1)return buttons
endlocalfunctioninputlist(buttons)local k=1local buttonlist={'right','left','down','up','start','select','B','A'}local list={}for i=0,#buttons dofor j=1,#buttonlist doif buttons[i][buttonlist[j]]then
list[k]={i,buttonlist[j]}
k=k+1endendendreturn list
endlocalfunctionreadgoldenRAM(goldenRAM)local vals={}for k=1,#goldenRAM do
vals[k]=memory.readbyte(goldenRAM[k])endreturn vals
endlocalfunctiongetgoldenvals(goldenRAM,checkpoint,buttons)local state1=savestate.create()
savestate.save(state1)while emu.framecount()<checkpoint do
joypad.set(1,buttons[emu.framecount()])
emu.frameadvance()endlocal goldenvals=readgoldenRAM(goldenRAM)print(goldenvals)
savestate.load(state1)return goldenvals
endlocalfunctioncomparevals(test,golden)
match=truefor i=1,#test do
match =(match and(test[i]==golden[i]))endreturn match
endlocal checkpoint=movie.length()--[[
Important Dr. Mario addresses:
pill counter: 0x90
pill x: 0x85
pill y: 0x86
virus counter: 0xa4
]]--local goldenRAM={0x85,0x86,0x90,0xa4}local buttons=getinput(inputRAM)local list=inputlist(buttons)
movie.close()print(list)print(#list)local removed=0local kept=0local testvals={}local match=falselocal goldenvals=getgoldenvals(goldenRAM,checkpoint,buttons)print(goldenvals)local gamestart=savestate.create()
savestate.save(gamestart)for i=1,#list dowhile emu.framecount()<checkpoint do
joypad.set(1,buttons[emu.framecount()])if emu.framecount()==list[i][1]then
joypad.set(1,{[list[i][2]]=false})end
emu.frameadvance()end
testvals=readgoldenRAM(goldenRAM)
syncs=comparevals(testvals,goldenvals)if syncs then
buttons[list[i][1]][list[i][2]]=false
removed=removed+1else
kept=kept+1endprint(removed)print(kept)
savestate.load(gamestart)end
How to use the script:
1) Create a movie. It should be short (<1 minute) and it should be a game that you know quite well. You will need to input some RAM addresses. I chose Dr. Mario because it was available.
2) Pick a frame that you want to test for synchronization. By default, this is the end of the movie, but you can change it to any value (before or after the end of the movie). To change it, change the value of "checkpoint" on line 66.
3) Pick RAM addresses to be tested for synchronization. These are addresses whose values you can be certain are important to the movie's synchronization. The more you include, the better... up to a certain point. If you include most/all of the game's RAM values, it will take much longer to compare them and evaluate synchronization. Also, if you include too many addresses, you may include one that is not actually important to synchronization (increasing the number of false positives). Ideally, you want just enough addresses to have zero false negatives (essential button presses that are deemed unessential) and not so many that you introduce false positives (non-essential button presses that are deemed essential). Set these addresses on line 74 in the array "goldenRAM". For my test movie, I included just four RAM addresses corresponding to the following values: pill counter, pill x, pill y, virus counter. Using just these four addresses, my script worked fine.
4) Run the game, pause FCEUX. Load the movie. Run the script.
5) Wait. A long time. The movie will play, removing exactly one input each time. If the movie desyncs, the input is returned in subsequent playbacks. If the movie syncs, the input is permanently removed.
6) As you wait, a few pieces of information will be printed to the Lua console. It will first print a list of every button you pressed in the movie along with the frame you pressed it on, it will then print the total number of button presses, it will then print the values of the RAM addresses that it is seeking to synchronize, and finally, at the end of every iteration of the number of removed inputs followed by the number of kept inputs. After the script is finished running, no data is saved to file (this will be changed in future versions).
Explanation of script's algorithm:
In its current version, the script is just about as naive as it can be. It runs the movie up until the frame specified by "checkpoint". It then reads all the values at addresses specified by "goldenRAM". Next, it plays the movie, removing the player's very first input. When it reaches the "checkpoint" frame, it again checks the values at addresses in "goldenRAM". If any of them fail to match up, the movie is deemed to have desynced and the input is kept (assumed to be essential). If they all agree, the movie is deemed to have synced and the input is discarded.
Results:
I ran this script on a 52 second movie with the emulator on turbo speed. It picked up 839 total inputs. Running the script took about 40 minutes. 713 inputs were removed and just 126 were kept. You can download and test the movie file here. It may actually be faster to just create and test your own movie file...
Things to do...:
1) Make sure the script runs when process is started in the middle of a movie (I think it does, but I haven't checked).
2) Improve compatibility for use in other emulators. It may work in emulators other than FCEUX, but I'm not sure.
3) Save final input to movie file. Well, what good is input minimization if the script doesn't actually produce anything?
4) Technically, the script may need to be re-run several times to truly optimize input. To see why, suppose the input is such that A is held for five consecutive frames but only needs to be pressed on the first frame to produce the desired result. The script will check for synchronization something like this:
AAAAA <-- Original input. No desync.
.AAAA <-- Desyncs. A is pressed a frame later.
A.AAA <-- Desyncs! A is pressed twice!
AA.AA <-- Desyncs. A is pressed twice.
AAA.A <-- Desyncs. A is pressed twice.
AAAA. <-- Syncs. A is pressed once.
In this example, the script would need to be run five times before it could be verified that input can no longer be optimized. To make checking faster, I might break the algorithm into checking "chunks" of button presses so that the whole script doesn't need to be re-run several times.
5) I'm sure there's a way that I can save a state right before input is changed so that it isn't necessary to replay the entire movie. This is just the quick-and-dirty version of the script.
6) The algorithm needs to be improved. I plan on changing it to a method that completes the process in four shorter steps. First, the script will remove random individual inputs from the movie file and check both whether desync occurs and exactly how long it takes. This will be done approximately 100 times and will be used to assemble statistics. These statistics will be used to determine optimal values for tau (expected time to desync) and B (bin size). Second, all addresses are checked individually for desync, up through tau frames. This saves time because desync is checked only up to tau frames, not to the end of the movie. However, there will be some false negatives. These will be caught in the second pass. Third, the presses that seemed to sync in the first pass are assembled randomly into bins (of size B). Each bin is tested for synchronization through to the end of the movie. If the movie syncs, all inputs in the bin are deemed unessential and are removed from the movie file. Fourth, any bins that desynced have their component inputs individually checked through the end of the movie. This is a final, exhaustive search and all inputs are now definitively classified as either essential or non-essential.
I expect programming this will take a while...
7) Other miscellaneous things that I can't think of right now. Make a suggestion!
Try it out and tell me how you like it!
6) The algorithm needs to be improved. I plan on changing it to a method that completes the process in four shorter steps.
That another algorithm sounds interesting. The current one is way too straightforward. But the main problem with the idea is that user has to actually spend manual work searching for those golden RAM addresses. I dunno if I'm too lazy, but the task of minimizing input doesn't seem important enough to figure new addresses for every game, especially since the script only reduces duration of buttonpresses and doesn't minimize the number of times the button state was changed. Maybe, if the performance of the script increases (after implementing the better algorithm) you could spend the processing power on comparing screenshots and thus not always requiring RAM addresses (sure, optionally providing them would allow the script to finish faster).
Bobo the King wrote:
I expect programming this will take a while...
Regarding the development, I suggest using TAS Editor's Lua API, to make the algorithm prototyping easier:
a) the API grants r/w access to input at any frame - use taseditor.getinput() and taseditor.submitinputchanges() instead of joypad.get() and joypad.set()
b) the IDE automatically savestates every frame (can be disabled when not needed)
c) the IDE visualizes the process of the algorithm's work (surely gonna be useful to debug the script)
http://www.fceux.com/web/help/taseditor/index.html?LuaAPI.html
But yeah, since TAS Editor puts some performance overhead, for the final script you may want to switch back to joypad.get/set. But actual making of the script will definitely be quickened by using the newer API.
comparing screenshots and thus not always requiring RAM addresses (sure, optionally providing them would allow the script to finish faster).
Yep, comparing screenshot can be quite fast, but it would be much more faster if emulator provided an inbuilt way to hash the screenshot value with a lua function for it.
Thought, if you want to get rid of "artistic" value of a movie in favor of minimal input, you might prefer using the golden addresses. Ex: The game has some waiting time, so the player use this time to mess around, even thought he could just stay idle while the game prepare more gameplay.
I guess this might be an interesting use case to check later, once the script is good solid enough.
edit:
If you compare the whole RAM, that shouldn't be that long if you directly grab the state of the savestate instead of using memory.readbyte for each addresses.
If you compare the whole RAM, that shouldn't be that long if you directly grab the state of the savestate instead of using memory.readbyte for each addresses.
Yes, but this detect almost every change in input as a desync, as almost always the input state is kept in the RAM.
I dunno if I'm too lazy, but the task of minimizing input doesn't seem important enough to figure new addresses for every game, especially since the script only reduces duration of buttonpresses and doesn't minimize the number of times the button state was changed.
Heh, that is pretty lazy. I think a very simple example of a "golden" RAM address is the character's position. If the character's position at any time differs from its expected value, the movie has almost surely desynced. (This is especially true of the horizontal position in sidescrollers.) It took me about five minutes to find the golden RAM addresses for use in my Dr. Mario movie. Compare that with the 40 minutes it took for the script to run.
AnS wrote:
Maybe, if the performance of the script increases (after implementing the better algorithm) you could spend the processing power on comparing screenshots and thus not always requiring RAM addresses (sure, optionally providing them would allow the script to finish faster).
Blech. I think I'll stick to RAM addresses. They're easier to find and compare, supported across all emulators, and can be a little more "targeted".
There are a few easy ways to use RAM addresses: 1) Use the character's position, as I already mentioned, 2) use an address that signifies a level change, or 3) use an address that's only used in the ending (perhaps signifying the finale music).
AnS wrote:
Regarding the development, I suggest using TAS Editor's Lua API, to make the algorithm prototyping easier:
That sounds really cool! I don't care too much about getinput, submitinputchanges, and savin every frame because my script already works fine without those features (though it could be improved with or without those features). However, I'm curious about how its visualization feature will illuminate different aspects.
I don't think I'll adopt TAS Editor for this project, but I'll definitely keep it among my "tools of the trade". Thanks for the recommendation!
BadPotato wrote:
Thought, if you want to get rid of "artistic" value of a movie in favor of minimal input, you might prefer using the golden addresses. Ex: The game has some waiting time, so the player use this time to mess around, even thought he could just stay idle while the game prepare more gameplay.
That is exactly correct. I would like to try my script out on a game that features some small amount of goofing off and see if it removes the player's fidgeting. There's already a small example of that in my Dr. Mario movie where I screw around on the title screen.
BadPotato wrote:
If you compare the whole RAM, that shouldn't be that long if you directly grab the state of the savestate instead of using memory.readbyte for each addresses.
That's actually a really great idea!
... Except some RAM addresses change values even though they aren't essential to the movie syncing. Here's a simple example: We have a movie of Mario 1 where, for no particular reason, the player has Mario jump and destroy a brick for 50 points. The entire jump can be removed without affecting sync, but the address holding the player's score will have changed. Your idea's very clever, but it ends up throwing out the baby with the bathwater.
I haven't worked on my script for the past few days. My latest insight is that the second pass can be removed entirely if the optimal bin size is less than 1. We'll see if that's likely to occur.
Compare that with the 40 minutes it took for the script to run.
But human time and processing time are incomparable. Leaving a script running for a whole night isn't much of a trouble. Well, I'm not insisting on screenshots, that was just some obvious idea to bring up.
Bobo the King wrote:
That sounds really cool! I don't care too much about getinput, submitinputchanges, and savin every frame because my script already works fine without those features (though it could be improved with or without those features). However, I'm curious about how its visualization feature will illuminate different aspects.
If you're going to store the input in a custom container (instead of the actual played movie), then it won't illuminate this data of course. I guess I was more thinking of how would I make such a script.
Bobo the King wrote:
BadPotato wrote:
Thought, if you want to get rid of "artistic" value of a movie in favor of minimal input, you might prefer using the golden addresses. Ex: The game has some waiting time, so the player use this time to mess around, even thought he could just stay idle while the game prepare more gameplay.
That is exactly correct. I would like to try my script out on a game that features some small amount of goofing off and see if it removes the player's fidgeting. There's already a small example of that in my Dr. Mario movie where I screw around on the title screen.
This is certainly not a problem, since the script shouldn't be working on the whole movie (that would take too much time even with an optimized algorithm). Instead, users should be able to select ranges of the movie to process. (oh, I guess I'm thinking in terms of Piano Roll again, heh)
localfunctiongetinput()local buttons={}local state1=savestate.create()
savestate.save(state1)for i=emu.framecount(),movie.length()do
emu.frameadvance()-- The address picks up the input set on the PREVIOUS frame.local frame=emu.framecount()-1
buttons[frame]=joypad.get(1)end
savestate.load(state1)return buttons
endlocalfunctioninputlist(buttons, startframe, checkpoint)local k=1local buttonlist={'right','left','down','up','start','select','B','A'}local list={}for i=0,#buttons dofor j=1,#buttonlist doif buttons[i][buttonlist[j]]and startframe<=i and i<=checkpoint then
list[k]={i,buttonlist[j]}
k=k+1endendendreturn list
endlocalfunctionreadgoldenRAM(goldenRAM)local vals={}for k=1,#goldenRAM do
vals[k]=memory.readbyte(goldenRAM[k])endreturn vals
endlocalfunctiongetgoldenvals(goldenRAM,checkpoint,buttons)local state1=savestate.create()
savestate.save(state1)while emu.framecount()<checkpoint do
joypad.set(1,buttons[emu.framecount()])
emu.frameadvance()endlocal goldenvals=readgoldenRAM(goldenRAM)print(goldenvals)
savestate.load(state1)return goldenvals
endlocalfunctiongetsilvervals(silverRAM,checkpoint,buttons)local silvervals={}local state1=savestate.create()
savestate.save(state1)while emu.framecount()<=checkpoint do
silvervals[emu.framecount()]=readgoldenRAM(silverRAM)
joypad.set(1,buttons[emu.framecount()])
emu.frameadvance()end
savestate.load(state1)return silvervals
endlocalfunctioncomparevals(test,golden)if#golden==0thenreturntrueend
match=truefor i=1,#test do
match =(match and(test[i]==golden[i]))endreturn match
end
emu.speedmode("maximum")local startframe=0local checkpoint=movie.length()--[[
Important Dr. Mario addresses:
pill counter: 0x90
pill x: 0x85
pill y: 0x86
virus counter: 0xa4
]]----goldenRAM: RAM that's checked at frame checkpoint to ensure synchronization.local goldenRAM={0x85,0x86,0x90,0xa4}--silverRAM: RAM that's checked every frame.local silverRAM={0xa4,0x90}local buttons=getinput()local list=inputlist(buttons, startframe, checkpoint)
movie.close()print(list)print(#list)local removed=0local kept=0local testvals={}local match=falselocal goldenvals=getgoldenvals(goldenRAM,checkpoint,buttons)local silvervals=getsilvervals(silverRAM,checkpoint,buttons)print(goldenvals)local state1=savestate.create()
savestate.save(state1)for i=1,#list dolocal syncsilver=truelocal saveflag=falseif emu.framecount()<list[i][1]then
saveflag=trueendwhile emu.framecount()<checkpoint and syncsilver do
joypad.set(1,buttons[emu.framecount()])if emu.framecount()==list[i][1]then
joypad.set(1,{[list[i][2]]=false})if saveflag then
savestate.save(state1)endend
emu.frameadvance()
testsilver=readgoldenRAM(silverRAM)
syncsilver=comparevals(testsilver,silvervals[emu.framecount()])endlocal syncgolden=falseif emu.framecount()==checkpoint thenlocal testgolden=readgoldenRAM(goldenRAM)
syncgolden=comparevals(testgolden,goldenvals)endif syncgolden and syncsilver then
buttons[list[i][1]][list[i][2]]=false--table.remove(buttons[list[i][1]],list[i][2])
removed=removed+1else
kept=kept+1end
savestate.load(state1)end
emu.poweron()print("Removed:", removed)print("Kept:", kept)print("Now record a new movie from power-on and unpause the emulator.")
emu.pause()for i=0,#buttons do
joypad.set(1,buttons[emu.framecount()])
emu.frameadvance()endprint("Recording complete!")
movie.stop()
emu.pause()--[[
An explanation of the more complicated algorithm:
1) The script picks a random input to test for sync. It removes this input and exhaustively checks
for sync to the end of the movie. It repeats this process until it has 100 samples of essential
button presses. This does two things. First, it compiles statistics on how likely a button
press is to be essential and when desync occurs. Second, it can allow the script to sniff out
"early indicators"-- RAM addresses that consistently indicate desync before the user-specified
"golden" RAM addresses do so. (This has not yet been implemented and has some danger of
generating false negatives.) The statistics are used to determine the optimal values for tau
and B, to be discussed later.
2) The script removes single button presses and then checks for desync up to tau frames. If it
desyncs, the button press is known to be essential and is kept. If it does not desync, it may
be non-essential or it may still be essential (it may cause desync later on).
3) Button presses that didn't desync in step 2 are assembled into bins of size B. This is done by
creating bins and randomly placing button presses that passed step 2 into the bins until they
are full. Each bin is tested by removing all of its component inputs. If the movie syncs even
when the bin is removed, all of its inputs are deemed non-essential and are removed. If the
movie desyncs, these inputs are checked individually in step 4. This entire step can be skipped
if the optimal bin size is less than 1.
4) All inputs in bins that desynced in step 3 are individually tested to the end of the movie. Any
input that desyncs on this pass is definitively essential while any input that syncs is
definitively essential.
How long it takes for the algorithm to execute:
This depends on tau and B and I do not want to leave these values to guesswork. The 100 samples
taken in step 1 are used to create a function I call q(t). This is a non-normalized probability
distribution function in which q is the number of inputs that desync after t frames divided by the
total number of inputs. The probability that an individual input will result in a desync between
frames a and b is then int(q,t,a,b), where int(f,x,a,b) is the integral of f(x) as x goes from a to
b.
Later on, we will see that it is desirable for q(t) to be smooth (differentiable once). For this
reason, I propose integrating it multiplied by a gamma distribution whose mean is t and whose
standard deviation is ~1/10 the movie's length. This should significantly smooth out q(t) to the
point of differentiability.
Let N be the total number of inputs and let T be the length of the movie. Step 2 will take roughly
N*tau time (in frames) to complete. It will leave N-N*int(q,t,0,tau) inputs that still need to be
thoroughly checked in step 3.
The number of bins will be N*(1-int(q,t,0,tau))/B. Step 3 will take roughly
N*T*(1-int(q,t,0,tau))/B frames to complete. The number of bins expected to fail this step is
N*(1-int(q,t,0,tau))/B * [1-(1-int(q,t,tau,T)^B]. We expect int(q,t,tau,T) to be small, so the
binomial approximation can be used to approximate the number of failed bins as
N*(1-int(q,t,0,tau))*int(q,t,tau,T).
Step 4 checks all the bins that failed step 3. This will take
N*B*T*(1-int(q,t,0,tau))*int(q,t,tau,T) frames.
The total time is therefore
f(tau,B) = N*tau + N*T*(1-int(q,t,0,tau))/B + N*B*T*(1-int(q,t,0,tau))*int(q,t,tau,T).
We wish to minimize this function with respect to tau and B. This is achieved by setting its
derivatives simultaneously equal to zero:
df/dtau = 0
df/dB = 0
which reduce to
g1(tau,B) = 1 - T/B * q(tau) - T*B*q(tau)*[1-int(q,t,0,tau)+int(q,t,tau,T)] = 0
g2(tau,B) = int(q,t,tau,T) - 1/B^2 = 0.
Now we wish to solve for g1=0 and g2=0 simultaneously. Again, this is nontrivial, but can be
accomplished using a multivariable form of Newton's method of finding the zeroes of a function.
Our initial guesses are tau_0 and B_0. A better approximation is obtained by taking
[tau_n+1, B_n+1] = [tau_n, B_n] - [g1(tau_n,B_n), g2(tau_n,B_n)]*J^-1
where J^-1 is the Jacobian matrix of g1 and g2, given by
[dg1/dtau dg1/dB]
[dg2/dtau dg2/dB].
The Jacobian is evaluated at tau_n and B_n, then inverted and used to find tau_n+1 and B_n+1. This
process is repeated until the values stabilize.
]]--
Improvements:
1) Added "silverRAM", which works like "goldenRAM" except that it's checked every frame. Because it's checked more often, I maybe should have switched their names. Oh well. You should be careful about what addresses you include in silverRAM because even though the game's state may differ from the movie's state slightly, it might still sync in the long term. As an example of how sensitive it is, I tried including the pill x and y positions in silverRAM when optimizing my Dr. Mario movie and it removed 582 inputs and kept 257, about twice as many as were kept in alpha version 0.3. This is because pills were moved one frame later, though not affecting the overall movie sync. I tested this feature again with silverRAM holding the virus and pill counts and it worked fine.
The effect of silverRAM is that the script's speed is greatly improved. Most essential inputs (inputs that cause desync) are discovered in a few frames. However, silverRAM does nothing to speed up discovery of non-essential inputs.
You may edit silverRAM on line 96.
2) Movie recording added. Sort of. After the script determines all essential inputs, the emulator is paused and it prompts the user to create a new movie. When the user unpauses the emulator, all button presses are written and the movie is closed. Because of different movie formats and Lua functions from emulator to emulator, I will likely keep this method for writing movies unless anyone has a suggestion on how it can be improved.
3) The state is saved right before a new input is tried. This improves the script's speed by (almost always) at least a factor of 2. Sometimes, it's much faster! Most essential inputs are kept after just playing a few frames. All non-essential inputs still need to be checked to the end of the movie, so they take about half as long to check on average.
4) You may choose to optimize a portion of the input. To do so, edit "startframe" on line 83. Only inputs between startframe and checkpoint are affected.
5) This isn't an improvement to the script's functionality, but I included a detailed explanation of the more complicated algorithm in a block comment at the bottom of the Lua file.
Things to do...
1) Check compatibility with other emulators.
2) Include compatibility for two players. (Oops! That's a big oversight!)
3) Re-run script until no further optimization is detected. After optimizing my Dr. Mario movie, I ran the script again on the "optimized" movie and it removed three further inputs. The player can do this manually.
4) Change the algorithm to the more fancy version.
5) Make the buttons list more easily editable. This would allow the player to minimize d-pad presses or A presses or any other combination of buttons. This could be extremely useful if it's expected that the different buttons follow different statistics (e.g., if all A inputs are essential but only 25% of d-pad inputs are essential).
6) As usual, other recommendations are welcome!
AnS wrote:
This is certainly not a problem, since the script shouldn't be working on the whole movie (that would take too much time even with an optimized algorithm). Instead, users should be able to select ranges of the movie to process. (oh, I guess I'm thinking in terms of Piano Roll again, heh)
Already done in the above script!
I'm going to put my script to practical use in the next few hours. Expect an update...
Mostly good news! Although I can't share the demonstration I was hoping to.
I tried running my script on LordTom, Mitjitsu, and Tompa's Super Mario Bros. 3 run in order to demonstrate that even in its current state, it can optimize inputs fairly efficiently. Long story short: it optimized the first two levels quite well but desynced unexpectedly after that. You can download the movie here.
How I made it:
First, I needed to find important RAM addresses in the game. I tried using the RAMSearch function with limited success. Then I turned to this handy list. I decided to use the following addresses for silverRAM:
Map x: 79
Map y: 75
Lives: 736
Powerup state: ED
Powerup state on map: 746
So if any of those failed to match up on any frame, the movie would be deemed to have desynced. By including Mario's powerup state, the script knows the movie has desynced if Mario takes damage or fails to pick up a powerup. I also included Mario's extra lives counter so if Mario loses a life, the game has desynced, but with the added bonus of forcing the script to keep the original movie's theatrics where they collect 99 lives. Notice that I omitted the player's x and y positions to give the script a little more leeway. That means some extra jumps might be removed. I also decided on the following values for goldenRAM:
Level ID1: 7976
Level ID2: 7978
Level ID3: 797A
These correspond to the position on the world map of the level the player has just entered. It would be inefficient to optimize the run as a whole, so I decided to optimize it level by level. If the player isn't in the next level by the end of the segment, then surely the run has desynced. My next step was to determine when the level transitions occurred. I did this by watching the original movie and checking when the player entered a new level. This turned out to be a bad idea (more on that later).
I started the script at 9:46 PM local time. I set "startframe" to 0 and "checkpoint" to 1960. The script finished without incidence at 10:13. There were 2159 inputs in the segment, 791 of which were removed, and 1368 kept. More than one-third of the inputs were unnecessary!
When the new movie was recorded, however, it desynced on the second level. I quickly realized this was because I hadn't set the movie's end to the instant of the level transition. Instead, Mario had already begun running right by the time the script checked for synchronization. This holding right could be removed by the script (Mario's didn't lose lives or take damage) and so the remainder of the movie desynced. I manually edited the frames by copying them directly from LordTom & co.'s movie, then went to fix my checkpoints.
To fix my checkpoints, I needed to know not the approximate time but the instant that the level changed. I did this by creating a new short script:
Download SMB3 level changes.lua
Language: lua
prevID1=0
prevID2=0
prevID3=0whiletruedo
ID1=memory.readbyte(0x7976)
ID2=memory.readbyte(0x7978)
ID3=memory.readbyte(0x797A)ifnot(ID1==prevID1 and ID2==prevID2 and ID3==prevID3)then
prevID1=ID1
prevID2=ID2
prevID3=ID3
print(emu.framecount())end
emu.frameadvance()end
On the exact frame that the level changes, the script prints the frame number to the Lua console. These served as my new checkpoints.
I still had a problem, though. The new movie desynced on the third level. Mario is supposed to boost off of a boomerang bro. but he jumped clear over him. This does not mean there was something wrong with my script! Clearly, some properties of the enemies are on a non-timer-based RNG that is somehow subtly affected by either the user's input or consequences thereof. I could conceivably fix the synchronization process by finding this RNG and adding it to my goldenRAM list. I continued to optimize level 2 in the hopes that the movie would re-sync.
I do not know exactly when I started optimizing level 2, but the script finished at 10:45. I believe it took about 15 minutes to complete. The script found 778 inputs in that segment, 314 of which were removed, while 464 were kept. Unfortunately, my Mario 3 optimization quest had come to an end, since the run continued to desync on level 3. The good news is that it desynced a little bit later; this time, Mario failed to pick up a red koopa, which would later be used to pick up a leaf.
So what are the take-home lessons here? First, be careful when choosing your checkpoints. Make sure there is no input just before them that can be accidentally removed. The player should be doing nothing and the game should be at a sharp transition, such as at a new level. Second, my script works pretty efficiently! If the run had synced, I could probably finish a new level of SMB3 every 30 minutes or so and I could optimize the entire game within five hours. Even in its current form, you can already begin to optimize some games. Third, the desyncing problem should be largely fixed when I change the bot's algorithm. The reason why is because the desync that occurred here was exactly the sort of "nightmare scenario" I was worried about: a subtle change in an unseen RAM address causes a desync far down the line. With the more sophisticated algorithm, even long movies can be checked fairly efficiently to their ends. Many of the removed inputs would still be removed quickly while the kept inputs that caused a desync would be checked alongside many others. Fourth, you should be able to use my script in its current form with no problems as long as you use it to optimize a movie you are currently working on. You can avoid all these problems by optimizing each level before you move on to the next one. Fifth and finally, this hints that games can be automatically scoured for those subtle RNGs. That boomerang bro. and that koopa moved for a reason. Perhaps this will eventually lead to an improvement in SMB3?
So although I really wanted to show you guys a new version of the SMB3 movie with 33% fewer inputs, I think things are working pretty well! I'll continue to update you as I make further changes to the script. Next up: the ambitious task of improving the algorithm.
HappyLee did a very good job of minimizing the input in his record Super Mario Bros. run. He completed the game with just 7407 inputs, but I was able to trim away 131 of them, leaving 7276.
Finally, I have a demonstration of what my script can do! I again used Mario's lives and powerup state for my silverRAM (powerup state was never used because HappyLee collects no items). For goldenRAM, I used the world and level numbers for most segments. For the last segment, I had a lot of trouble deciding what would definitively show that the game had been beaten. I decided to use a few RAM addresses corresponding to Mario's x position and the camera's x position, evaluated at frame 20,000, well after the end of the movie. I once again optimized the input one or two levels at a time. I probably spent 3 hours total optimizing the input.
My movie is not an improvement on HappyLee's! I removed 19 frames from his movie, but there was no input during those frames to begin with! Convention states that Super Mario Bros. movies end at the axe, not at last input. See this post and topic for precedent. I will not be submitting this!
Next up: the ambitious task of improving the algorithm.
Your explanation about the complicated algorithm sound very interesting. Using probability to enhance performance of the guesswork to aim for the minimal input should be handful.
So far, in order to use some advanced math in Lua, I've only found lua-gsl, that might do the work if you don't want to manually implement all the function you need. But since you have to install GSL throught cygwin and generate your own alien dll for windows, I'm not sure if the script would be easily portable.
An another idea would be to use the R programming language to do the math work and use the TCP/IP Rserve server as an network API with this lua client, but I'm not sure either how well it actually work.
Bobo the King wrote:
I had a lot of trouble deciding what would definitively show that the game had been beaten. I decided to use a few RAM addresses corresponding to Mario's x position and the camera's x position, evaluated at frame 20,000, well after the end of the movie. I once again optimized the input one or two levels at a time. I probably spent 3 hours total optimizing the input.
Yeah, at some point when you can't find obvious memory addresses such as flag for a specific "checkpoint/endgame goal" you might use trick like x/y camera position, but at this point you might as well use screenshot to compare if this sync fine, just as AnS mentioned(for 2D games with static sprite+camera).
Also, once you minimize some more movie, I'll suggest you ask to an encoder to produce a couple of comparaison encode to highlight the best of what the script can do.
I am console verifying SMB3 warpless. Right now it desyncs on world 6-castle because the runners treat Mario like a jump-happy buffoon and send him into flames. (How he escapes all the other flames up until this point is beyond me...)
It could have just been a one-off desync. If this script will eventually work for SMB3 though, and if the run desyncs again on console at this point and I can determine it isn't an implementation bug, then you might have a valid use of your script :)
(That said, this level is an autoscroller, so maybe I can fix this part manually...)
