Posted: 10/19/2011 4:08 AM
Post subject: Higher Level Movies
Quote
scubed
Former player
Joined: 7/6/2004
Posts: 155
I was considering how movies could be expressed in higher level terms. Right now, most of the movies are done by humans with only really tricky and tedious parts done by AI. Currently, movies are represented as a sequence of button presses. This is a very low level way of expressing it. When we think of movies, we think of them in terms of events. We think about Mario starting to run, jumping off of a koopa troopa, and landing on a platform. What if we expressed movies this way too? So, this could be implemented by having a script in the sense of a movie script implemented as a LUA script with the emulator. The movie could be divided into discrete steps. Each step would have: 1) What to do 2) When the step was over 3) What constraints have to hold afterwards For what to do, there would be a bunch of standard maneuvers for a game. For example, 1) Have Mario run right with holding right and B 2) Swim by pressing A on certain frames, maintaining X velocity. 3) Press A every time it would advance the text. The idea is that these should be fairly simple and not require large amounts of backtracking. Some backtracking would be allowed for simple optimization, but it should try to keep it much less than in the AI search case, such as getting the large weapon capsules in Megaman 1. This way movies could be tweaked easily. (But, for it to work, there would probably have to be a few parts where it would go out of its way to manipulate a drop or enemy spawn, etc.) To remain tractable, backtracking should be contained within a step, not between separate steps. (But I'm not sure if that would work in practice. It seems that there will be a few parts where it would just get stuck then.) To know when to go on to the next step, a condition would have to be given to know when the current step is done. Some example conditions would be: 1) player.x >= 500 2) player.state == on_ground 3) enemy[1].state == dead 4) enemy[1].drop == weapon_capsule 5) respawn_time < 20 6) at_title_screen 7) level == 8 Since some searching would be involved, constraints can also be given. They can be soft or hard constraints. These can also help with pruning. Obviously, the more searching is involved, the more important these are. 1) bombs.count > 7 2) money > 100 3) ammo == 0 4) hp == 100 5) next_prn & 63 == 35 Some constraints can be put on the whole movie too. That way it will try to enforce that it is a no damage, no dying, or all enemies killed run. For testing, tweaking, and making the movie originally, it would need to be possible to resume making a movie from where you left off in terms of both which step you are on and the input already generated. For reproducability, a fixed pseudorandom number (PRN) seed would be used, and reset for each step. This has some notable differences from other proposals on this site. This is NOT saying that we would need to make a really good AI capable of beating the game entirely on its own. This is about having a middle ground between the two, so a human is still making ("directing") the movie, and the AI is filling in small blanks, which should be much more tractable. Advantages: 1) Easier to splice movies together. 2) Can have very simple frame reference for when events occurred. 3) Can more directly compare different paths. 4) Can update entire movie as new tricks are found. Difficulties: 1) It doesn't exist yet. 2) It requires more programming knowledge, and in that sense is more obscure. 3) Have to track down all of the relevant memory addresses. 4) Have to catalog all of the standard techniques used in the game. 5) Some parts won't fit standard techniques and need custom code. Though, a lot of that has already been done for current tools. The additional parts could well lead to even better tools. If this caught on, the script could be included with the submissions. I realize this is a bit pie-in-the-sky, but figured I should write it down and see what others thought about it.
Posted: 10/19/2011 8:08 AM
Quote
MESHUGGAH
Other
Skilled player (1918)
Joined: 11/14/2009
Posts: 1353
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
NES TASer of 2013 NES TAS of 2013 NES TAS of 2012 NES TAS of 2011
I don't understand what's your point. You are talking about making LUA scripts that uses artificial AI? Please explain it. Otherwise: Use the search function.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Posted: 10/19/2011 1:00 PM
Quote
TASeditor
Editor, Skilled player (1536)
Joined: 7/9/2010
Posts: 1319
Glitchy TAS of 2015 NES TASer of 2014 Speedy TAS of 2014 NES TAS of 2013
MESHUGGAH wrote:
I don't understand what's your point. You are talking about making LUA scripts that uses artificial AI? Please explain it. Otherwise: Use the search function.
I think he means LUA scripts, which allow to find a better route for a TAS. i.e. in Pokemon Yellow run, it would be a script, which calculates the fastet way of beating this game. It's not always the best solution if a text advances, the LUA script presses the button, there are also frame-rules. To improve the entertainment of a movie we should do different actions, like shoot an enemy from far away as possible and the next enemy from near as possible. Lag should be considered.
Favorite animal: STOCK Gt(ROSA)26Sortm1.1(rtTA,EGFP)Nagy Grm7Tg(SMN2)89Ahmb Smn1tm1Msd Tg(SMN2*delta7)4299Ahmb Tg(tetO-SMN2,-luc)#aAhmb/J YouTube Twitch
Posted: 10/19/2011 3:14 PM
Quote
scubed
Former player
Joined: 7/6/2004
Posts: 155
I don't understand what's your point. You are talking about making LUA scripts that uses artificial AI? Please explain it. Otherwise: Use the search function.
AI stands for artificial intelligence. Previously, people have thought about trying to make bigger, more complicated AIs to complete the games. But, those would be very big and complicated. Likely, they would be far from the fastest known times and would take a very long time to do backtracking search too. What I'm proposing instead is a bunch of little AIs, each capable of doing a segment of the movie. They should be much simpler, and in fact similar to what already exists. But, it should be much easier to manipulate a movie if expressed in terms of them. There is nothing in what I said that is LUA specific. But, since that's what FCEUX uses, that is likely what it would be written in.
I think he means LUA scripts, which allow to find a better route for a TAS. i.e. in Pokemon Yellow run, it would be a script, which calculates the fastet way of beating this game.
This also allows putting in domain-specific knowledge that it would be extremely difficult for an AI to figure out. Indeed, some segments are likely to be exact keypresses for lack of a better way of expressing it, such as entering the name in Pokemon which affects which messed up pokemon appear much later in the game. An AI wouldn't figure that out on its own in any reasonable amount of time. Also, note that it wouldn't be for the whole game at once. It would be in short segments.
It's not always the best solution if a text advances, the LUA script presses the button, there are also frame-rules.
This is where the conditions come in. It could check if pressing A on that frame actually causes the text to advance, and only press when it would. For the Chrono Trigger TAS, for example, they only used turbo A since it would be too tedious. But, an AI would be able to do that trivially. There are other tricks that require frame rules, so it could just check the relevant counter to align it properly. So, yes, you would tell it the frame rules, and it would take that into account when searching.
To improve the entertainment of a movie we should do different actions, like shoot an enemy from far away as possible and the next enemy from near as possible. Lag should be considered.
Some of the segments could easily be dance segments, such as the spelling out text in Gradius. As for variety like that, you could specify in the segments how to mix it up, but if such annotations were missing, yes, the movie would be likely to be bland. But, we already have movies doing such things, just at the input per frame level. Instead, we could be doing it at a higher level of abstraction. You could still say to do different maneuvers for variety. As far as optimization factors, most movies would try to minimize enemies on the screen and lag frames directly. So, the simple backtracking search would search for ways that have less lag, yes.
Posted: 10/19/2011 3:25 PM
Quote
Lex
Joined: 6/25/2007
Posts: 732
Location: Vancouver, British Columbia, Canada
This sounds like a heck of a lot of work; writing configurable mini-bots for every section (or gameplay type) within a game. It sounds like it wouldn't be worth the effort to write the bots. When you've written an example, I might feel differently. However, for the record, unlike the other posters in this thread, I completely understood your whole concept. You explained it very well.
Posted: 10/19/2011 5:06 PM
Quote
MESHUGGAH
Other
Skilled player (1918)
Joined: 11/14/2009
Posts: 1353
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
NES TASer of 2013 NES TAS of 2013 NES TAS of 2012 NES TAS of 2011
scubed wrote:
AI stands for artificial intelligence. Previously, people have thought about trying to make bigger, more complicated AIs to complete the games. But, those would be very big and complicated. Likely, they would be far from the fastest known times
This is a typo, right? I don't understand, why would a complicated (I should say "more precise") AI be slower than a simple AI that checks fewer conditions. I think I actually know what you are trying to say and what are you aiming for, but this really, REALLY depends on the situation. Various games needs vastly different approach. Some games are easy to debug, some games only needs some memory checking, there's also where only a simple LUA script needed that shows hitbox. I think that your kind of technique only required on games that has nearly the same physics and gameplay objects throughout the game. But I still didn't get the "higher level" stuff, except if it was what arukAdo explained me (higher level language, not higher level movies).
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Posted: 10/19/2011 7:59 PM
Quote
Kuwaga
Joined: 10/20/2006
Posts: 1248
I think this might be an excellent idea! We already have movie files that usually store the held buttons for every single frame. You could read such a file and as a first step translate the button data into lua-code like this 
frame  55: hold B for 800 frames
           hold RIGHT for 800 frames
