Nice work. This is better than what I made- even the second time. Maybe we could co-TAS the rest of the game. I had some detailed farming routes I could share. The route spreads out spawns so that you don't have too many at once and gets EXACTLY the right amount of gold for extra swag. I can't remember how far I planned it though. (EDIT: Looks like I planned farming in detail up to level 4)
I also wasn't aware that the JP version didn't have that map bug. I should get me a JP ROM and play it.
PRE-EDIT: (I still have my old project file. I haven't worked on it in probably over a year due to TASStudio crashes. Those might be gone with BizHawk 2.x...
Just lacking motivation.)
I ended up using Bayes for type inference (which is all I really had time for - no "interesting" detection mostly partly I really had no idea how to objectively define an "interesting" address- maybe I should have used a neural network?), but it ended up not working at all. I probably needed a better model to determine the likelihood of data given a type as it really ended up only finding volatile addresses and calling them u32s and u16s. It was also really slow, so that was kind of a bummer.
I'll put up the paper I wrote at some point so that you know what doesn't work.
On the other hand, I was able to make a really straightforward and fast LFSR RNG detector which easily detected the known RNG in SMB3 and found some currently undocumented likely RNG addresses in Dr. Mario (0x00EA-0x00EB) and Zelda 1 (0x0017-0x0023).
You can get my LFSR detector here. You will need Python 3 and numpy to run the analysis tool and (naturally) Bizhawk to dump RAM from a game. I ended up not using pipes. Maybe I will someday.
I'll put it up on GitHub eventually. I'm just feeling lazy right now.
First, what kind of output do you want to get? Should this problem be solved with classification or regression? Classification would imply to define some categories such as: this byte(the value of an address) is being labeled as "some-behavior/relationship".
I was planning on doing a classification-ish of "most interesting addresses" Hopefully, this finds things such as position, HP, RNG seeds, velocity, etc... Though I'm not exactly sure how to go about this. I could have it track patterns and trends and that would probably get a good starting point. Then I could feed addresses found with that into another script that tracks which memory addresses were read immediately before writing to those.
It would be doubly cool if I could not only label addresses as interesting, but give a good guess of what the address actually represents. Humans would probably have to correct it most of the time, but it would probably help analysis.
I originally planned on finding correlation, but I quickly realized that would scale poorly- requiring at least 32 MB to analyze an NES game (4 million address pairs, 8 bytes for a double-precision float each)
While that would probably work for non-real-time analysis of NES and maybe SMS games (requiring 512 MB for correlation analysis), it pretty much explodes if you want to do realtime analysis or later generations. Using single-precision floats wouldn't help deal with the issue of scale.
BadPotato wrote:
Since there's a decent database of labelled memory for the NES collection, in order to do actual training, you will probably have to record some gameplay session, then dump the ram data while filtering useless data(such as constant).
I was planning on using that as comparisons so I can figure out what works well.
BadPotato wrote:
Getting the data is a problem.
I plan on using Lua scripts to dump RAM at every frame, making this pretty breezy. It would probably make sense to throw in joystick input as part of the data as well. This might slow down emulation a bit, though probably not enough to be an issue.
BadPotato wrote:
Another almost completely different idea(maybe easier to do):
Right now, with our current tools we don't even know right away if a set of consecutive byte is actually a long, int, short, word, byte, etc(well, despite you check directly how the disassembler write his info), does a byte is signed or unsigned? Maybe it would be easier to simply tag what kind of data bytes any given byte is. Also, to do this you may not need a large dataset as input(number of columns), you simply need some of the adjacent bytes. Then, for F numbers of frames(of actual gameplay) you can try to predict the datatype for a byte.
That is a good thought. This could cause hiccups in analysis as it is. This might need to be solved before much other progress can be made. I'd imagine that larger datatypes are typically aligned to their size, though that assumption may not be true on 8-bit hardware. Then there's the matter of endianness to worry about.
That being said, what kind of ML frameworks did you intend to use?
Probably Numpy since I'm mostly just doing analysis right now (the class is more focused on big data analysis than actual ML). I'm not exactly sure if Neural Networks would help much. That's already sort of been done before with some interesting results.
There's going to have to be two-way communication somehow, as some work will have to be done by Lua (disassembly and event hooks)
Does Lua's popen allow r/w pipes, because that would be, by far, the simplest way to handle 2-way talking. I know you can do read-only and write-only pipes, but it isn't very clear in the documentation. (Also, does BizHawk even support popen?)
Alyosha wrote:
tracing RNG usage: as feos mentioned, finding RNG is not so difficult. Finding all the things it impacts though can be more time consuming. If you could automatically make some lists of what values RNG impacts (and even indirectly impacts) that might be really useful.
This requires disassembly for sure, but I have an idea of how to automate this process somewhat.
Alyosha wrote:
Finding object tables: Usually enemy/sprite/player data used by a game is clumped into tables in RAM, if we could automatically get lists of object slots, hit boxes, attributes, and such that could save a lot of time.
That is a great thought. I was hoping to be able to do this sort of thing.
It also points out that related data tends to be clumped together, which probably would help with automated analysis.
-----
Thanks everyone for the responses so far and keep it coming!
Oh... That's good to know.
Sorta leaves me with less of a project though. Or I guess it just calls for a change of direction.
I still wonder what kinds of other patterns can be gleaned from throwing data science at the system RAM. It might turn out to be fruitful for something unexpected.
I'm currently in a data science / machine learning class, and I just got approval for a final project to analyze RAM in NES/SMS games for patterns. I'm hoping it can make finding interesting memory addresses easier or potentially allow us to find more than we could before, for instance abstract things like RNG.
We currently have RAM searching, but it's a little primitive. It works well for some things where you expect a specific value or a clear change, such as position or HP. However it's a bit more difficult to find more elusive things like RNG, leaving us to throw spaghetti at the wall with rerecords until we get what we want.
I would be doing this programmatically, so that makes it a bit challenging to find more interactive memory addresses. Point is, I need a way to objectively define in a general sense what an "interesting" memory address is.
I have some thoughts on what an interesting address might be:
* It affects the value of many other memory addresses from frame to frame. This should identify things such as velocity, input, and (maybe) RNG. Inferring these kinds of relations would require a quadratic amount of memory and time on the total amount of input RAM and therefore probably can't practically scale beyond 2Kb (NES) unless you can do some serious filtering on which addresses you include in the search.
* An address that holds a predictable value that isn't constant. It might be periodic or it might be affected by other memory addresses. Periodicity would be mostly reasonable if you bound it and wouldn't explode as much as a dependency network/matrix.
* ...? Not sure what else
(In case you couldn't tell, I'm really interested in finding RNG seeds)
I could use some ideas on how to approach this. They probably should have linear complexity on space (for those of you who are not well versed in CS, that essentially means that I can't reasonably bookkeep on every possible pair of addresses) or be able to filter out temp values such as stack data. It would be ideal to be able to scale this to memory sizes larger than 2 Kb.
I will keep that in mind, but It's going to be a while. I probably won't finish my current TAS (Golvellius SMS) until a month-ish after summer starts.
I'm pretty pumped though. I might work on both at the same time actually.
I would have to say that all previous posts about this game not being worthwhile to TAS because it's just a reskin of Kirby's Adventure are a bunch of hot air. I see your point, but I just don't think it's a good reason.
I'd have to say that throwing a remake out because "the original is better" is one of the worst excuses you can do for speedrunning. Think about the number of crappy games that are speedrun just because... For all we know, this game could have some other exclusive glitches and tricks that aren't around in the NES version- ones that will never be found because someone doesn't think it's worthwhile. (Some remakes are actually BETTER for speedruns. Take WWHD for instance- only 2 minutes slower without having to deal with Tingle tuner nonsense... and getting faster.) Also, given the lack of the UFO glitch, that should be enough for it to count as a different category in its own right.
On top of that, why aren't there official submitted versions of the boss rush and Meta Knightmare? It would be SOOO easy to make a verification video for that- taking about 3 hours for a casual RTA speedrunner like myself. I mean for Pete's sake, we have a verification for Chrono Trigger New Game + and that had to have taken a lot longer.
[/rant]
As soon as I'm done with my current TAS, this will be my next project. I should easily be able to beat the current RTA WR of 44:00 by at least a minute. IDK exactly how much; I need to get Kobral's splits to find out. (and I will use his current WR video for reference)
I'm running this whether you like it or not and I'm going to try my hardest to make it interesting to watch.
I've totally laid waste to Bachular/Taruba, the third boss, and I have things done up to the Valley Sword (the one that does 3x damage in the overworld and 2x to bosses)
Bachular is a joke to TAS and is no problem at all to 3-cycle (something that would require amazing luck to pull off in an RTA) You can literally manipulate him to spawn in basically the same place. It also turns out that his hitbox disappears on the frames where he's vanishing (but not completely), so I took those opportunities to refresh the sword. I'm not sure if spawn wait times are manipulatable. I might have to experiment.
WIP is coming along.
My only constructive criticism for you here is that there still seems to be some little things that you could be doing to shave down some more time. I noticed that my test WIP from your prior submission thread is still 21 frames faster at the stopping point where the first money upgrade is obtained.
hmm. Interesting. I probably should have based my run off that. I got A LOT more meticulous starting in the second dungeon though.
I'm not saying that means you have to now go back and re-do everything again!
Thank goodness. Those 21 frames would completely WRECK the RNG manipulation. There's also no telling if optimizing that beginning would actually help in the long run, as a slower start could theoretically set up later parts for better RNG setups. Obviously we're dealing with an exponential problem here... so yeah. I'm assuming this and some other rules set me up for a much more likely approval. :D
I don't know what the rules on multiposts/BUMPs here are (I should probably check that...), but I've made more progress and it's really disappointing to see that nobody has pitched in their two cents.
I have everything completed up to the third dungeon
The game I'm currently TASing is Golvellius for SMS. I figured out that at various specific frames, inputs influence enemy spawns, which turns out to be extremely helpful for the run.
I haven't actually figured out where the RNG is in memory, but I have an idea of how to go about finding it. (Any tips BTW? My idea is to find one of those frames and then see what changes when I change inputs until it narrows down to one memory address)
Here's basically how it would work:
You give it a frame to try all possible inputs on. (you would find the frame where input influences the RNG)
It runs all possible inputs, advances n frames on each iteration, and takes a snapshot and/or savestate and/or outputs the value of a RAM address. You can then review all of the outcomes and their inputs and then choose the input you want.
This solution is O(n^2) O(2^n) where n is the number of inputs you enable it to test. This is pretty feasible for a single frame, MAYBE 2 (though that wouldn't likely help), and you could reduce the number of possibilities as well by allowing the user to put constraints on the input. (such as make sure the Up input is on and the pause input is off)
Obviously, this is a lot easier than doing it manually.
I will probably make a proof of concept at some point and use it in my current WIP if it works well. If someone wants to beat me to it, you're more than welcome to do so. It might be a while until I get to it; I'm not on Windows super often.
It's been a couple months since my v2 (rejected) submission and today, I finally decided to hop over to my Windows side to work on v3.
Well here is my work in progress. I've finished up through the first boss.
Comments/critiques/suggestions would be appreciated.
Also, any advice on making the autoscrollers more interesting to watch? All I have right now in the swag department is killing 2 bats at the same time and dodging like 6 bats on the screen (which I don't think lags the game - how would I measure that?. Lag frames don't seem to register most of the time in this game). There has to be something more exciting I can do there...
I'll probably chip at this again next weekend if I have time. Maybe sometime during the week too.
EDIT: I figured I might as well throw another hour at this. Now I'm up to the first boss. I don't want to get too ahead of myself though. RNG is a pain to manipulate.
I submitted "v2" a couple weeks ago and I'm working on polishing up the route, even down to the farming route (to get exact amounts)
Map/Route
I currently have the farming planned in detail up to the third dungeon.
Does anyone know of any useful glitches?
I've found 2 for the platforming caves:
- If you get knocked back, you can move forward as soon as you touch a wall behind you
- You can crouch in midair by stabbing and holding down during the animation until the your sprite begins crouching. This happens to also reduce knockback as well.
I've been working on improving my route and I actually found a couple of improvements already- just from moving differently between screens. The improvements so far are well above a second. Maybe 2. I'm also working on optimizing the farming route. I'm not sure how much faster it is yet, but it's at least a lot more efficient.
Yeah... I'm going to start the WIP thread now.
I could see how more detailed planning would help. I basically just went with the flow. RNG didn't need to be manipulated everywhere (and in many cases, it was just to make sure that no enemies were in the way), though it could be used a lot better in the extended grinding sections. I think at this point, that's where the biggest improvements could be made.
Yeah, you can go ahead and reject it. I'll open up a WIP thread for this game and chip away at a superior run over the next few months. I suppose it takes more than a week to make a great TAS.
Is there any reason you kill all the enemies along your path in the very first sidescroller area? There's no mention of it in the submission text and it looks like a lot of time can be saved by just skipping them. The sidescroller segments in general seem like they could use a bit more work as well, though what I'm seeing as suboptimality might just be the game itself. Your boss strategies seem inconsistent: Sometimes you do single hits and other times you hold out the sword to do 2 hits in one swing. Are they both the same speed?
For the optimal gold route, I need to kill 180G worth of enemies in that cave- and that's about as many as are conveniently in the way. There is a possibility of getting less and just killing an extra enemy or two in the overworld, though due to spawning times, that is not likely to save time. I suppose I could try to figure that out, as you can manipulate the spawn timers. Getting the right type of spawns can be difficult, especially since I couldn't find the RAM location that determined enemy spawn types.
The blue worm thingies have 2 health, whereas the red snakes only have 1, so I have to hold the sword out longer (see my post on how damage works) to kill them.
You seem like you know the game well, and it's great that you submitted your second effort instead of your first, but I'd still recommend giving it another shot just in case. You mention yourself that 30 seconds can possibly be saved, which is pretty significant even for a longer run like this. I'd also recommend interacting with the forum a bit more instead of posting finished runs: Post your works-in-progress, explain what you're doing and why you're doing it, ask people for advice if need be. For a first-time TASer, it's still a good effort! It just needs that extra push to be great.
It's probably going to be a while before I make another attempt, but I suppose that's fair. It's just annoying when I discover how useful certain glitches are halfway through the run...
I hope it gets accepted anyway since I didn't really think of the improvements until after it was too much of a pain to fix them, but I do plan on obsoleting it within the next 6-8 months, sooner if I can get BizHawk working on Linux, so it wouldn't be heartbreaking if it didn't make it.
I will keep your advice in mind though. I'm not sure what game I'll TAS next or when that will happen, but I'll open it up to the boards when it does.
Your input is lazy you hold down for way, way longer than you need to when attacking, your movement is sloppy.
This is actually intentional. The way damage works makes this necessary. There is an invincibility counter that drains only while the sword is touching. This is actually the fastest way to do damage.
And the movement looks sloppy mainly because you're stuck to the 8x8 grid. It's very difficult to work with. That, and sometimes the weird movement is used to manipulate RNG.
EDIT: also note that I'm not sure if the route change I'm thinking of would actually save time. AFAIK, other than a few minor things here and there, there is very little room for optimization. More meticulous RNG manipulation might help, though not likely by much.
I made a proof of concept TAS. It's a little sloppy, so I'm going to make an improved version before I actually submit it. I think I could improve the time by about a minute overall.
You can see it on YouTube.
