Difference between revisions of "Random Number Generators"

Latest revision as of 14:26, 25 July 2013

Random Number Generators

A Random Number Generator (RNG) is a system which produces seemingly random values based on an initial sequence and other sources of entropy. It is important to note that RNGs in games are not "truly" random; the same sequence of inputs and conditions will always produce the same results (and thus these constructs are technically Pseudo-Random Number Generators, or PRNGs). This means that in some cases a game's RNG can be manipulated to produce favorable results. The TASVideos page discusses RNGs in more detail, but this page is meant to discuss real-time strategies for manipulating RNGs to produce favorable outcomes.

Categories of Random Number Generators

Different games will require varying amounts of randomness and with different frequency. For example, consider a platformer such as Donkey Kong Country and a dungeon crawler such as Swords & Serpants. There might be very little randomness in DKC since most enemies move in fixed patterns, but nearly every action in Swords & Serpants has some element of randomness to it. Different RNG systems take different information as inputs as well. In general, game RNGs can be boiled down to a few types of categories. These categories have been adapted from the listing on TASVideos.

• Per-frame RNGs. This type changes every frame regardless of the actions taking place in the game. Events that require the RNG will use whatever value is available when they need it.
• Per-call RNGs. This type of RNG changes its value ("state") only when it is called for an event. This type of RNG is common in RPGs where significant randomness is needed only when deciding actions and in calculations for damage etc.
• Input-driven RNGs. This type collects entropy from player inputs to use as either the seeds or direct values for the RNG. This is uncommon, but can be used in games which expect input-heavy actions to drive the gameplay.
• Event-driven RNGs. Similar to input driven and per-call RNGs, event-driven RNGs advance on certain required actions in the gameplay even if the action has no randomness component to it. For example, some RPGs might advance the RNG each time a step is taken, regardless of whether or not the player is susceptible to random encounters.

While these are the main types of RNGs, they are not necessarily distinct from each other. For example, consider the RNG system used in Super Punch-Out, which relies on user inputs to seed a per-frame RNG. Suikoden II advances its RNG only when called for some periods of time before shifting to a per-frame version after timed "grace periods" have elapsed. Figuring out what type of RNG your game uses can be somewhat tricky, and a short guide is available in the Reverse Engineering section.

Exploiting Random Number Generators

Since game RNGs are part of deterministic systems, it is possible to force the same events to occur by performing the exact same actions. What it means for actions to be "exactly the same" varies from game to game, but in a tool-assisted environment it is easy to manipulate and predict subsequent RNG values. It is not nearly as simple to do in real-time, but is still possible in a number of cases.

It is important to note that manipulating the RNG does not necessarily mean always getting the correct outcome. There are a number of cases where just understanding the RNG can better inform your decisions about which actions are most likely to succeed. Even if you can't guarantee 100% success rate, being able to improve a 5% chance to a 25% chance is a huge boon to sanity for many runners. Even a tendency of an RNG to produce certain outcomes 1% more often is valuable knowledge for routing.

First, consider the category of RNG that is present in a given game. Per-frame RNGs are typically not manipulable in real-time unless you can be sure it resets to a certain value after certain events or can adequately buffer all required actions. Per-call RNGs are much easier to work with, but determining or forcing a good starting seed value is not trivial. This is also true of event-driven systems, where the player can control when or how to perform certain events to get a favorable outcome. Input-driven RNGs are slightly less difficult to manipulate than per-frame RNGs, but can still be challenging or impossible in real-time.

Second, figure out if there are any nuances to how the RNG operates. Does it change during any other actions? Does it reset between stages? What happens on a death or a game over? How about a reset? Is it ever overwritten? This step just aims to figure out the range of options you have in trying to manipulate it.

Finally, determine what is actually used from the RNG value for your event of interest. In many cases the full value from the RNG is not needed; it will only take a small sample of the bits and use those to determine an action. Every game and event may deal with this differently though. The best way to determine this is to dig into the assembly code and determine the exact conditions for certain events, but this requires some special knowledge and skills. Alternatively, one could simply observe the RNG values and draw conclusions based on patterns of the bits and observed outcome. This is not advised for events that have many possible outcomes however (such as item drops in an RPG). As a rule of thumb, count the number of possible outcomes and then look for patterns in the square root of that number of bits, rounding up. Thus, 4 outcomes would be based on 2 bits, 6 would be 3 bits, and 20 would be 5 bits.

