The Let's Play Archive

MegaMan Battle Network: Operate Star Force

by giver336, GeneralYeti

Part 7: Prof Explains The Mystery Data Bug...In Great Detail

So to briefly explain this RNG glitch that Giver touched on... It's kinda something you really have to 'get', it's hard to explain why this happens, but I'll try my best to make it as accessible as possible. This got kinda long whoops You will need to be a little familiar with the mathematical concepts of the modulo operation (basically just getting the remainder of a division) and bitwise operations in order to fully understand this post (but don't worry, it's pretty easy, and you'll hopefully be able to get the point even if you don't fully understand it).

First, a brief introduction into RNGs if you're not familiar with the concept.

As you probably know, RNG stands for Random Number Generator and it's a mathematical function that spits out random numbers in case the game wants to for something. More specifically, an RNG is pseudo-random, which basically means that it produces a fixed sequence of numbers based on the current "seed" value. Usually this "seed" is the previous RNG result. The key principle is that since the player cannot know the current "seed" value, they therefore cannot predict the sequence of numbers that the RNG will output next. Note that the RNG result is not equal to the result you actually see reflected in the game; if you roll a die in a game, and it shows a number between 1 and 6, the actual RNG result will be a number between 0 and 2 billion (in the case of MMBN1), from which the die roll result is calculated (usually via a modulo operation).

If you're familiar with RNG manipulation from, say, Pokémon, or speedrunning, you might know that this key principle can be broken if you're persistent enough, and if the game's developers didn't do a good job of protecting against RNG manipulation. If you know the formula the game uses for its RNG, then you can figure out, in advance, the full sequence of numbers that the RNG will generate, and the corresponding die roll results shown in-game. You could then repeatedly roll dice and note down the results, and then cross check with your sequence of numbers to deduce the current RNG seed. For example, in MMBN1 speedruns, the RNG always starts from a known initial state when you hit Continue on the title screen, and so if you hold down a direction on the D-pad you'll always run into the same fight with the same chip draw.

With the introduction out of the way...

All the Capcom-developed MMBN games on GBA/DS use the following function to generate a new RNG result:
The game also advance the RNG on every frame the game is on the overworld (in the case of BN1) even when it doesn't need any random numbers.

As far as I know this doesn't correspond with any other RNG algorithm out there. If you Google the parameter 0x873CA9E5 (or its decimal notation, 2268899813), all you'll find are results referring to MMBN. I guess they just rolled their own algorithm and figured it was good enough without properly testing for randomness or something.



