Page 17 of 20

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.01.16 (14:18)
by ska
Why wasn't an MBD ever done for 00-4 sr? Is 164 max?

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.06.04 (22:36)
by Raif
alsojp27ace wrote:13-0 highscore (123.200):


I struggled to get a decent trajectory off that final cj, I'm sure there are still frames left in this level.
Found an incomplete 13-0 mbd on my pastebin:

Was originally doing this which turned out to be slower,


faster with rcj:

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.06.05 (02:18)
by ska
Very nice.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.08.28 (21:32)
by jp27ace
TheRealOne wrote: Edit: 95-4, Sticking this here so I don't lose it on my HDD. I was attempting to think up a real time method for skipping waiting for the drone at the start. This works, but is way too hard for real time.
Here you go, I feel like you're still going to run into drones later though

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.08.29 (01:33)
by TheRealOne
jp27ace wrote:
TheRealOne wrote: Edit: 95-4, Sticking this here so I don't lose it on my HDD. I was attempting to think up a real time method for skipping waiting for the drone at the start. This works, but is way too hard for real time.
Here you go, I feel like you're still going to run into drones later though
Ah. I did not foresee those two drones coming down the wall in unison like that. So in order to not wait at the start you would have to redo the gold collection route. Bummer.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.08.29 (08:35)
by jp27ace
TheRealOne wrote:
jp27ace wrote:
TheRealOne wrote: Edit: 95-4, Sticking this here so I don't lose it on my HDD. I was attempting to think up a real time method for skipping waiting for the drone at the start. This works, but is way too hard for real time.
Here you go, I feel like you're still going to run into drones later though
Ah. I did not foresee those two drones coming down the wall in unison like that. So in order to not wait at the start you would have to redo the gold collection route. Bummer.
I don't think I'm insane enough to try and pull off this and the start all in one run (incidentally, I had already redone the gold collection):

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.04 (17:18)
by Raif
95-4: 147.450 (4.975 faster than Eddy)


Would be faster if I could get Eddy's speedrun ending at the end.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.04 (17:28)
by aids
You guys are wizards.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.04 (19:36)
by EddyMataGallos
Woah, awesome. To get that ending I presume you have to get a little bit higher than the switch.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.05 (11:36)
by jp27ace
Raif wrote:95-4: 147.450 (4.975 faster than Eddy)


Would be faster if I could get Eddy's speedrun ending at the end.
Very nice! Now lets see how much we can close that gap realtime, saved .800 to start.
It's a pretty poor run but I'll wait to see what Eddy comes up with before I try to improve it.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.05 (11:45)
by xaelar
jp27ace wrote:
Raif wrote:95-4: 147.450 (4.975 faster than Eddy)


Would be faster if I could get Eddy's speedrun ending at the end.
Very nice! Now lets see how much we can close that gap realtime, saved .800 to start.
It's a pretty poor run but I'll wait to see what Eddy comes up with before I try to improve it.
Holy ****! That looks difficult.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.07 (00:51)
by TheRealOne
xaelar wrote:
jp27ace wrote:
Raif wrote:95-4: 147.450 (4.975 faster than Eddy)


Would be faster if I could get Eddy's speedrun ending at the end.
Very nice! Now lets see how much we can close that gap realtime, saved .800 to start.
It's a pretty poor run but I'll wait to see what Eddy comes up with before I try to improve it.
Holy ****! That looks difficult.
Nice Raif! That is a hell of a run. The timing on the double jump up the middle slop is great because of the drone. You just sneak right ahead of it to finish out the run.

jp, that route is nice and that switch grab around the drone is crazy, that had to be a run killer constantly before your 0thed. Nice job.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.08 (17:27)
by TheRealOne
20-4 SR:


I was bored and made a crappy FBF run of this route. The whole run is sloppy, but I just wanted to experiment with the corner jump ending rather than the double jump on the left 4tile/wall.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.08 (19:26)
by EddyMataGallos
Nice innov over there, I'm interested in the fact you used the previous slope to do the double jump, which saved a lot.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.09.09 (00:22)
by TheRealOne
EddyMataGallos wrote:Nice innov over there, I'm interested in the fact you used the previous slope to do the double jump, which saved a lot.
Yeah, doing the closer 4-tile requires a faster double and must be a JNJ double.

Here is a bit better run. Ending still sucked.

20-4 SR 339f

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.12.08 (22:58)
by shomman
How I imagine Raif when he makes his MBD's: https://youtu.be/3vAnuBtyEYE?t=6

Re: Tool-Assisted Highscores/Speedruns

