Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany
In here ( http://tasvideos.org/forum/viewtopic.php?p=496075#496075 ), I just laid out a game with its levels, and explained its mechanics, and what I found to be a rather forthcoming property of the game (from the perspective of the intent to TAS it) was that it appeared to be in such a form (with no RNG, effectively no lag, independent levels structure) that it seemed to make it possible to work efficiently on optimizing the entire game without the need to be at the computer and have the game running on an emulator (provided one would have the structure of a level on paper or an image of it to think up solutions and write them down with pen & paper), which basically makes it possible to work on it during times (like waiting or travel times) in which one otherwise couldn't be TASing. And this sparked the idea that maybe, in order to make TASing more accessible in (at least) 2 ways, namely to make TASing possible at more (day-)times or in more situations (e.g. while one's on a train without a laptop or otherwise without a device for TASing) and to provide a larger spectrum of games to look into and choose from that likely would be more accessible to newcomers to TASing (due to the properties such games might need to have in order to be efficiently optimizable without requiring emulator knowledge or working with an emulator), so I thought one might just as well generalize & expand on this kind of approach.
For my example above, it looks like The Brainies was also released on Atari ST, Amiga, Apple IIgs, Macintosh, and Amstrad CPC computers, but I have no idea if the levels and/or mechanics are the same or if frame count related changes for different actions exist for those cases, but it might be something of similar interest if one is interested in this case for the SNES. Though beyond this game here, I wondered if this concept could be applied more broadly also for further games that stand similarly much out to be approachable almost in an equivalently effective manner (for optimizing its levels from a TASing perspective) when all one has is a given level of the game together with just some basic required knowledge over its mechanics/rules, compared to if one had to actually use an emulator in order to figure out what the fastest way is to finish the game.
And with this said, I'm suggesting to other TASers to think of further (preferably new, in terms of not already having been TASed) games for which an approach that's effectively separated from having to play the game would be similarly effective, and if they can come up with games of this kind (where the optimization of the full game can be broken into much smaller individual rather separate pieces), and maybe that they mention them or even set up similar posts with the relevant game's resources for allowing quick access to contributing to a game's optimization by TASVideos community members in general. I'm not sure how often such an approach has been taken for a game yet (or how successful such cases might have been), but I think more of it wouldn't hurt.
And maybe this could be considered as some kind of shared optimization contributions concept idea for some people from the TASVideos community, similar to the Dream Team Contests or also the various contributions by different people that I remember that gathered to discuss fastest solutions for the game The Chessmaster in here ( http://tasvideos.org/forum/viewtopic.php?t=4847&postdays=0&postorder=asc&start=25 ) some time ago (and at least The Brainies would also consist of ''pawns'' to move around a board).
collect, analyse, categorise.
"Mathematics - When tool-assisted skills are just not enough" ;)
Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on.
1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans.
2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai.
(last updated: 18.03.2018)
Well to find easily collaborative games, essentially you would have to find games that have low/no amount of randomization and consistent lag. I had also thought of this, but the problem is exactly how would this be done?
Ideas of identifying bad candidates
1a) Manually test for low/nonexistent RNG.
1b) Manually test for consistent lag. Lag can sometimes be changed from previous actions.
2) Perhaps there are certain common RNG seed values that would indicate the game uses randomization. Perhaps exclude if found.
3) Search for certain code for RNG if it could be found to be common among games. Perhaps exclude if found.
Manually testing for RNG specifically can be done like this as far as I know.
1) Make two states having different inputs with different timings that beat the same level.
2) Then beat the next level the same way. Have this new level appended on both of the ways above.
3) If the appended level is able to be run and to be completed after running the inputs then the game probably has no/low RNG.
Also some game types like puzzles where there the "player" is essentially static are far more likely to not use randomness. Games that have some sort of inventory that persists would add additional problems.
Collaborators need to use the same emulator and the same core. Differences in emulation would most likely make stitching the work of different people difficult or impossible.
It would be cool if there was some sort of collaborative tool in Bizhawk for this kind of effort. However it would probably be a ton of work, and might be more suited for some kind of online tool.
Just my two cents on this.
2) Perhaps there are certain common RNG seed values that would indicate the game uses randomization. Perhaps exclude if found.
In games from the era that TASvideos normally cares about, a search for the constant 0x41c64e6d (1103515245 in decimal) within the ROM is likely to find the RNG routine approximately half the time. Finding good constants for use in RNG algorithsm is hard, and 1103515245 has been known to be an acceptably good multiplier value for 32-bit RNGs for a long time. (Bear in mind that many consoles will reverse the bytes in a number, so it might appear in the ROM as 6D 4E C6 41.)
This won't find RNGs with a size other than 32 bits, nor RNGs that use a nonstandard algorithm, but most developers are happy to just use a stock RNG algorithm, and many of those use the constant 1103515245 for some purpose or other.
(Note that 1103515245 isn't technically a seed value – it's a multiplier value – but it's nonetheless a strong indication that an RNG routine is in use, because there isn't much reason to use the number in question otherwise, and it's too large to be likely to appear by chance.)
For what it's worth, the most commonly seen 64-bit equivalent of 1103515245 is 6364136223846793005 (in hexadecimal, 0x5851f42d4c957f2d, or 2D 7F 95 4C 2D F4 51 58 when its bytes are reversed), but this is a much rarer number than its 32-bit counterpart; it may also be more likely to be swapped out for an alternative constant (this isn't the best known value, just the most common, and developers who care enough about their RNG to use a 64-bit algorithm may also care enough to look up improved constants for it).
Joined: 10/28/2013
Posts: 130
Location: United States
ais523 wrote:
In games from the era that TASvideos normally cares about, a search for the constant 0x41c64e6d (1103515245 in decimal) within the ROM is likely to find the RNG routine approximately half the time. Finding good constants for use in RNG algorithsm is hard, and 1103515245 has been known to be an acceptably good multiplier value for 32-bit RNGs for a long time.
[...]
For what it's worth, the most commonly seen 64-bit equivalent of 1103515245 is 6364136223846793005 (in hexadecimal, 0x5851f42d4c957f2d, or 2D 7F 95 4C 2D F4 51 58 when its bytes are reversed), but this is a much rarer number than its 32-bit counterpart
Very interesting, thanks. What properties of these numbers make them so effective as RNG seeds? Is it something about how they respond to bitshifting operations and XORs, or something else?
In games from the era that TASvideos normally cares about, a search for the constant 0x41c64e6d (1103515245 in decimal) within the ROM is likely to find the RNG routine approximately half the time.
I've seen you mention this before, and I have to admit I'm a bit skeptical of its commonality. Maybe the games I've looked at (which are GBA games) are not the ones you're referring to. For reference, the two games I've analyzed had the following values (both using linear congruential generators):
Game & Watch Gallery 4 -- multiplier: 0x5D588B65, increment: 1
Final Fantasy I & II: Dawn of Souls -- multiplier: 0x6C078965, increment: 7
I'd be curious to know what examples you have for using the multiplier you mention, or maybe there's a list somewhere already that can be linked to?
----
goldenband wrote:
Very interesting, thanks. What properties of these numbers make them so effective as RNG seeds? Is it something about how they respond to bitshifting operations and XORs, or something else?
Just to clarify: these values aren't actually seeds. They're Linear Congruential Generator (LCG) multipliers. The difference is that a seed is the initial state value for an RNG, while the multiplier determines how the RNG state advances each time it is called.
Actually, an LCG is a pretty easily understood method of RNG, in my opinion. The basic idea is this: the RNG starts at some state (i.e. a number), and each time a random number is wanted, the LCG produces the next random number by multiplying the old state by the multiplier, and adding the increment-value (both values are generally hardcoded in advance). So for example, if you had a multipler of 10 and an increment of 7, the RNG state would advance as follows:
0, 7, 77, 777, 7777, 77777 (0 * 10 + 7 = 7, 7 * 10 + 7 = 77, etc.)
There's one other wrinkle to this: the RNG state has a fixed size, usually either 2^32 (for 32 bit systems) or 2^64 (for 64 bit system). If the resulting RNG state would exceed that size after multiplying by the multiplier and adding the increment, only the remainder after dividing the original result by the size is kept (i.e. the modulus operation, but really in practice it's done implicitly because the result is truncated by the memory location's size anyway, or it can be done through a bit shift because of the nature of powers of 2).
I can't claim to understand the full theory behind choosing good LCG parameters, but I can at least give a simple example of bad LCG parameters nabbed from the Wikipedia article: multiplier = 0 and increment = 1.
This produces an LCG that produces the following numbers:
0, 1, 2, 3, 4, 5, 6, ...
Clearly not random, and there are probably many similar parameters that would be easily detected by the player, so it's best to be a bit careful in ones choice.
Very interesting, thanks. What properties of these numbers make them so effective as RNG seeds? Is it something about how they respond to bitshifting operations and XORs, or something else?
With any LCRNG multiplier, if you take a group of consecutive outputs, treat them as a coordinate in some number of dimensions, and plot them on a graph, all the resulting points will be on one of a finite number of lines/planes/hyperplanes. So there's a relationship between groups of consecutive numbers. When there are a lot of lines of this nature, the relationship hardly matters in terms of randomness because it doesn't give you much information. When there are only a few such lines, though, it can cause notable issues in the quality of the resulting numbers. A good multiplier will reduce this effect as far as possible by maximizing the number of lines and thus minimizing the information gained from the relationship between groups of consecutive numbers. (If you're interested, Wikipedia has an article on the spectral test for finding low-quality random number generators.)
RetroEdit wrote:
I'd be curious to know what examples you have for using the multiplier you mention, or maybe there's a list somewhere already that can be linked to?
The multiplier in question is presented as part of an example rand() implementation in the C standards, so it's found its way into a lot of C standard libraries over the years (and into some other languages too, which often borrow standard libraries from C).
A quick search of the TASvideos forum gives the following list of games whose RNG was discovered to use the 1103515245 multiplier here on TASvideos:
* Skies of Arcadia Legends
* Phantasy Star Online Episode 1 & 2 Plus
* every game using the PSX's built in random-number generator
* Paper Mario: The Thousand-Year Door
* and two games where someone asked for help with an RNG without saying which game they were working on
GBA games tend to use some other RNG algorithm than this one, though. Perhaps the toolchain for GBA doesn't have a built-in random number generator, so each developer has to come up with their own. (There are some exceptions, e.g. the 1103515245 value appears in GBA Pokémon games, and some of the earlier DS games, too. Perhaps they copied the formula from Pokémon Stadium, which uses the same RNG algorithm.)