In Battle Network 1, when you inspect a random Mystery Data (I'll call them Green Mystery Datas or GMDs for simplicity's sake), it will determine the item you get as soon as you press A/B to advance the text "MegaMan accessed the mystery data...". This is done via two consecutive RNG calls, where the first determines whether you get Zennys or a BattleChip, and the second one determines how many Zennys or what BattleChip you get.
Now here is the tricky part. I mentioned before that the RNG result is actually a number between 0 and 2 billion, and the way the game converts this to the desired range by doing a modulo operation. In the case of RNG call 1 it would do modulo 2, and for call 2 it would do modulo 16. It just so happens that 2 and 16 are both powers of 2, and because of this, the modulo operation is equivalent to doing a bitwise AND operation. (This is not the case when you do a modulo operation with a number that's not a power of 2.)

It might not be immediately obvious, but this last part actually violates the RNG principle that I outlined above, namely that you cannot predict the next RNG result if you don't know the current seed. It turns out that if you know part of the RNG result, then you also know part of the current seed, and you can actually make predictions about the next possible RNG seed + result.

I think the easiest way to demonstrate this is by an example, so it's time to do some math.

Let's step into the shoes of the game for a bit. Suppose that the player is in Undernet 11, and has just accessed a GMD, so we need to figure out what item to give them. Let's assume that we will be giving them a CannBall A chip. Okay, let's take a look at the BattleChip drop table for Undernet 11 GMDs:

0: Ratton2 J
1: Ratton2 J
2: Ratton2 J
3: Ratton2 J
4: Ratton2 J
5: CannBall A
6: Recov120 F
7: Recov120 F
8: Recov120 F
9: Recov120 F
10: Recov120 F
11: Recov150 L
12: Recov150 L
13: Recov150 L
14: Recov150 L
15: Recov150 L

As you can see the other 3 chips each have a total of 5 entries, so they are more likely to be chosen than CannBall A. That's how the game's developers control the rarity of these chips. Anyway, we want to hand out a CannBall A, so we need to hit index 5 for the second RNG call. We'll call the result of the first RNG call 'A' and the result of the second RNG call 'B'

Let's assume that we got result 5 for the second RNG call. That means we got the RNG result, 'B', and did a modulo 16 operation on that, which equaled to 5:

B mod 16 = 5

Because 16 is a power of 2, this simplifies to a bitwise AND operation on the lower 4 bits:

B and 15 = 5

If we represent B as a binary number (so only using 0s and 1s), that means B must follow the following pattern. The lowest 4 bits of B are 0101 in binary, which is 5 in decimal. For any bits we don't know the value of, I've put an 'x'.

B = xxxxxxxxxxxxxxxxxxxxxxxxxxxx0101

Well, let's go back to the RNG formula that the MMBN games use.
Knowing the result, which is B in this case, we can work our way backwards to find out what the previous seed was.

First, undo the right-shift by 1 bit:

B' = xxxxxxxxxxxxxxxxxxxxxxxxxxx0101x

Then, undo the exclusive OR (XOR) with 0x873CA9E5. Luckily, this is the same as just doing a XOR with the same number again. If we represent 0x873CA9E5 as a binary number we get:

10000111001111001010100111100101

So let's do another XOR on B' with that number, and we get:

B' = xxxxxxxxxxxxxxxxxxxxxxxxxxx0111x

Now we need to undo the "add 1". This is a bit tricky as we don't know the lowest bit of B'. We know it's either a 0 or 1, though. Let's just account for both cases:

B' = xxxxxxxxxxxxxxxxxxxxxxxxxxx01110
or
B' = xxxxxxxxxxxxxxxxxxxxxxxxxxx01111

Okay, so now let's subtract 1 from that number.

B' = xxxxxxxxxxxxxxxxxxxxxxxxxxx01101
or
B' = xxxxxxxxxxxxxxxxxxxxxxxxxxx01110

Finally, we need to undo the bitwise rotation. This is simple enough:

B' = 1xxxxxxxxxxxxxxxxxxxxxxxxxxx0110
or
B' = 0xxxxxxxxxxxxxxxxxxxxxxxxxxx0111

So what now? We applied the RNG formula that the game uses, but in reverse. In order to obtain the final result of 5, we now know that the input seed value that was used follows the pattern 1xxxxxxxxxxxxxxxxxxxxxxxxxxx0110 or 0xxxxxxxxxxxxxxxxxxxxxxxxxxx0111.

Alright. Now let's look at the first RNG call of a GMD again. If the result is 0, then you get a BattleChip; if it's 1, you get Zennys. Well, we supposed that the player would be getting the CannBall A drop. That means the result of that RNG call was 0. Let's look at the RNG formula again.
Okay, so specifically the last two steps are the ones we're interested in. We just worked out the pattern for the input seed for RNG call 2, which is also the output seed for RNG call 1. So we know that the "new seed" produced in RNG call 1 follows that pattern we found.

Alright. So for RNG call 1, the "new seed" is 1xxxxxxxxxxxxxxxxxxxxxxxxxxx0110 or 0xxxxxxxxxxxxxxxxxxxxxxxxxxx0111... So let's do the final step of the RNG formula and get the result for RNG call 1.

Right-shift the new seed by 1 bit and return it as the result.

A = 01xxxxxxxxxxxxxxxxxxxxxxxxxxx011
or
A = 00xxxxxxxxxxxxxxxxxxxxxxxxxxx011

Alright, so the RNG result for RNG call 1, A, was one of the above patterns. Now we need to convert this to the range [0, 1]. Well, this was done via a modulo operation by 2, which is equivalent to bitwise AND by 1. Let's do that now:

Result = A and 1 = 1

Wait a sec. Result = 1? But that means we should be getting Zennys! Huh? What's going on here?

We went from the assumption that the player gets a CannBall A drop, but then concluded that they get Zennys. Clearly, this is a contradiction--which means our original assumption does not hold. Yes, that means that it is impossible to get a CannBall A drop from an Undernet 11 GMD!

For the same reason, it's also impossible to get the 5,000 Zennys drop in Undernet 10 in OSS. This is because this drop, originally 10,000 Zennys in BN1, occupied two slots in the Zennys drop pool, one of which can never be chosen due to this RNG quirk. When the underpaid interns developers who made OSS reduced the drop to 5,000 and removed one of its slots in the drop pool to make it rarer, they actually removed the one that could be chosen. So now, all you'll find in Undernet 10 in terms of Zenny is 10z, 20z, 30z and sadness. Fortunately, CannBall A is the only unique item that's unobtainable due to this glitch. FtrSword L, even though it only occupies 1 slot in the pool for Undernet 9, is still obtainable, because the slot that it's in, isn't one that's excluded by the RNG quirk. And later games aren't affected (as much...) due to changes in how they handled GMDs.



This is the MMBN RNG quirk in a nutshell. By doing two RNG calls right after one another, where both results use a modulo operation with a power of 2, the second RNG result ends up being biased or skewed depending on the result of the first RNG result. And because of this, certain combinations of results are impossible to get. I use the name "RNG carryover glitch" for this, since the result of some RNG call ends up carrying over into the next one.

You might be thinking, well, if the RNG quirk does that to GMDs, then I bet there are other things that it might affect. And actually, the answer is yes! There are a number of other, completely unrelated things in different MMBN games that are affected by this glitch. It is somewhat rare due to the specific requirements needed to get this glitch, but one good example is battle selection in Undernet 2 in MMBN4. That area has 4 battles with Wood viruses, but if you have Jungle equipped, you will find that you almost always only get 2 of those 4 battles, because RNG carryover glitch occurs if you get a random encounter in that exact situation, unless your step counter is very high (e.g. after an expired SneakRun). It just so happens that one of those 2 battles has a Battle GMD in it which can drop 3 BugFrags, so this actually makes it the most efficient strategy for farming BugFrags in MMBN4. Another example is that some GMDs in Battle Network 4 and 5 will only give specific drops based on the location in the map where they spawned, so if you only check one GMD spawn point in a map, it's possible you won't see all the chips it drops.

It's interesting to note that Capcom did eventually figure out that this quirk occurs, because in Battle Network 6, whenever the game needs to roll the dice, they actually do a number of bogus RNG calls and discard those results, just to advance the seed value and eliminate the effects of the carryover, before getting the final RNG result.

By the way, Greiga Master is pushing out an update to the translation patch soon which will also fix the RNG quirk for GMDs, so you'll be able to get CannBall A as God intended. Hooray!