Posted: 2015.12.09 (20:13)
by EddyMataGallos
Ahahahah damn, that's a pretty good one.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.14 (15:21)
by zapkt
Has anyone ever thought about using more advanced techniques to produce N TAS? I'm thinking about basic machine learning methods. There are some existing tools (such as this one for NES games, even though it's not speedrun-oriented). N levels are pretty simple: you need to get to the door with the highest possible time. Opening doors and avoiding traps requires some planning that may be quite hard to handle, though.
The fact that the game is coded in flash makes me quite reluctant to work on this... I can't even run the game on Linux (but I haven't tried much). (Edit: why didn't I simply try wine before?)

Also, dropping a ninja on a bounceblock and bruteforcing all possible inputs may reveal some crazy unknown bounceblock jumps (triple-then-side-jump? who knows). It must be easy to automate if you have a program run different sessions and check for the ninja's maximum speed or position in each session.

I guess Unreality knows a lot about how to hack N to do such stuff

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.14 (18:17)
by ska
Zapkt! Long time no see!

To answer your interesting question, I, and I'm sure others on this forum, have considered machine-learning algorithms; in fact, I wouldn't be surprised if this has been posted before. I, too, am aware of the so-called machine-learning techniques employed to complete Super Mario Bros. One of the big pitfalls I forsee with N is its non-linearity. Super Mario Bros. is a good candidate for brute-force learning because of its simplistic goal. N has a number of waypoints and complications that would make an AI struggle to complete all but the most trivial of levels.

Consider the following: take a level that has a current speedrun 0th of 500 frames. Now imagine the possibilities after a single frame input; there are 4: left, right, jump, nothing. After 20 frames, there are already more than a trillion possible states; after just 5 more inputs, the possibilities are more than a quadrillion. In just 3.5 seconds, you'd have more possible states than there are atoms in th entire known universe, according to my calculations. Short of advanced parallel quantum computing, such a feat seems impossible. I estimate that there are about as many possible chess positions as there are states in N after just five seconds, and chess isn't getting solved any time soon. There may be heuristics, like in chess, which could be used in tandem with brute-force calculation, but this is purely hypothetical, since my programming experience is very limited.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.14 (22:45)
by EddyMataGallos
I stumbled across this topic some time ago, but I think N might too complex for that, specially compared to e.g. mario, so it would have to be very cleverly coded to make it plausible with today's computing power. I'd friggin' love to see it though, and I'm noone to talk about computing anyways as it's just a hobby for me so I hope to be wrong.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.15 (08:56)
by ska
EddyMataGallos wrote:I stumbled across this topic some time ago, but I think N might too complex for that, specially compared to e.g. mario, so it would have to be very cleverly coded to make it plausible with today's computing power. I'd friggin' love to see it though, and I'm noone to talk about computing anyways as it's just a hobby for me so I hope to be wrong.
Yeah, I was pretty sure I had, too, but not 100%. A link to a previous discussion about this would be interesting...

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.15 (11:33)
by zapkt
ska wrote:Consider the following: take a level that has a current speedrun 0th of 500 frames. Now imagine the possibilities after a single frame input; there are 4: left, right, jump, nothing. After 20 frames, there are already more than a trillion possible states; after just 5 more inputs, the possibilities are more than a quadrillion. In just 3.5 seconds, you'd have more possible states than there are atoms in th entire known universe, according to my calculations. Short of advanced parallel quantum computing, such a feat seems impossible. I estimate that there are about as many possible chess positions as there are states in N after just five seconds, and chess isn't getting solved any time soon. There may be heuristics, like in chess, which could be used in tandem with brute-force calculation, but this is purely hypothetical, since my programming experience is very limited.
That's what machine learning is all about: it's basically statistics to try to guess what the most probable best outcome can be without testing all possibilities. Look: Google just happened to write a software able to beat the top-human player at go, a game which is all about combinatorial explosion of possibilities (each step does not have just 4 possibilities, but over 300). Besides, there's an issue in your calculation: don't forget that some inputs have equal effects in some contexts, which reduces the number of possibilities. For instance, if you just hit a bumper, pressing jump or nothing will yield the same result.

When I think about it, there are several use case for automating N, some of which are easier to reach with ML. Trying to get an IA to finish a level all by itself will indeed be a pain because it requires a lot of planning and understanding the mechanisms of the game (the author of the mario IA spent a huge time trying to get mario to go back a few steps to get out of a trap - so imagine trying to get N to understand how to open doors). However, trying to improve a run is a different story and seems way easier to me.
Here's a simple algorithm that may produce some results:

Code: Select all

Input: best 0th/MBD run of a level
At each frame, try to bruteforce possible inputs for a few frames, until you find a solution which transports N to the same (x;y) position as the current best solution in a shortest time, or with a bigger speed
Of course this is a first draw which requires more thinking to be usable, but you see the idea (bigger speed is not always better, and deciding what "a few frames" means is tricky, as looking at a low number of frames in the future may lead N to unavoidable death).
Such an algorithm would focus on improving existing runs through local optimizations. Finding new route is incredibly complex and probably requires actual intelligence (I really doubt a random search would produce anything good).

A first step to such automating could be a graphical tool where users could indicate a position where the ninja should be in a few frame, and the tool would automate trying the different possibilities, which would pretty much be an automation of what MBD writers currently do.

MBD writers, how do you currently do? Do you have some kind of tool more advanced that N + a text editor? A (non-graphical) tool taking level+demo data as input and returning position, speed, time and death-situation of the ninja by executing a frame of the game without speed restriction would be a huge help. I don't know how hard that is to do, as I never attempted to reverse the game. Does Unreality have any idea?

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.19 (10:39)
by ska
zapkt wrote:
ska wrote:Consider the following: take a level that has a current speedrun 0th of 500 frames. Now imagine the possibilities after a single frame input; there are 4: left, right, jump, nothing. After 20 frames, there are already more than a trillion possible states; after just 5 more inputs, the possibilities are more than a quadrillion. In just 3.5 seconds, you'd have more possible states than there are atoms in th entire known universe, according to my calculations. Short of advanced parallel quantum computing, such a feat seems impossible. I estimate that there are about as many possible chess positions as there are states in N after just five seconds, and chess isn't getting solved any time soon. There may be heuristics, like in chess, which could be used in tandem with brute-force calculation, but this is purely hypothetical, since my programming experience is very limited.
That's what machine learning is all about: it's basically statistics to try to guess what the most probable best outcome can be without testing all possibilities. Look: Google just happened to write a software able to beat the top-human player at go, a game which is all about combinatorial explosion of possibilities (each step does not have just 4 possibilities, but over 300). Besides, there's an issue in your calculation: don't forget that some inputs have equal effects in some contexts, which reduces the number of possibilities. For instance, if you just hit a bumper, pressing jump or nothing will yield the same result.

When I think about it, there are several use case for automating N, some of which are easier to reach with ML. Trying to get an IA to finish a level all by itself will indeed be a pain because it requires a lot of planning and understanding the mechanisms of the game (the author of the mario IA spent a huge time trying to get mario to go back a few steps to get out of a trap - so imagine trying to get N to understand how to open doors). However, trying to improve a run is a different story and seems way easier to me.
Here's a simple algorithm that may produce some results:

Code: Select all

Input: best 0th/MBD run of a level
At each frame, try to bruteforce possible inputs for a few frames, until you find a solution which transports N to the same (x;y) position as the current best solution in a shortest time, or with a bigger speed
Of course this is a first draw which requires more thinking to be usable, but you see the idea (bigger speed is not always better, and deciding what "a few frames" means is tricky, as looking at a low number of frames in the future may lead N to unavoidable death).
Such an algorithm would focus on improving existing runs through local optimizations. Finding new route is incredibly complex and probably requires actual intelligence (I really doubt a random search would produce anything good).

A first step to such automating could be a graphical tool where users could indicate a position where the ninja should be in a few frame, and the tool would automate trying the different possibilities, which would pretty much be an automation of what MBD writers currently do.

MBD writers, how do you currently do? Do you have some kind of tool more advanced that N + a text editor? A (non-graphical) tool taking level+demo data as input and returning position, speed, time and death-situation of the ninja by executing a frame of the game without speed restriction would be a huge help. I don't know how hard that is to do, as I never attempted to reverse the game. Does Unreality have any idea?
Well, I was well aware that there would be certain positions where pressing jump or holding nothing would yield no difference, but the difference on the game's exponential factor is essentially negligible. Your suggestion about brute-forcing existing MBD runs does, however, strike me as plausible, especially with your suggestion to try tree attempts with x,y comparisons. N has so many nuanced manoeuvres, though, which might be a stumbling block. Still, I can't see why a well-written program couldn't shave off a few frames here or there from a pre-existing run.

P.S. The last time I checked, Raif, Eddy (and maybe TRO) used Excel to chart inputs.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.19 (18:49)
by EddyMataGallos
Yeah we use a spreadsheet to specify the keys pressed in each frame of a 7 frame chunk and it calculates the resulting code for that chunk. I attach the spreadsheet I use, it only has 25 chunks because I rarely require to go back and modify something more than 25 chunks behind. I also attach the spreadsheet that breaks down how this values are calculated (it's not necessary, just for informative purposes).

As far as I'm aware this is the highest technology anyone has ever used for MBD'ing, although I'd have to ask Raif for that.

Re: Tool-Assisted Highscores/Speedruns

Posted: 2016.07.19 (22:41)
by jp27ace
Here's the spreadsheet I used for making my MBDs.
It has a section for generating a 7 frame chunk of your choosing, as well as handy buttons for commonly used chunks and copying/deleting.
I had a better version but its been lost somewhere, this was the latest one I could find.
Hopefully the macros work on your versions of Excel.