Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
This category reminds me of a newgame+ more than anything else (except that cheat codes are used to unlock the fully powered state rather than an existing save file). Would there be some way to make a similar run starting from a completed save file? If so, it would likely be less controversial (but still might be rejected if it's perceived to have insufficient entertainment value).
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Soig wrote:
7-tower is similar to it. To get the last starcoin, shell Mario is the fastest one. And the places getting injured are too near. So it would not be faster, I guess.
That's not what I meant: my idea would be to intentionally run at the crusher that blocks the star coin (rather than waiting for it, which is slow), collect it during the invincibility frames, then use a hammer from inventory right afterwards (so you still have the hammer for the boss). Even if you need that inventory hammer for something later, you should have an opportunity to restock it without needing too much time.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
ais523 wrote:
Feedback on storage glitches: although all three variables are probably storable, u.usleep gets unstored whenever nomul is called and you don't end up helpless.
My current line of investigation is to try to save the action where we heal our wounded legs (via prayer, which would involve storing afternmv); saving an action would presumably give us options for making the endgame strategy more probable and/or entertaining. This basically requires some approach to setting multi to 0 from negative without changing the value of afternmv: in other words, a helplessness cancel. My first thought along these lines was stinking cloud + lifesaving, but unfortunately that doesn't store afternmv while multi is negative (it ranges from -3 to -1 over the course of the prayer). Equipment removal storage doesn't work either (as that requires you to store afternmv to a different value and we can't store it at two values at once). So this might be a dead end.
(Storing eating, rather than prayer, might seem easier because it's interruptible; however, it's an occupation, and occupation storage can't possibly persist past a player input because occupations replace player input, making this a non-starter.)
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Does this run intentionally take no damage? There are a few points where I was expecting you to damage boost (e.g. 7-Tower and 7-Castle), but you didn't. Or do the damage boosts not work there for some reason?
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
ais523 wrote:
we need to land close enough to the Dark One that the monsters that followed us are in range, also land next to a level teleport trap (on that level)
Crazy speculation, but what if we use a different role's quest nemesis rather than the Archon? (I don't even think you can create a "stable" off-role quest nemesis, but it might be possible to get a doppleganger to act as one for a bit.) There are circumstances under which quest nemeses will go after your Quest artifact and attack in the same turn; I'm just not sure if the circumstance that exists immediately after creation of the Quest goal level is one of them (there are some special cases with respect to meditating monsters that prevent Rodney waking early and I'm not sure if they apply here; even if they do, we might be able to do something using a shopkeeper polymorphed into a mind flayer, but that starts reducing the probability again). If it does, we wouldn't need to land next to the Dark One ourself as the level is teleport-permitted; arrive on the level, let the quest nemesis covetous-teleport to and ORKO the Dark One (Master Kaen would be a good choice for this!), get thrown onto the level teleport trap, then let a quantum mechanic teleport us. Because we have teleport control, we can then pick the square with the Bell without needing to be near it.
We'd need to change the setup for the Quest home level slightly to allow for the fact that Master Kaen would be standing next to us, but that's doable (we could have him replace a red mold).
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
I've updated t2000timings with the strategies that have been discussed in this thread over the last several months. It's quite possible I've missed something, but if not, everything does actually fit into 2003 turns now.
The next step would likely be to work on ways of increasing the probability of the most implausible steps (either by finding an alternative, equally fast, strategy, or else by finding a better way to do manipulation). The worst part is probably 2000:49 and the following monster turns; we need to land close enough to the Dark One that the monsters that followed us are in range, also land next to a level teleport trap (on that level), and after teleporting back up to the Quest, land on a specific square that we've set up in advance beforehand. (Although it seems plausible that we could use an ice-and-landmine chain to move us into the right place during 2000:37, as long as it's somewhere between northwest and southwest of the prepared square, which increases the chance of that part of things somewhat.)
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Tools like Hourglass and WINE are translating at the API level, not the ABI level. The ABI basically just says "if you have a function which takes X arguments and produces Y return value, here are the registers you use, here's how you have to set up the stack, etc.". Most notably, the ABI doesn't define anything about what individual functions do. An ABI translation would thus allow you to connect together programs and libraries which were compiled using different compilers (the best-known such incompatibility being MSVC versus mingw).
The API is a list of functions and what those functions actually do; it's relevant both for programmers, and for compiled programs. (Sometimes the details differ, but normally not by much, in order to keep compilers simple.) Hourglass, WINE, and libTAS work at this level of abstraction; they know, e.g., which functions are timer functions, which is information included in the API but not the ABI. Then those functions (only) get replaced.
There are other possible techniques, e.g. I (have been working / do not currently have the time to work on) a layer that translates at the system call level rather than the library level (on Linux, these are distinguished by which chapter of the manual they're in, system calls in chapter 2, library calls in chapter 3). The benefit of that is that there's only a few hundred system calls (as opposed to too many library functions, across all the libraries in existence, to easily count), so in theory it should be possible to consider all of them individually and ensure that they're all 100% reproducible.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
I typically like runs which are "this game, but using its main mechanic as little as possible", and like the amusement value in considering the main mechanic of VVVVVV to be the checkpoints (it's a famously lethal game).
I'm not sure it makes enough of a change to be worth a separate category, though. Most of the time, you don't even notice it. The Tower was a pretty interesting exception – there was some pretty clever manoeuvring to avoid some checkpoints there – especially as I expected it to be uninteresting. (There was even room for the scrolling trick, despite it needing a checkpoint to use, because the checkpoint was unavoidable.) However, that level's an autoscroller, so I'm interested in how many of the checkpoint skips you could incorporate into an any%-no-telejump run in order without losing time; it might be a good way to make the level more entertaining.
Perhaps it's worth having a category that contains the Gravitron, just to show off the whole game, but it's not actually all that interesting under TAS conditions; I imagine that frame advance trivialises it.
What version of the game is this? In the encode, the music in the "third intermission" / the sixth main area is different from what I remember actually existing in-game.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
100% rules question: say a game contains 100 items, some of them have duplicates out of bounds, and collecting both the out-of-bounds and in-bounds copy does not increase your percentage more than collecting just a single one. Is it legitimate for an all-items/100% run to collect just an out-of-bounds copy of an item, and not the intended original?
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
ErisK wrote:
So in theory, if the camera is always fixed in one place, no other loadings should occur? Well, I'm not sure about the backgrounds and such but... The objects that I want to keep track of (or rather, the 'slots' containing them), they should keep the same value as long as the camera is still in the same place, right?
In most 2D games, no objects that are currently onscreen will load into different memory locations as long as the camera doesn't move. (It's frequently the case that there are short-lived objects, like animations as the player's character moves, that load in and out even without the camera moving. But those rarely affect anything that was onscreen already.)
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
There's Hourglass, but it's somewhat finicky (working much better on some versions of Windows than others) and frequently doesn't work (either with specific programs or in general). There's a project to write a newer version of it but it's nowhere near finished.
If you're making the game yourself, TAS tools such as savestates and frame advance are often fairly easy to implement into the game engine. That might be easier than trying to get hourglass to work.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
ErisK wrote:
Well, while I've done some work on memory watch and was able to find a bit hard RAM Addresses, I'm still new to this and aren't too sure about how to search for such slots/objects. My guess is that I should watch at the changes of values before and after a loading, but is there some clue as to when the loading actually starts? Is it as soon as the object appears onscreen, or could it be before?
There's no hard rule that forces games to do it a certain way, but most 2D games will load an object when it reaches a particular point relative to the camera. That might be the moment the object is visible onscreen, slightly earlier, or in some cases even slightly later (in these games you can see the object loading in). Bear in mind that the view shown onscreen might not go right to the edge of the screen, too (many games will have some sort of frame around the edge of the screen, maybe just a black rectangle, to hide objects that are in the process of loading so that people can't see them suddenly appear).
In 3D games, objects are more likely to load based on the player's position than on the camera's position (because otherwise, the console would have huge lag issues if the player decided to spin the camera round quickly).
Also, what numbers do ID normally have? And do objects have their own RAM Address? I guess they do as absolutely everything seems to have a RAM Address (which makes sense considering everything has to be saved somewhere), but I'm just guessing so I ask just in case.
Normally, an object's address will depend on its ID number; there'll be some place in memory that, say, stores information about the object with ID 5. Part of the reason to have a system like this is that not all the objects in the game can fit into memory at the same time, so the ID number system prevents two objects trying to use the same bit of memory. The ID numbers themselves are often just small integers (0, 1, 2, etc.), and might not be stored explicitly in memory (i.e. you determine an object's ID number by looking at the address where its data is stored, rather than the other way round).
Actually finding the memory addresses in question can be fairly hard; I can't think of a simple way to do it offhand. On some consoles, there'll be memory addresses reserved for sprite coordinates (e.g. the NES's OAM); you may be able to find the object loading code by monitoring for writes to that, but you'd likely need to decompile the code in order to figure out where it's storing the information about objects.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Many games use a "sprite slot" system where each sprite on screen has an ID number, but there are only a very small number of possible ID numbers and so they get recycled a lot. When an object loads, therefore, it'll typically be given the lowest ID number that isn't in use at the time (but then that number will stay stable as long as the object stays loaded). This is particularly common on older platforms (like NES) due to the way that those platforms' graphics works.
My guess is that the object that's being targeted is always picking the object with the (highest/lowest) ID number, which is why you can't see a pattern but also can't get the results to change. In games where "which object goes in which slot" is important, it's normally a good idea to set up a memory watch to allow you to keep tabs on it; often you'll need to unload specific objects at specific moments to get other objects to load into the slot you want.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Some more thoughts about how best to do the Plane of Fire:
If we need to get pushed on arrival, it is best to use hostile following monsters, as they have by far the greatest chance of doing so. We can do that by bringing covetous monsters with us from level 1, making sure they are put into the Plane of Earth before the monster that will cause us to fall from the ceiling, so that they go after it.
This isn't compatible with an overflow hurtle because that happens on our own turn; although magic portal level changes are always deferred, deferred_goto() runs before movemon() so the covetous monster wouldn't move to our destination.
Additionally, covetous monsters are very problematic for enexto triggers. The problem is that if the player has something they covet, they always teleport before moving (even if they're in melee range at the time and the teleport would take them further away). This means that the square you land on after the enexto is in practice nearly always going to be the square the covetous monster moved from, and it's very hard to make that the same square as the one you actually want.
These two considerations together imply that using a covetous monster on Earth is problematic, on Air is potentially possible, and on Fire seems very unlikely indeed; each Plane you have to navigate it through adds its own set of problems. (The corpse-with-added-data suggestion you had earlier is likely to be the best solution for Astral; it's much easier than trying to navigate a monster in monster form through all the levels in question.)
Incidentally, the fastest follower in the game is a polymorphed shopkeeper (although those aren't covetous). Faster still is an arbitrary following monster that's been hypercharged by repeatedly allowing it to gain movement points and then changing level before it can spend them (this relies on the fact that monsters can't move until the next player action if the player entered the level as a result of a monster action on a different level; you can sneak a turn boundary in between).
n720 wrote:
That luch-manipulation can be done by 'g'-moving in the direction of the monster used for the push
Thank you so much for this tip. That's likely to make the planes orders of magnitude more watchable, as it's a message-free turn-free method of luck manipulation. It works on pets too, and although we could do that anyway, it's so much faster in realtime that it opens up possibilities for extreme luck manipulations without making the run unwatchable. (It should even be able to be hexed in in cases where we used pet-attack-cancel previously, if any of them exist in the run.)
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Congratulations on another successful TAS block! Celeste seems to have been the most-well received this time (which is heartening, as non-ACE runs tend not to have done that well in the past, so it shows that this genre can excite audiences too).
The main potential improvement I'm seeing is that people are confused as to a) what was done purely via controller input, b) what was done via crafted SRAM/memory cards, and c) what was done by editing the game ROM. I'm assuming that there are no edited ROMs here (apart from the "Hi SGDQ" in Celeste which was left over from the non-TAS runs?), F-Zero GX used an edited memory card, and Super Metroid was pure controller input? If so, that really wasn't explained well at all and some people were unsure how impressed they should be. Apart from that, though, everything seems to have gone very well.
I guess we now have to start planning for next time…
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Huh, it does work.
I'm pretty surprised at that because I thought I'd checked all the codepaths. Perhaps I had some sort of mental block that prevented me considering invalid commands (in this case, applying an artifact that doesn't have an apply effect).
In a way this might make the TAS a bit less interesting, as it means that we don't have to screw around nearly as much on Home:1 as we would otherwise (I was preparing some sort of super-elaborate plan with multiple zero-turn backtracks via double-drowns). On the other hand, it does rather increase the chance that it gets finished at all.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
OK, so the basic idea is this: we want to find the shortest input file that completes the game, and in theory you could do that via trying all possible input files in length order until one of them completes it, but that's too slow. So we want to find some other algorithm that has the same effect as that one.
The most basic thing we can do here to speed things up is called "pruning": identifying input sequences that can't possibly be shortest (or at least, if they are shortest, must be tied for shortest with a sequence that hasn't been pruned), and not simulating them. For example, if we discover that holding down the Select button on the first frame of the game has no influence on the game's memory, we can prune all the sequences which hold Select on frame 1, as they'll necessarily tie with the equivalent sequence that doesn't use Select. This can be very easy to do in the simplest cases (e.g. via using a memory comparison of all of memory).
There are more complex examples of pruning, though. For example, if the memory states differ but the addresses that differ will necessarily be overwritten before they're read (say some memory address holds "buttons held on the previous frame" but it's only used in certain circumstances that don't apply here), or the memory states differ but can't affect the time at which the game is completed (as determined by, e.g., static analysis; this is very hard to do in general because almost anything can affect lag properties).
A second possible optimisation is reordering: changing the order in which we look at input sequences to look at more fruitful sequences first, in the hope that we'll find the optimal sequence earlier. The problem with reordering is in proving that the sequences that you've deferred until later aren't going to lead to a shorter outcome than the final game-completing sequence you end up with; so you'd need to use something like automated static analysis to produce hard constraints on what's possible in the game that a reordering algorithm could use. (However, there are algorithms like A* that can be used to produce a good reordering given pretty much any assumption about how the game can act, and are known to find the optimal answer first if the assumption is correct. So the only difficulty here, but it's a pretty big one, is to ensure that the assumption you've made is one that's valid in the game, which would have to be done via a combination of searching for any codepaths that violate it, plus a proof that ACE does not exist in the game. The latter isn't as ridiculous as it sounds; it's an important security property to have so tools for proving that already exist for a range of languages and platforms. If we had one for a common TAS platform, it'd both be helpful in finding optimal runs, and in finding new ACE tricks.)
Reordering can also be used to get results that are intermediate points towards having a provably perfect run. For example, suppose that instead of aiming for a minimum number of frames of input, we aim for a minimum number of non-lag frames between the start and end of the game, and try the input files in an order that provably optimises for that. This will likely be much easier to prove optimal (under the non-lag metric) than proving an input file optimal under the normal timing would be, as you can prune it much more aggressively. Once you're done, you have a proven fact about the game that you can use to guide future TASing; for example, if you know that the game takes a minimum of 19425 non-lag frames to beat, and you then produce a TAS that beats the game in 19425 frames total, you'll know that your TAS is optimal (and, as it happens, lag-free).
Finally, there's the concept of parallel simulation: you have two gamestates that genuinely are different, but which are similar enough that you can emulate them at the same time rather than having to emulate them separately. The simplest example of this is to imagine two input sequences that lead to memory states which are almost but not quite the same, and the memory addresses that differ are not read on the next frame (but may remain different at the end of the frame); we can determine this with registerread or the like. In this case, simulating one input sequence has given us the result of the other input sequence for free. The main disadvantage of the simple case here is that we'd need to somehow identify what input sequences can be grouped and how to make use of that for our big simulation. You can get more complex with this, e.g. tracking dependencies that are more complicated than an untouched address, or caching the emulation of blocks of code at a subframe level, but at that point you pretty much have to write the emulator from scratch to support that sort of operation.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
feos wrote:
Sure, you can compare every memory state you get to all possible memory states, and disregard all the new input sequences that lead to some previously found memory state. But that doesn't tell anything about which memory state leads to absolute shortest movie. It's just not enough to check if the "word" you have is in the "dictionary" or not.
For example, let's say I have a savestate on frame 1000, I got there by executing certain inputs. It may be possible to reach this state sooner in the movie than in 1000 frames. Without testing all the possibilities up to that frame, I won't be able to prove that 1000 is the optimal frame for this state.
This is down to search algorithms. There are some search orders you can use that are guaranteed to find the shortest output first; the simplest is to try all the possible inputs in length order (except for ones which have a prefix that turned out to be slower than another way of doing the same thing). I think there may be games where this is simple enough that it's actually within the capabilities of a powerful modern computer.
I have some more complex algorithms in mind that would have the same properties but be more efficient. The problem is just finding time to getting around to implementing them.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
The most obvious example of an assumption that can't possibly be wrong: if two sets of input lead to the same internal memory state in the game (i.e. every address has the same value), then there's no reason to explore possibilities starting from both sets of input data. You can drop one (the longer, or either if they're the same length) and just continue with the other.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
Doesn't the standard branch label for Metroid Fusion, "100%", exactly show the number of optional items that are collected (100 of them)? I think there'd be opposition to relabelling the branch as "all optional items".
Nobody cares about the mandatory items because the game doesn't count them (and in fact is technically incapable of recognising game completion unless it considers them all to have been collected, thus any glitched state in which the game can be completed via the intended ending will also contain every mandatory item).
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
moozooh wrote:
Without going out-of-bounds, no. You need a total of 4 missile/super missile packs for Mother Brain's first form (it works on a per-hit basis), a Varia Suit and 3 e-tanks to survive her rainbow beam, Morphball, bombs, and powerbombs for accessing various areas of the game, Charge to damage bosses, either Ice or Speed Booster to skip Zebetites. Neither of them is skippable by clipping through the floor.
I guess Bombs might have the most potential to be skippable? You can get Power Bombs without them nowadays, so the only thing you'd need them for would be jumping in Morph Ball form, something that's rare enough and physicsy enough that there might be some way to skip all those points individually.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
electricslide wrote:
Ais, your point about 'adjusting the time' to match what the net expected number of resets requires makes no sense to me from a TAS context. Luck manipulation is a big part, making unlikely things happen on command is huge.
The whole point is that you can't manipulate it by control input. The only ways to manipulate it would be unauthorised changes to the cartridge or console.
Seeing TASes manipulate luck is fun, but only because they do it to the laws of the game, rather than cheating.
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
I'm interested in how you managed to get a different Pokémon to be caught each time with the glitch. Where's the species number being read from?
Anyway, this reminds me of previous April 1 submissions in which the player has edited a cheat engine into the game using Arbitrary Code Execution and used it to complete a non-any% goal. In this case, the glitch family used is Arbitrary Memory Corruption, not Arbitrary Code Execution, but the end result is fairly similar. These sorts of glitches are often looked for to exploit non-game programs, and so quite a lot of effort has been put into mitigating them; in particular, most modern home computers now ban executing RAM altogether by default. However, it turned out not to stop ACE-like bugs, because AMC is normally just as powerful (just harder to use). This run is a demonstration of that general principle.
At this point, I don't think the category is meaningful unless you ban memory corruption altogether (i.e. buffer overflows and similar effects that can cause a RAM address to be written to by code that isn't meant to write to it). I'm not sure if the goal is still possible under those circumstances, but it might be, e.g. the Old Man glitch would probably still be legal (as although the memory addresses involved are being written with one purpose and interpreted as another, they're still being used for their intended purpose in both cases).
Editor, Experienced Forum User, Published Author, Player
(44)
Joined: 7/11/2010
Posts: 1022
So the fundamental problem here is that we require games to run from a blank cartridge (and a blank console, i.e. without pre-initialised RAM), but in practice the cartridge and console will have to have some values in their memory and SRAM, and it's unlikely that the game developers or console manufacturers took these into account when creating the game or console.
There will always actually be values there, of course, but they might not be the same. Games are normally designed so that in normal gameplay, the values don't matter. (There are a few exceptions, e.g. some games might use the values to initialise an RNG.)
However, it's possible to do glitches that make the values in question very relevant. Such glitches will not have deterministic results on a real-life console. On emulators, they will of course have deterministic results (because emulators are designed to be stable), but what those results are will be based on an arbitrary decision by the emulator designer.
I can see a few options:
a) Program emulators to use an "uninitialised memory" value for storing the content of uninitialised memory. If this is read at any point, halt and refuse to continue running the game. This would ensure that any emulator run will have the same result on a practical console.
b) Work out what the most likely values to appear on a blank cartridge/turned-off console are, and set that as a set of fixed values which all emulators must use. This might or might not be 100% realistic.
c) Work out the probability distribution of values to appear on a blank cartridge/turned-off console. Then for any run that relies on particular values appearing in particular places, calculate the probability that those values are there. Time a run as though it repeatedly resets until it gets the values it needs (as soon as the fact that they're incorrect becomes observable through, e.g., audio or video output), and an average number of tries is needed to get to the values.