Examples

Coming soon.

Hagane

Hagane on the SNES uses a proprietary RNG system that only advances when called. The main properties for it are listed below:

• The two RNG addresses are initialized to 00 at the start of the game.
• RNG is called for some enemy actions, drops, and any particle effects. This includes explosions, falling feathers, and "dust" from flying enemies.
• If the player dies in a stage, the player restarts the stage with the exact RNG sequence from the first time they entered it.

With this knowledge, there are a few ways to exploit the game's RNG. The first is the most obvious, but perhaps least useful for speedrunning: if you die in a stage, you can expect the exact same outcomes the second time through if your movements are consistent. This is important for bosses that have random patterns. This fact that dying is necessary for this makes it non-ideal for full attempts, but it is useful knowledge in a marathon environment.

The second main point is that the RNG consistently starts in the same way, and to some extent you can control how many times it is called. This is useful in the first stage to manipulate bomb drops from certain enemies. Experimentation is one way to determine the proper sequence of actions, but a more concise way is to simulate the RNG sequence in code and actively try to achieve the desired values.

For example, suppose that the 92nd and 104th RNG values both produce bomb drops if you can kill an enemy on those values. With some observations of the game's engine, you find that killing a bird causes the RNG to advance 82 spots, and killing a regular sword enemy will advance the RNG 6 times with each explosion in addition to the random drop. Some small other consistent effects advance it an additional 4 spots. With this knowledge, you can develop a plan to hit both the 92nd and 104th RNG values as drops:

Initialize RNG (0, 0)

• Kill a bird (+82, 82)
• Miscellaneous calls (+4, 86)
• Kill a sword dude (+6, 92!)
• Kill two more sword dudes, get bomb drop 1 (+12, 104!)
• Kill any enemy that has a random drop, get bomb drop 2

The final way to exploit Hagane's RNG doesn't try to manipulate the system at all, but instead observes the system so that effectively random events can achieve favorable outcomes slightly more often. Due to how the RNG is constructed, any time it reaches a state of 00 00, it follows the same pattern until it again hits 00 00, and so on. Turns out that it only takes 1558 calls to reach 00 00 from 00 00, meaning that it has a very short period. Digging in a little deeper, the distribution of numbers is not equal. For example, consider the attack patterns of En-Mikoshi and Shura-Oh, two of the bosses in the game. They each choose their pattern based on the last two bits of the current RNG value to select one of 4 patterns.

• En-Mikoshi:
  • 0 is lasers
  • 1 is electro-balls
  • 2 is soul balls
  • 3 makes him vulnerable
• Shura-Oh
  • 0 spawns weak spot on top
  • 1 spawns on left side
  • 2 spawns on right side
  • 3 spawns on top

A frequency analysis of all 1558 RNG values in the cycle reveals that the last 4 bits have different probabilities to occur.

• 0: 26.64%
• 1: 24.71%
• 2: 25.16%
• 3: 23.49%

This is bad news for En-Mikoshi since the desired pattern is the least likely and cannot be manipulated. For Shura-Oh, however, you can use this information to make a more informed decision about which side to attempt the quick kill. Since 2 is slightly more likely than 1, it is more likely that you can get the quick kill be approaching from the right side instead of the left. This difference in probability is very minute, but any additional help towards the desired outcome can help out during attempts.

The assembly subroutine for Hagane's RNG is listed below.

