TASVideos

Tool-assisted game movies
When human skills are just not enough

Nach / Memory Init

This page describes various crucial details regarding how systems initialize memory and details to be aware of regarding how this affects games and correlation with emulators. These important concepts in turn influence the rules that TASVideos establishes for movie acceptance.

Table of contents [expand all] [collapse all]

Understanding memory initialization patterns

Memory initialization is typically not a well understood topic. People often think of memory as one giant block of bits, where every bit has a 50/50 probability of being on or off, independently from every other bit of memory. However, memory does not work this way.

Memory is often arranged in some kind of multidimensional grid, consisting of cells. These cells in turn may be arranged within some larger structure, such as separate RAM chips or separate sticks of RAM. Memory will have various controllers as a whole as well as on different hierarchical levels. RAM may also be managed in a way that certain combinations of physical bit settings are actually read as a more limited set. This is done on some systems in order to automatically correct errors that may occur, due to various non ideal situations causing a bit to flip unintentionally.

The structure that stores and manages bits of memory differs from platform to platform. However, a commonality to all platforms is that there are many complex relationships between the bits as a whole. This relationship may mean that rows or columns in a cell must all contain the same value during initialization. It may mean that a cell as whole will always the contain the same value for all bits within it during initialization. It may mean that due to electrical timings and fluctuations, all early bits close to the electric source will be on, and all the bits farther away will be off, with the exact dividing line differing each time electricity is supplied anew. Such a case requires that there must be a running set of on bits followed by off bits, and there can be no other alterations in the middle. Whatever the case may be for a platform, one thing is certain, most bit combinations are impossible as a starting state.

An important way to view this is that the memory bits themselves are NOT random. Memory bits are initialized via propagation from other sources, and these other sources in turn may have some randomness[1] to them. Therefore blocks of memory will always contain some kind of pattern, even though this pattern may or may not be discernible.

Mathematics for the amount of possible initial memory states

It was stated earlier that most bit combinations are impossible as a starting state. Let us review the math regarding the relationship of possible to impossible starting states proving this point.

  Let X be the amount of bits which can be truly random.
  Let R be the amount of bits in RAM.
  Let Y be the ratio of RAM bits to random bits.
  Therefore R = X*Y, where Y >= 1[2].
  Therefore R >= X.
When Y = 1, R = X. Most people are under the mistaken impression that Y is always 1. However, as described in the above section, Y is always much greater than 1.

  The amount of possible initial unique states, P, is 2X.
  The amount of possible states RAM can be in is 2R.
  Let I be the amount of impossible initial states.
  Therefore I = 2R - 2X = 2X*Y - 2X.
In comparison of the ratio of P:I, the amount of possible states is a bounded set, while the amount of impossible states is relatively an unbounded set where the amount of impossible states constantly grow with larger values of X and Y.

Some examples:

  When X = 1 and Y = 2, P = 21 and I = 21*2 - 21 which reduces to P = 2 and I = 2, making the ratio equal.
  When X = 2 and Y = 2, P = 22 and I = 22*2 - 22 which reduces to P = 4 and I = 12, a ratio of 1:3.
  When X = 1 and Y = 3, P = 21 and I = 21*3 - 21 which reduces to P = 2 and I = 6, a ratio of 1:3.
  When X = 2 and Y = 3, P = 22 and I = 22*3 - 22 which reduces to P = 4 and I = 60, a ratio of 1:15.
As can be seen when X >= 2 and Y >= 3, I > P.

Bearing in mind that the amount of bits that are supplying perceived randomness is generally greater than 2, and that complex memory cell structure contains far more than 3 times the amount of bits than the size of the sources they depend on for initialization, it becomes apparent just how many impossible initialization states there are to any memory-based platform. The curve becomes pretty steep.

This proves that in nearly all cases, the amount of impossible cases greatly outnumber the amount of possible cases. Therefore it is a huge mistake for emulators to fill RAM completely randomly[3], as that will in virtually all cases result in a starting state which is impossible for the platform being implemented.

