Re: Tool-Assisted Highscores/Speedruns
Posted: 2015.01.16 (14:18)
Why wasn't an MBD ever done for 00-4 sr? Is 164 max?
Welcome to the Metanet Software community.
https://forum.droni.es/
Found an incomplete 13-0 mbd on my pastebin: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.
Here you go, I feel like you're still going to run into drones later thoughTheRealOne 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.
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.jp27ace wrote:Here you go, I feel like you're still going to run into drones later thoughTheRealOne 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.
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):TheRealOne wrote: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.jp27ace wrote:Here you go, I feel like you're still going to run into drones later thoughTheRealOne 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.
Very nice! Now lets see how much we can close that gap realtime, saved .800 to start.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.
Holy ****! That looks difficult.jp27ace wrote:Very nice! Now lets see how much we can close that gap realtime, saved .800 to start.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.
It's a pretty poor run but I'll wait to see what Eddy comes up with before I try to improve it.
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.xaelar wrote:Holy ****! That looks difficult.jp27ace wrote:Very nice! Now lets see how much we can close that gap realtime, saved .800 to start.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.
It's a pretty poor run but I'll wait to see what Eddy comes up with before I try to improve it.
Yeah, doing the closer 4-tile requires a faster double and must be a JNJ double.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, I was pretty sure I had, too, but not 100%. A link to a previous discussion about this would be interesting...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.
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.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.
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
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.zapkt wrote: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.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.
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:
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).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
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?