frame  88: hold A for 8 frames
frame 150: hold A for 12 frames
frame 855: hold LEFT for 1 frames
frame 856: hold RIGHT for 1 frames
frame 857: hold LEFT for 1 frames
frame 858: hold RIGHT for 1 frames
->
hold(55,800,"b")
hold(55,800,"right")
...
Then in a second step, you could apply some game-specific translations. This would maybe require an AI to identify what's going on on the screen atm or some user input to work well (for context specific glitches, etc). 
frame  55: Run to the right for 800 frames
frame  88: Jump with strength 8
frame 150: Jump with strength 12
frame 855: Wobble for 4 frames
->
--game specific part
function run(length, direction)
  hold(frame,length,"b")
  hold(frame,length,direction)
end
.....
--movie specific part
frame = 55 
run(800,"right")
frame += 33
jump(8)
.....
I think that once a movie has been successfully converted in this way, editting it should become infinitely easier already. Then you could maybe even make the lua script display the commands on screen, maybe in an abbreviated form, instead of raw button presses: 
run ->
run ->, jump 8
run ->
run ->, jump 12
run ->
wobble
This third step would make it easier for somebody who watches a TAS to identify what's going on. If you'd be able to look at and edit the results of the first step next to the emulator window, it'd probably make TASing a bit easier already. If you manage to do the same for the second step, (maybe with some nice visualisation/gui), it'd essentially be macros on a piano roll. Now, that'd have the potential to considerably improve TASing efficiency already imo. Smart macros would obviously be the next step, but I think that even without them this'd be a pretty awesome idea!
Posted: 10/19/2011 9:04 PM
Quote
TASeditor
Editor, Skilled player (1536)
Joined: 7/9/2010
Posts: 1319
Glitchy TAS of 2015 NES TASer of 2014 Speedy TAS of 2014 NES TAS of 2013
Well, this is just input recording via lua, i doubt if there is any advantage from frame-advance input recording. some ram addresses must be considered in the script.
Favorite animal: STOCK Gt(ROSA)26Sortm1.1(rtTA,EGFP)Nagy Grm7Tg(SMN2)89Ahmb Smn1tm1Msd Tg(SMN2*delta7)4299Ahmb Tg(tetO-SMN2,-luc)#aAhmb/J YouTube Twitch
Posted: 10/19/2011 9:22 PM
Quote
Kuwaga
Joined: 10/20/2006
Posts: 1248
If you added a nice GUI with a piano roll, I think it might be totally awesome.
Posted: 10/20/2011 3:21 AM
Quote
scubed
Former player
Joined: 7/6/2004
Posts: 155
Kuwaga: Yes, what you describe is roughly what I had in mind. Note to self: Give examples to be more intelligible. Thanks for giving an example to make it clearer. There is 1 minor difference. For frame 55: hold B for 800 frames you wouldn't want to just give a number of frames. That would still be prone to desyncing. (And is easily accomplished by run length encoding.) Consider if you wanted to go to the end of a platform. Instead of saying number of frames, you could run until the "on ground" bit disabled, then go back 1 frame. So, Segment "Run to end of platform 3": hold right and B while on ground This is similar to your example, but has the extra advantage of working even if there is a different amount of lag. Or, if the previous segment is modified to land on a different position on the platform.
This is a typo, right? I don't understand, why would a complicated (I should say "more precise") AI be slower than a simple AI that checks fewer conditions.
Your question reveals the answer. The more of the space you have to search, the longer it will take. There is also the question of how much domain specific knowledge (i.e. tricks for that game) you feed into the AI. If you don't give it everything that is currently known, it is unlikely to figure much of it out. But, with the small segments approach, you are basically encoding the current best movie, thus it should take almost the exact same amount of time. Even if you fed all known tricks into a more general AI, it is unlikely to produce something as good as the current best movie (depending on the exact type of search it is doing) just for not figuring out how to efficiently put all of the tricks together.
Posted: 10/20/2011 5:39 AM
Quote
DarkKobold
Skilled player (1652)
Joined: 11/15/2004
Posts: 2202
Location: Killjoy
Arcade TASer of 2010 PCE TASer of 2010 Arcade TAS of 2010 Lucky TAS of 2009 Lucky TAS of 2007
scubed wrote:
Segment "Run to end of platform 3": hold right and B while on ground This is similar to your example, but has the extra advantage of working even if there is a different amount of lag. Or, if the previous segment is modified to land on a different position on the platform.
This... this is not a trivial programming problem, in the least. You have to find the memory addresses for speed, the ending pixel of the platform... what if the subpixels change, and therefore change the "X" of the end of the platform? What if there is a lag frame when you planned to jump? This is hours of programming. Whereas, reproducing the input by hand, to run to the end of a platform and jump? Trivial. At this point, as you mentioned, people only use lua scripts for either short segments, displaying pertinent behind-the-scenes information, or brute-forcing certain parts. The reason is efficiency and ease. While an interesting concept, it is far too overwhelming, and is pretty much only theory.
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.
Posted: 10/20/2011 5:53 AM
Quote
Patashu
He/Him
Joined: 10/2/2005
Posts: 4043
This approach only makes sense for a game that isn't hardware-dependant, with a well defined semantical model. Starcraft 2, for example, can store replays as events because it can guarantee determinism. A game as simple as megaman is wrought with oscillating speeds, emulator-dependent amounts and positions of lag and a tiny chance of executing arbitrary logic (which is again emulator dependent and not part of any well defined model). As you've said, bots could be used to do short sections of the game for you - these have already been made and utilized. Why put the cart before the horse? Decide you need a bot that does X, then code everything that the bot needs. Admittedly, I'd love to see the 'higher level movie' for an RPG like final fantasy. Instead of measuring durations in time, you'd timestamp things like 'at RNG #FE, attack CHAOS with BIGGS'. In games where RNG manipulation is easy (advancing it as fast as possible is always trivial) it would be a compact way of describing the run.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Posted: 10/22/2011 11:51 AM
Quote
MESHUGGAH
Other
Skilled player (1918)
Joined: 11/14/2009
Posts: 1353
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
NES TASer of 2013 NES TAS of 2013 NES TAS of 2012 NES TAS of 2011
DarkKobold wrote:
At this point, as you mentioned, people only use lua scripts for either short segments, displaying pertinent behind-the-scenes information, or brute-forcing certain parts. The reason is efficiency and ease. While an interesting concept, it is far too overwhelming, and is pretty much only theory.
I'm totally agree with this, something like this what I wanted to write down but I lack of proper expressing myself (just like this sentence).
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Posted: 10/23/2011 2:46 PM
Quote
AnS
Emulator Coder, Experienced player (728)
Joined: 2/23/2006
Posts: 682
That's interesting idea. Reminds me how Object-Oriented Programming made code better structurized and thus easier to get/more popular. I'm talking about Kuwaga's rendition, because OP sounds too unrealistic. I'll think about further developing these thoughts in TASEdit Markers paradigm.
scubed wrote:
you wouldn't want to just give a number of frames. That would still be prone to desyncing. (And is easily accomplished by run length encoding.) Consider if you wanted to go to the end of a platform. Instead of saying number of frames, you could run until the "on ground" bit disabled, then go back 1 frame.
Usually you don't have formal rules, instead you have desired chain of events that must be considered when recording even first event. You don't run all the way until ground ends, usually you run just enough for jumping to land you safely on next platform. Also most events are too vague to express verbally. What's exciting about TASes, most of time you don't have enough words to describe what you want from the AI to do. Watch latest Megaman movie - can you possibly express what's going on there? And sometimes you don't even know what exactly you want to do with the game, because you don't know what you can do with it. So you must experiment until satisfaction, and meanwhile record TAS manually. Example: "Run right until the point from where high jump will possibly lead Mario into floating Koopa, so that he will bounce just in time to miss Bullet Bill and look cool when doing it, maybe also shoot that Koopa from behind or make enemies collide or something better, whichever will look more entertaining" But here's what can be done in similar fashion to the idea: If TASer can divide his movie into verbal parts (not for AI, but for himself or for TASing partner or movie watchers), then he can move his scope to higher level of abstraction. For example, he can navigate his movie by jumping from Marker to Marker, not just from one frame to another. Actual keypresses must still be done by human, but now it will be possible to find similarly named chunks and copy/paste them around (aforementioned macros). What's important: TASer should be allowed to enforce his own logic of dividing movie into parts. Some people like to go deeper than others. It's also very game-dependent. So. AI and bots aside, current TASing process can be enhanced a lot, and this idea is one of good examples.