Most people who are unfamiliar with this subject think that systems are designed such that Y = 1, which in turn means R = X, and I = 0. However there is no hardware on the market that is known to have this property, and the odds of Y being 1 would be incredibly rare. Memory just isn't designed that way. I haven't seen any mass produced computer system where Y is anywhere close to 1.

Possible/Impossible Graph

This image depicts how the impossible cases outnumber the possible cases as the amount of random source bits X = 1..150 and amount of RAM bits per random source bit Y = 1..20 increases. The height of the bars show the magnitude of the ratio of impossible cases outnumbering the possible ones. The very top of the graph represents 1:1080.

Conceptual Diagram

See this image to get a better idea how memory is filled:

In the upper left, are some bits which can be random. These bits in turn influence other bits which are not random, but are initialized to some formula of their parent bits. These bits in turn fill the bits in the RAM.

Each platform and memory module has its own way of working, but any system you encounter will do something along these lines.

How memory initialization affects games

Not all games are equal regarding whether memory initialization differences affect them or not. Some games will initialize all used RAM to predefined values when they launch. When memory is initialized by the software itself, what the bits of memory contained when electricity was initially supplied to them becomes moot. When these games do something that appears random, it's usually because they're tied to a clock or some formula related to player input and possibly counters.

For games where the software makes use of uninitialized memory, how the game presents itself and the challenges it offers can change drastically based on what happened when electricity is supplied to the system. The ambient temperature and current oscillations cycle in use when a system is powered on could alter where enemies appear and/or what they do for this kind of software. It could affect anything the game generates during the course of play, such as mazes, vitality, or other resources.

Understanding mutual exclusivity

Mutual exclusivity is an important concept which is also typically not well understood. People may understand all the other sections discussed here, but often fail to consider how enabling one possibility in a game also requires enabling or disabling another associated possibility.

Consider a fighting game where every match begins with the computer controlled opponent either performing a standard attack or blocking. The game may have a series of bits where each is associated with a different fighting round, which determine what the starting activity is. Imagine the platform in question can only initialize a byte in memory to 01010101 (55 hex) or 10101010 (AA hex). In this situation, every fighting round of the eight rounds alternates whether the computer controlled player begins with attacking or blocking. Having two rounds in a row of attacking or blocking would be technically impossible.

In this example, how a particular character behaves can have a full range of possibilities, but one possibility in practice will also force the outcome of other possibilities. Players may want to take advantage of a certain initial fighting pattern for certain rounds because that may be more entertaining or may end up being faster against the fighting character in question. However, setting a single bit in order to force how a certain round behaves, without also setting all other bits with it to be in a possible state will lead to the game as a whole being ran using an impossible situation.

Players may point to some record breaking movie where a particular round was also played in some record breaking fashion, and may want to force that particular round in their movie to be in the same state. However forcing this situation without offsetting the other bits of memory into a combined possible initial state means that multiple rounds are accelerated, when the game technically forces some rounds to start quickly, and others more slowly. Any record based on setting a single bit without also aligning its counterparts is cheating.

Battery backed RAM or NVRAM

Some cartridge-based games come with their own RAM inside the cartridge, and often Static RAM with a battery is used in order to allow a game to save a player's progress. An alternate approach that could be used is also a cartridge which contains Non-Volatile RAM.

When a cartridge uses a form of persistent memory, this persistent memory may feature all the same potential for initialization patterns described above for system memory. In addition to that, it is also possible for the cartridge to have its RAM be preset to some state at the factory, one which would otherwise be impossible when initialized by supplying electricity.

For these kinds of cartridges which use battery powered RAM, when the battery dies, the game may start in some unusual way. Even though this way is atypical when compared to a fresh cart, it is still a valid initialization as batteries failing is an eventual occurrence.

Games often uses some kind of checksum on their persistent RAM in order to detect corruption due to a battery dying or a result of other issues such as electromagnetic alterations to some bits of memory. When a game sees that the RAM's checksum does not correlate with the other bits, it can initialize the memory to some state, which may match any potential factory initialization. Some games may report this occurred. It's also possible the game may just go into failure mode and refuse to start. In any case, it's unlikely that any potential possible starting state for memory when it first receives electricity will also happen to contain a valid checksum.