c101e1 jsl $c0c434   [c0c434] A:0007 X:0002 Y:0000 S:01e4 D:1180 DB:83 nvmxdiZC V:  2
c0c434 php                    A:0007 X:0002 Y:0000 S:01e1 D:1180 DB:83 nvmxdiZC V:  2
c0c435 phd                    A:0007 X:0002 Y:0000 S:01e0 D:1180 DB:83 nvmxdiZC V:  2
c0c436 sep #$20               A:0007 X:0002 Y:0000 S:01de D:1180 DB:83 nvmxdiZC V:  2
c0c438 lda #$00               A:0007 X:0002 Y:0000 S:01de D:1180 DB:83 nvMxdiZC V:  2
c0c43a xba                    A:0000 X:0002 Y:0000 S:01de D:1180 DB:83 nvMxdiZC V:  2
c0c43b lda #$00               A:0000 X:0002 Y:0000 S:01de D:1180 DB:83 nvMxdiZC V:  2
c0c43d tcd                    A:0000 X:0002 Y:0000 S:01de D:1180 DB:83 nvMxdiZC V:  2
c0c43e lda $aa       [0000aa] A:0000 X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdiZC V:  2
c0c440 lsr a                  A:00b0 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizC V:  2
c0c441 lsr a                  A:0058 X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  2
c0c442 lsr a                  A:002c X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  2
c0c443 lsr a                  A:0016 X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  2
c0c444 sta $28       [000028] A:000b X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  2
c0c446 lda $ab       [0000ab] A:000b X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  3
c0c448 asl a                  A:0067 X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  3
c0c449 asl a                  A:00ce X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c44a asl a                  A:009c X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizC V:  3
c0c44b asl a                  A:0038 X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizC V:  3
c0c44c ora $28       [000028] A:0070 X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  3
c0c44e eor #$ff               A:007b X:0002 Y:0000 S:01de D:0000 DB:83 nvMxdizc V:  3
c0c450 sta $28       [000028] A:0084 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c452 lda $aa       [0000aa] A:0084 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c454 ora $ab       [0000ab] A:00b0 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c456 bne $c45e     [c0c45e] A:00f7 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c45e lda $aa       [0000aa] A:00f7 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c460 sta $ab       [0000ab] A:00b0 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c462 clc                    A:00b0 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c463 adc $28       [000028] A:00b0 X:0002 Y:0000 S:01de D:0000 DB:83 NvMxdizc V:  3
c0c465 sta $aa       [0000aa] A:0034 X:0002 Y:0000 S:01de D:0000 DB:83 nVMxdizC V:  3
c0c467 lda $28       [000028] A:0034 X:0002 Y:0000 S:01de D:0000 DB:83 nVMxdizC V:  3
c0c469 pld                    A:0084 X:0002 Y:0000 S:01de D:0000 DB:83 NVMxdizC V:  3
c0c46a plp                    A:0084 X:0002 Y:0000 S:01e0 D:1180 DB:83 nVMxdizC V:  3
c0c46b rtl                    A:0084 X:0002 Y:0000 S:01e1 D:1180 DB:83 nvmxdiZC V:  3

MATLAB implementation to determine drops:

 iterations = 100;
RNG = uint8(zeros(iterations+1,4));
drop = uint8(zeros(iterations,2));

for i=1:iterations
      
    drop(i,:) = bitxor(uint8([RNG(i,2) RNG(i,3)]),uint8([15 15]));
    if(bitor(RNG(i,1:2),RNG(i,3:4))==[0 0])
        RNG(i+1,:) = uint8([1 0 1 0]);
        RNG(i+1,4) = drop(i,2) + RNG(i+1,4);
    else
        RNG(i+1,1) = RNG(i,3);
        RNG(i+1,2) = RNG(i,4);
        RNG(i+1,3) = RNG(i,3);
        RNG(i+1,4) = drop(i,2) + RNG(i,4);
    end;

    if(RNG(i+1,4)>15)
        RNG(i+1,3) = drop(i,1) + RNG(i,3) + 1;
    else
        RNG(i+1,3) = drop(i,1) + RNG(i+1,3);
    end;
    RNG(i+1,:) = bitand(RNG(i+1,:),uint8([15 15 15 15]));
    
    itemval = bitor(bitshift(drop(i,1),4),drop(i,2));
    itemnum = drop_table(bitand(bitshift(itemval,-1),uint8(63))+1);
    if(itemnum==1)
        items{i} = '1up';
    elseif(itemnum==2)
        items{i} = 'Blue Flame';
    elseif(itemnum==3)
        items{i} = 'Red Flame';
    elseif(itemnum==4)
        items{i} = 'Kunai';
    elseif(itemnum==5)
        items{i} = 'Grenade';
    else
        items{i} = 'Bomb';
    end;
    
    hexRNG{i} = cat(1,dec2hex(RNG(i,:)));
end;

items = items';
hexRNG = hexRNG';

Robotrek

Super Punch-Out!!