Due to all this, any RAM supplied on a cartridge has all the same behaviors and caveats system memory has. However it must be understood alongside the possibilities for factory setup, checksums, and how the game reacts to various situations.

Emulator behavior

Emulators have a large amount of variance regarding how faithful they are at implementing some platform. It is important to keep in mind that even the most faithful emulators do little to ensure conformance to memory initialization criteria and behavior.

The different initialization patterns certain kinds of RAM or systems exhibit is not a well studied nor well documented subject. Therefore, for games that make use of uninitialized RAM, they may often exhibit behavior in a particular emulator which is impossible on the official implementations for the platform in question.

Some emulators created by authors who mean well but do not understand this subject will initialize RAM with random values[3]. The randomization will cause the game to exhibit different behavior in the emulator each time it is played. Any of those behaviors will probably also differ from any scenario as a whole that is offered by the official platform.

Persistent memory

Persistent memory has many of the same problems as system memory. One of the added problems is that some games may refuse to start when persistent memory doesn't contain a valid checksum or certain values in certain areas. For these games, emulators often cannot play them, or they feature some kind of hack to force a few bits to a certain setting so the game starts. Such a starting state is likely invalid, but is typically consistent, and allows the game to function in what appears to be a normal fashion.

When dumping[4] cartridge-based games that use persistent memory, ideally any pristine on-cartridge RAM should be dumped as well. This should be shipped alongside any ROM data and used by emulators as the initial cartridge RAM state. This is not typically done, and in many cases it is hard to find a pristine cartridge with its initial factory settings intact.

TASVideos requirements

TASVideos wants to ensure authenticity and reproducibility for movies that are published. Part of this is ensuring equal footing for the options available to players who make movies. It also entails ensuring that no intentional cheating is occurring.

Emulator memory initialization to some computer language's random number generator causes different players to have different situations when they play a game. It introduces non-deterministic occurrences which makes it difficult to compare one movie with another. This is unfair to players who are trying to optimize a game using what appears to be the same benchmarks. Therefore, we want to avoid any such randomized[1] memory initialization routines. While a fixed state an emulator offers may be invalid for the platform, more so is any randomized initial state it offers. Since neither is technically valid (although the fixed state might be), we want to aim for consistency.

Emulators often also allow memory editing so players can have fun with a game and try to play them in new and interesting ways. While this may be fun, we also call this cheating. Even though someone may modify the memory in a game to allow some small part of the game to exhibit behavior that can sometimes be seen on the official platform, they fail to take into account how that behavior becomes inconsistent with how the rest of the game is played. Therefore we disallow any supplied memory state which is not shown to be a possible starting state for all the bits of memory as a combined unit.

Sources of memory initialization entropy

There are many different sources whose permutation of occurrences determine the memory initialization pattern that is applied.

This list is non-exhaustive.

Manufacturing variance

Not all units for a particular platform are necessarily identical. Some units may use different parts which are similar and compatible. Even parts which are considered identical may have minor variances as minute differences are not considered a manufacturing defect if they operate within a given range of acceptable behavior.




Notes


[1] On a philosophical level, I don't believe in the existence of randomness. However, the point here is that how certain pieces of hardware or software is initialized appears to be random, in that it's not fully deterministic from the hardware or software itself and can depend on external sources which have fluctuations.

[2] Note that Y < 1 is nonsensical.

[3] Emulators typically don't use some random algorithm where each bit has a 50/50 probably of being on or off in isolation. Rather they typically use an LFSR-like algorithm, or something similar, which has its own set of relationships between bits when used to initialize large bit streams. You can guarantee that no physical RAM hardware would use anything like one of these algorithms, as memory structure design isn't based on a looping number algorithm like basic random number generators are.

[4] Dumping is the process where the memory of a cartridge is copied to a more popular storage medium or personal computer.



Combined RSS Feed
Nach/MemoryInit last edited by Nach on 2018-05-28 20:33:28
Page info and history | Latest diff | List referrers | View Source