In this blog, I like to bring up quirks that happens in video games which mostly have to do with their engineering and the causes usually goes back to something interesting in their programming.  It could be an oversight or just something that was intended, but gives out fascinating results at times.  One of the quirks that I previously talked about is luck mainly how it’s achieved and also how it’s only a SIMULATION of luck and not actual randomness.  One thing I briefly mentioned though is it might be possible under certain circumstances to manipulate the luck in your advantage, but I haven’t really pointed out much other than some examples and how TAS uses it fully.

Well, this blog post will be about RNG manipulation, specifically the recently found (well about 2-3 months old as of this post) starter manipulation in Pokemon Colosseum and Pokemon XD: Gale of Darkness by……me!  I will talk in detail how a manipulation and luck works in general before explaining how convoluted manipulating both of these games has been and how in my opinion, this is one of the most insane manip (RNG manipulation) in addition that the fact it is even possible is nothing short of incredible.

But first a little refresher on what is RNG.

What actually is RNG and how does it work in practice?

If you are familiar with any speedrunning community, you certainly have heard people throwing the term “RNG” around in everyday conversation and when they refer to it, they mostly refer to it as “luck”.  This is…..mostly true, but there’s a lot of hidden meaning behind this term that makes it much more than luck so let me address that first before we proceed because it’s going to be very important later on.

RNG means Random Number Generator and it’s actually just a way for a computer, console, toaster…..whatever thing that has a CPU to SIMULATE randomness by generating a sequence of numbers that SEEMS random, but is actually so deterministic, you could predict every numbers in the sequence if you know the term in the sequence you are in (called the “seed”) and you know how the RNG works.  Because of this, calling it “random” isn’t really correct, it’s more referred to as a PSEUDO random number generator: it gives the IMPRESSION of randomness, but the reality is there’s nothing random about it inherently.

To show you what I mean here’s the VERY simple RNG algorithm in both Pokemon Colosseum and XD, it’s a very simple formula:

seed(next) = seed(current) * 214013 + 2531011;

Yes, the source of ALL randomness in both of these games is a mere multiplication followed by an addition, you can’t be more simple than that!  It really shows you how nothing is random about this, but if you actually plugged a number in this, the result will seem not related at all to the number you put in and if you keep running this in chain with the results you get on each step and note the result, this is where the randomness starts to go in: they don’t seem related AT ALL.

In fact, this is even worse because this particular formula combined with the GameCube system stores the seed in a value somewhere in RAM that has 2^32 possible values and a mathematical proof tells you it GUARANTEES that this formula it will go through all the 2^32 (about 4 billions) possible values when you call it in chain before repeating itself!  For those math freaks that are interested in the subject, I recommend you read more about the LCG which is the name of this RNG algorithm, it won’t be necessary to understand the manip, but it can be fascinating to learn why this works so well while being that simple.  To show you how random they seem, here’s the first 100 seeds of this LCG starting from 0 as the initial seed:

2531011 505908858 3539360597 159719620 2727824503 773150046 548247209 2115878600 2832368235 2006221698 2531105853 3989110284 2222380191 2165923046 1345953809 1043415696 586225427 3870123402 2343900709 3109564500 3522190791 2090033518 3566711417 3845303128 3357146299 2234209426 4040255757 146855836 2784856047 4262888182 2307812833 2186156320 2202588003 1218146458 3255514357 1391793124 1547432727 2974409086 816345673 2204347368 4082973451 2598295970 3997112797 1172243756 2070757183 1349033222 2947833777 4186407856 2644169651 3265965994 500021189 1927072628 2952203367 3032601998 3745830425 763478136 808009051 470291122 152809133 1262519996 3596810895 3073944342 3912267137 2219737664 3566475267 550773434 1594990229 1825593092 366913975 3770957214 923917801 3013470472 2454389675 1094713282 1000089469 1044798540 180074975 3941575974 4039618385 1179915472 3240206419 2354104778 774629733 3687888532 15715079 274340270 183798201 1896424856 2345635323 677355730 3493168205 1402045916 1049918767 758555446 3850308897 914963296 2188405923 2610537690 3954284597 840886820

The point I am trying to make is this is what RNG is: a sequence of seemingly random numbers or seeds generated by a deterministic (does the same thing no matter what) algorithm which is called on the seed to get the next one.  The randomness is only there because in practice, you normally never know either the current seed or the number of times this algorithm has been ran so the only thing you can guarantee is that the current seed is a number…..that’s ALL.  This is by design because it makes everything for you, as a player completely unpredictable.

As for how does a mere number influence stuff like critical hits or drop rates in RPG like Pokemon, it’s because they use arbitrary criteria on the seed they get after calling RNG (this is why RNG is only called when something requires randomness, it’s to not have patterns in the outcomes).  For example, if you want a 50% drop rate, you could just check if the seed is even or odd because as far as you are concerned, the seed can be ANY number so there’s an even chance here.  You could use even more math formulas if you wanted a more complicated rate like 29% or something, but the point is, the seed is ALL you need to do anything you want with randomness.

So you probably can connect the dots on what an RNG manip is: it simply involves to have a way to know the current seed AND the number of time the algorithm has been ran.  In other words, you TRACK the seed.  And if you track this, you can predict EVERY outcome in the game because you will know when the seed will meet the criteria of the outcome you want.  Basically, you are in control of everything so you can start to laugh in hysteria 😀

Okay that was all the boring theory so now let’s get to talk about both of these Pokemon games and why we would want a manip.

Reset, reset, reset…

Pokemon speedruns at least from what I noticed seems to have one thing in common: the route relies on the starter(s) having good stats (stuff like IV, natures….other complicated Pokemon things) because they expect the starters to have decent chances to survive through the run.  I mean it’s a speedrun, you don’t want to spend an hour grinding cause your level is low.

Pokemon Colosseum and XD are no exception which is a problem because the stats like other games are random and the desired stats are strict enough that getting a run past the 20 minutes mark is, in theory, 3-5%!  This is so incredibly low it was common for runners to spend hours and hours of resets without even attempting the hardest parts!  In fact, most runs never got past the starter and some of them would get past it, but both of these games needs a secondary Pokemon in the route that also has strict stats so it would frequently die there too.

So the interest of having a manip is obvious here: if you could at least manipulate the stats of the starter of each game, it would raise the probability to as high as 30% to have a run past the secondary pokemon!

Which is where I came in as I have pretty good experience in reverse engineering (RE) GameCube games so I started to check if  it was even possible in the first place and…..it was already a terrible start because of 2 obstacles: the system clock and the naming screen in each game.

The system clock, biggest wall in this entire project

I never thought I would hate a clock this much in my life, but here we are, I REALLY hate this clock.

GALE01-5
The concept of a time keeping device has never been so frustrating to deal with….that and trying to read the time on those clocks with the sticks on them

So after some quick RE, I determined that the initial seed is the lower half value of the clock (the least significant part).  It just takes it from the system quite early when the game is booted and that’s your initial seed.  So, if we could find our seed on boot, we should be good.

The first thought would be “lol just set the clock and boot the game frame perfect”, but NOPE, this clock is INCREDIBLY precise, so much the mention of a frame (which is the length of time inputs are polled, usually 1/30th or 1/60th of a second) is meaningless.  The system clock speed is 1/12 of the CPU’s own clock speed which, if you do some math, gives you one tick every 22 nanoseconds!  To put this in perspective, a frame in the GameCube menu is about 0.017 seconds (so the 1/60th of a second), 22 nanosecond is 0.000000022 seconds!!!  This is so precise the disc spinning in the system is WAY too much variation!

So that’s not happening meaning no matter what, you are never going to know your seed on boot which is a huge blows to the possibilities of a manip.

The naming screen, why did you have to use random animations?

Let’s say through insanity (which is what this manip is), you get past the clock and you ARE aware of your seed, well you could be able to get to start the new game, but then you come to the problem of the naming screen where you enter your trainer name and confirm it before the game starts.  Quick RE reveals that the starter for both games is generated AFTER this screen and for the run, it’s mandatory to pass through it so no matter what, you HAVE to be able to track the seed through this screen.

The naming screen is a huge problem because it calls RNG constantly!  Each frames, it calls RNG and this is due to the little pokeballs spawning in the background in Colosseum for example, some random properties are determined with RNG like size, position or time to be on the screen.  Since we assume you would know your seed by this point, this is normally not a problem because you just continue to track it, except that this screen REQUIRES user input which are variable and thus, screws up the manip because it makes it frame perfect and potentially impossible.

GC6E01-14
Who would have thought that the process of naming yourself would be so difficult and random?

HOWEVER, I done some hours of RE to determine that fortunately, there’s hope here because the number of calls the RNG does is completely frame dependent.  Each frames where the naming screen is rendered, it calls RNG once to determine a 10% chance that if it pass, it will call RNG 4 more times.  This happens very consistently each frame and what this means is that since you would know your seed by this point, you can predict when the 10% passes or fails every time and as for the amount of frames….well obviously you don’t know that, but you know what is going to happen for a given amount of frames.

So you could simply predict the starter for a bunch of frames amount, present it to the runner and the runner will be able to pick the amount of frames that gives the stats they want.  This is possible because there’s only one input that matters: the very last one spent on that screen which is confirming the name, even if the runner does additional inputs, it doesn’t change the consistency of the RNG.  In other words, through complete luck in how the game works, this obstacle only makes the manip frame perfect, but not impossible!

….except there’s a little minor exception and that is on Colosseum.  Although both games allows to enter a custom name, if you do so on Colosseum, every frame the keyboard is rendered, more RNG calls happens per frame and for whatever reasons, this isn’t the case for XD.  The reason this is bad is because it breaks the consistency we want: that each frames calls RNG 1 or 5 times, now it depends if it’s a frame where the keyboard is rendered or not.  By the end, you wouldn’t know how many frames lasted while the keyboard was rendered or not, the only way you would know this is if you did BOTH the “new name” option AND the name confirmation frame perfect.  Since ONE frame perfect input is already 1/60th of a second…..2 of them in a row is simply not happening.

GC6E01-17
Biggest mystery of the entire project: why this screen screws up everything, but not on XD?  Who knows!

This unfortunately incurs a 3-4 seconds time loss in the run because naming yourself “A” instead of “WES” does make a difference when the text scrolls.  A worthy price to pay however considering how much more likely it would be to get the starter the runner want.


Basically, most of the challenge of doing a manip in this game has to do with that clock: we need a way to find our seed AFTER booting and once it is found, track the seed until reaching the new game option and we’re done!

This sounds impossible, but actually, a Japanese programmer had a brilliant idea.

The Battle Now/Quick battle menu

Both games have something I will refer as random quick battle which is a neat little feature: it allows you to battle against the CPU, but your team and theirs is randomly generated from predetermined sets.  This was originally supposed to just be a way to do a very quick battle, but for our purposes, it turned out to be our savior.

You see, in both games, before you actually start the battle, there’s a confirmation prompt that not only asks you to make sure you want to start the battle, but it also displays information of what battle setup was generated.  The information varies for each game, but if you take Colosseum for example, you get to know your trainer name (which is random among 3) and you get to know your team (which is random among 8).

GC6E01-18
This is how the confirmation screen looks on Colosseum, notice that the trainer name and the team changes randomly each time you reach this screen

Now, I want to remind you that the output you see on-screen is DIRECTLY related to a math result performed on the seed to determine them.  What this means is that whatever the seed was at the moment you chose to see that confirmation screen, it HAD to have generated the information you see on the screen to be the correct seed.

A Japanese programmer by the name of “ginzaru” had a brilliant idea: what if we run simulation on all or a range of the ~4 billions possible seeds and put it in a re-engineered version of the team generation process and drop the seeds that doesn’t match the information the runner see on the screen?  In fact, this can be done multiple time in a row, you could back out the confirmation screen and go back to it, it just so happens the main menu of both games don’t call RNG much.

Eventually, you would be left with only one possible seed which HAS to be the current one and because we were in the main menu this whole time which doesn’t call RNG, we can track it to the naming screen and BOOM, it would be done!  You could even attempt to regenerate additional teams after finding your seed in case you don’t like the predictions you would get for the naming screen so essentially, it will allow you to pick and choose the prediction you want!

….unfortunately, life has to be complicated sometimes and we were actually very far away from it being practically done.  The program the Japanese person did is incredibly inefficient, not because of the language barrier (which forced me to read like 10 Bulpapedia pages of Japanese Pokemon names), but it’s because I could tell very quickly that the algorithm was just not optimized at all.

Screenshot from 2018-09-08 18-02-37
This is “xdseed”, the Japanese program ran under Wine

It’s made in a high level language called C# using the .NET framework which is normally good for most cases, but it’s really not the best if you want the best performance for a task as intensive as doing billions of math on numbers quickly (also, you can’t let the runner wait more than 1-2 minutes or it won’t be worth it/make them very sad).  The other problem is the performance it claims to be able to do was very poor compared to some mock-ups I made in C++, essentially, it should not take that long.  Plus, it only accepts to search in a specific range of seed you have to enter manually….which is very odd and very unfriendly for the user.

Just to make this more interesting, the programmer has not released the source code of the program and I unfortunately don’t speak Japanese so asking them to have it would have been complicated.  This is a huge blows because the program actually implemented all the RNG calls until the team generation which is all you need to do a reliable seed finder.

Essentially, my first goal in this project is to prove that it is computationally possible to do this method.  If it is possible for most computers to do this, we have a manip.

The journey starts: the proof of concept

I want you to realise first what we are dealing with here.   The clock shuffles the initial seed so on boot, it could be anything from 2^32 or about 4 billions values.  After boot, through the magic of a RAM search and dolphin, we can see that the seed advances a lot before even reaching the first battle confirmation.  In fact, just before reaching the title screen, thousands of RNG calls already happened!  There’s also some thousands happening when entering the battle menu, and finally, a couple of thousands when generating the actual team.  The number of calls is variable because of many reasons, but I realized that the Japanese program was kind enough to put the number of calls that happened in each set before the battle confirmation (it’s the numbers you see before the seed at the end).  Therefore that program must have been accurate in its implementation.

The issue here is we are at around 5-6 thousands RNG calls PER SEED which are variables and we have about 4 billions of them, that’s a LOT of math for your poor little CPU!  In fact, if you take a look at the RNG formula, you will see there is an integer multiplications which is normally easy peasy for a CPU to do, but it’s not free and doing several billions of them in a row is REALLY showing that.  In fact, when I reached the point where I had a working way to test this, even with the assistance of using fully my 4 cores on my CPU, it would complete the first filter in 10-20 minutes!  This is so slow, it’s unacceptable, we are trying to make this under 2 minutes, how the heck can we do a 1000% performance improvements?

This problem is what ended up making this manip amazing because it sounds impossible, but to be honest, I love challenges like this.  This is one of the main reasons I love programming so much: I love to think hours upon hours upon a problem like this to finally find a solution and feel accomplished I did; one of the best feeling ever.

After realizing the raw workflow is not going to work, it’s clear I had to find a way to reduce it.  And then I realized something: the clock is editable, why not use that to my advantage?

Using the clock

Okay so I mentioned that the clock makes it impossible to know our seed on boot, but maybe it can tell a range of values where it’s in most likely.  Imagine the following scenario: the runner sets the clock to the value of 0 and boots the game as fast as possible.  Now obviously, we don’t know the value of the seed, but booting the game doesn’t even take 30 seconds, it’s a short time and the initial seed would very likely fall into a range of say 5-10 seconds of time depending on how the stars aligned on that clock the night the GameCube was booted or something.

There’s actually ways to optimize this because Dolphin is so good that it actually emulates pretty well the GameCube and Wii menu and it even has pretty good emulation of the clock so I can test stuff and do some TAS to find the least possible amount of frames to boot the game.  I can even test the reliability of my solution because Dolphin supports booting the game from the system menu.

Although here’s a fun bit: in my tests, I discovered 2 issues (this one and this one) relating to the clock with the emulator and I had to submit fixes so I could test things (the first one especially is very funny because it essentially meant the Wii clock’s value at 0 in Dolphin was wrong for MANY years and no one noticed it!).

Screenshot from 2018-09-08 18-24-06
This is a snippet from the source code of Dolphin BEFORE the first clock fix. Who would have thought that this comment was foreshadowing an ancient bug that I would end up noticing?

After what seemed like days of tests, I found out that both on hardware and on Dolphin that we can safely assume the seed will be in a 5 seconds range which gives us about 200 millions seeds.  That’s A LOT better than the 4 billions we had, but is it good enough?

Well at this stage of development, I had no implementations of the game’s RNG calls and I didn’t want to do them until I am very sure this is possible so what I did is I simply put the RNG formula and simulated a workload of 6 thousands RNG calls 200 millions times which is really a worst case scenario.  The results were MUCH better, but it wasn’t quite there yet, it would take a couple of minutes, but this is promising!

However…..I had another trick: precalculation.

Precalculating stuff

I mentioned earlier there’s a lot of calls happening even before the team generation process, but these batches of calls only needs to be ran before the first filtering process and if you have a predefined range of seeds (which we do because we do a trick with the clock), the lists of seeds before the first pass will always be the same.  So I had a clever idea: I would run the calls before the first team generation only once and output the seeds into a file.  That way, when we do the first pass, the program already has the seeds ready to actually go through the team generation thus optimizing the process significantly.  The file takes a while to generate and can be quite large, but it can be kept for every further findings so it’s worth it in the end.

Again, I had to do simulation for this to give me an idea, but this time, I had significantly fewer calls per seed, about 2-3 thousands.  The results this time were amazing: on my computer, it took 10 seconds!  This was fast enough that even if you had a dual core low-end CPU, it would have taken 20 seconds still which is perfectly acceptable!

The manip was proven to be possible YAY!!!!!

The fun part: actually programming everything the game does

OKAY WE HAVE A MEANINGFUL PROJECT WOOOOOOOO!!!

xycil4e
I needed an excuse to link this GIF 🙂

So, now I can program stuff without worrying it would be for nothing, it’s time to RE the heck out of the game!  I started with Colosseum because I actually done very little work on XD so I would have been more comfortable to program an RNG backend on Colosseum first.  The goal is simple to understand: read the compiled code of the game when it calls RNG, re-engineer that code in C++ and make sure it behaves exactly as the game (so the seed between my implementation and Dolphin matches).

The RNG re-engineering backend

This was really fun to do for me because it combines RE and programming with heavy debugging process along the way.  It’s probably one of the project I had the most fun doing especially knowing many speedrunners would benefit from this.

Screenshot from 2018-09-08 18-39-36
This is a very typical working setup when I RE the RNG of the game, notice the far right side of this screenshot is supposed to be the game, but Dolphin has a little bug when I try to screenshot.  It is a very small space because I spent most of my time reading the assembly 🙂  Basically, you need A LOT of tools to do this.

There’s a lot of stuff that happened during the process like being dumb and doing a mistake and realized it was stupid after an hour of diagnosis, you know stuff like that, but eventually, I got to the team generation.  There’s actually a ton about the inner mechanics of Pokemon I learned along the way like how was the shininess determined or how does the personality ID (PID) works and a bunch of other stuff that I never thought I would ever touch, but I guess I did 🙂  To give you an idea of how complex it gets, here’s a snippet about shininess from Bulpapedia:

Shininess

00000000 00000000 00000000 00000000

From Generation III onward, whether a Pokémon is Shiny depends on its original Trainer‘s Trainer ID number and secret ID number and on the Pokémon’s personality value. The high half of p (highlighted in red above) is referred to as p1 below, while the low half (highlighted in blue) is referred to as p2. Mathematically, p1 can be derived by calculating p / 65536 and rounding down the result, while p2 can be derived by calculating p % 65536.

S = IDTrainer IDSecretp1p2

A bitwise exclusive or operation (or “⊕”) on inputs a and b, written as ab = c, outputs c such that, if ai (bit i of a) and bi are different, then ci is 1; otherwise it is 0. For example, 11002 ⊕ 10102 = 01102. When exclusive or is applied to multiple inputs, as in the calculation for Shininess above, it may be more easily understood as, “If an odd number of bits (at position i) are 1, output 1″. This operation is commutative.

From Generation III to V, if S < 8, the Pokémon is Shiny.

One of these adventures is so funny it’s worth to share.  The game kept a feature called assertions in the retail version which is a common feature in software development that allows developers to inserts conditions in the code that if it fails, it will literally crash the program with a custom message set by the programmer.  The idea is to find bugs that causes something that is theoretically possible, but in practice should NEVER EVER happen under ANY circumstances.

For safety reasons, this is normally only used in development and just disabled in the release version of the program….however, this isn’t the case for Colosseum!  In fact, in the team generation function, I stumbled across these assertions and this is what the logs of Dolphin shows me when I try to trigger one manually (you can’t trigger one without hacking or using the Dolphin debugger like I did):

Screenshot from 2018-09-09 14-05-48
Even if you don’t understand what this is, it looks pretty angry!

After these logs appeared, a crash followed a few seconds later with a very annoying tone constantly playing as audio.  The interesting bit here is this is a special type of logs not generated by Dolphin, but by the game and Dolphin can show me these logs.  Here, it seems to be REALLY mad that a certain piece of text isn’t of an appropriate length and then it prints me low level debug information about the state of the system.  This is interesting how a feature that shouldn’t have been enabled in the retail version is in and the funny part is these actually helped me to reverse engineer the code!

The team generation re-engineering was a huge challenge because there’s a lot that happens there.  Essentially, when the game generates a team, there’s different criteria the game wants when it generates the Pokemon.  For example, it may want a certain gender or nature or not being shiny (hence the need to understand the above snippet), stuff like that, but the problem is to get these, the game has to continuously generate until it finds what it wants.  This made me required to implement the generation algorithm AND to take note of the different criteria the game wants and god it was just a mess of stuff that the game needed to properly track the seed.  There’s so much I had to fill the code with comments 🙂  Oh also, this is why the team generation is very complex to re-engineer, it wastes a lot of call to generate the Pokemon since it drops most of them.

screenshot-from-2018-09-08-18-54-23.png
These are data that I had to put in the code to properly re-engineer the RNG, getting them and entering them is as painful as it sounds 😦

After what seemed to be 2 weeks of hard work, the first seed has been correctly found with the finder, this was the most hype moment of the project, I even skipped sleep that day because I was this hype about that moment, it actually happened at 4 AM that day 🙂

Screenshot from 2018-04-30 05-38-22
This is the screenshot of the very first seed that was correctly found, god bless 0x85AD0E56 😀  The little dialog tells the actual value in Dolphin.

Soon enough, I had a working program on command line to find the seed.  I released the program along with a YouTube videos explaining how to perform tests on this.

People tested it and it was a success, people were able to find their seeds under an acceptable length of time and they seem to be okay with the process as convoluted as it is!

The RNG predictor

After this reassurance people would be okay with the most complicated part of the manip, I now focused on the predictor because the naming screen forces me to present the different stats for the number of frames it would have elapsed.  Although, I took only a day to realize the algorithm of the naming screen was very simple to re-engineer, the hardest part was the frames heuristics.

You see, I had to TAS this screen heavily because there’s some edge cases to take into consideration.  First is that I had to TAS to see the minimal amount of frames it would take to confirm the name so this is where I had to start my predictions.  Then I realized before the first RNG frame, it for some reasons calls the render function which has the RNG call 500 times, probably to have an initial background so I had to take care of these.  Then after, I had to also include the frames AFTER the name has been confirmed because the screen is present for some seconds before fading out.  Finally, I reached the holy grail: the starter generation, but because I plan to output all the interesting things like IV or nature, I had to program a function to handle this.

I put all that in a loop and integrated this in my little command line program and now I had a finder + predictor all in one to test!

Screenshot from 2018-05-20 04-01-10
A very early version of the output of the predictor, this was mainly made for me to test before implementing it in a graphical interface.

After the initial tests on Dolphin, I moved over to hardware to test it and at the time, the only timer to properly time an input like this was the eon timer which only works on Windows so I had to use a virtual machine as I am on an Arch Linux OS.  This gave an interesting testing setup, I don’t think I got this convoluted of a setup to test my program 🙂

After some adjustments were done, I finally had the predictor to be reliable so this was a huge milestone: I had a GUI-less working version of the manip and it was convincing, it WOULD be able to manip and it would take 1-2 minutes per attempt (you still have to time an input frame perfect, but that’s really all the hard part to it).  Colosseum was definitely done as far as the backend was concerned so I only needed to implement XD before implementing the graphical interface.

Moving on to XD or laughing face 😀

Now as I expected, XD was…..mostly uninteresting because it behave very similarly to Colosseum, many of the code have the same semantic or at least, they are very close.  It was very quick to get the pokemon generation where it became much more complicated.

The battle confirmation screen of XD is very different, instead of showing a trainer name and a team, you know BOTH your team and the player’s team (though, each are among 5, they are for some reasons different depending if it’s you or the computer) as well as the HP stats and genders of the pokemon.  Also, you see EVERY pokemon involved as it is only a 2 vs 2 which means there’s much less pokemon being generated than Colosseum which is promising because it indicates the seed finder can go through the calls faster.

GXXE01-2
As you can see, this is very different from Colosseum.  Both teams are random among 5 and the HP is random due to the random IV and EV.

Unfortunately, it would have been so fast if it wasn’t for the fact the game also generates the EV (effort value, 1/4 of a stats point at level 100) at random and the algorithm  to do so…..is very complicated.

Screenshot from 2018-09-08 19-11-42
HOLY MOLLY!

It actually is simple in concept: it tries a bunch to aim for a good sum of EV, but if it fails, it manually adjust, but still, this was a pain to go through the compiled code to re-engineer it 😦  The reason this makes the process slower is because well there’s a lot of calls introduced with this as it usually doesn’t reach good EVs quickly.  Another thing that made it difficult is I had to essentially calculate the HP stats which meant I had to store some properties of the predefined pokemon such as the base HP stat.

However, and to my satisfaction, if you enter the HP and the teams, it is still decently faster than Colosseum and it also takes twice as less passes because the HP makes the narrowing down process much quicker.

After getting through the pain, the rest was very easy because the naming screen behaved very similarly and same goes for the starter generation.  So really, except the team generation which was kinda hard to do, it just was very similar to what I had done before so it was kinda easy.

Nonetheless, I finally have a predictor and a seed finder for both games.  After an hour of intensive tests, I was convinced I can FINALLY move on to even more fun stuff: the graphical interface (GUI)!

Putting some graphics in the interface

I like command line, it’s minimalist and from a programmer, it’s incredibly easy to control what’s going on, but it’s really not good user wise because it’s very unfriendly so I need to do a convenient interface for anyone to use without much trouble.

It sounds mundane for me as I already have pretty good experience with the Qt framework to do GUI, but this one was challenging because as you may have realized by now, nothing has been simple in the backend! 😀  Pretty much everything has been complicated or convoluted and required several clever manipulations to get what I wanted and I have to put a graphical interface that makes it simple.  It’s definitely not easy.

The biggest challenge was again, it’s the seed finder, this finder alone I swear I think I spent 70% of the entire project on it because it really has been the major point of difficulty because of that mean clock 😦 (did I mentioned I hate that clock?)

The seed finder with a wizard!

So the idea I had is when I look at the steps the user has to perform to do the manip is it’s very much like a cooking recipes where you do the instructions exactly as indicated and it the right order.  One of the step, entering the information displayed on the screen, repeats itself indefinitely until we are done.  So I can’t really have one screen layout, it just would be weird and seem too imposing for the poor user so that made me think of a series of dialog with a linear path in them and each of them having one step of the “recipes”…..WAIT this is exactly what is wizard is!

This is more common on Mac OS or Windows, but have you ever downloaded a program and when you came to run its installer, the first thing you saw was “Welcome to the installation of the thing, this wizard will guide you through the installation process” or something like that with a next button that people kept mashing without reading?  Well that’s a wizard and it’s supposed to help the user to do a normally complicated, but orderly process, you know, like a cooking recipes.

install01
A typical example of an installation wizard, YES I AGREE TO THE STUPID LICENSE AGREEMENT!

This seems to perfectly match the manip process!  There’s one catch however: wizards aren’t usually done to repeat themselves, they just go from one dialog to the next so this was going to be a bit complicated to do.  In fact, I pretty much had to workaround several things that the Wizard Qt offered JUST to implement a repeating steps, some of which I am not really proud of, but it works so yay!

Screenshot from 2018-09-08 19-30-12
This is an earlier version of the program working REALLY hard to find the seed.  Note that when this ran, your ENTIRE CPU and all of its cores were maxed to 100% usage which means it was working at its fullest.  It was so much I had to add an option to limit the number of threads later because live streaming software hated that!

I also learned by the way how to perform asynchronous tasks with Qt because especially on the first pass, it is a long process and if you just run your code, the GUI will have no room to breath so it will just freeze completely without seemingly doing anything, but it’s just waiting for a long running task to complete.  This sucks because I want to show a progress bar that updates, but thankfully, learning how to run the task asynchronously meant the GUI wouldn’t freeze and it can still receive updates, but my long running task can do its thing.

After a long time of fiddling with the wizard mechanic and working around it, I was finally able to get a really nice looking wizard complete with full instructions.  This was one thing I really needed to do as a priority by the way: have the program explain itself and not have to refer to say a video or a manual to use it, the instructions are right there in the wizard.  I wanted to do this because I noticed way too many times on specialized tools like this one where the author expects you to read much more documentation than you should because it could have been made obvious in the program itself.  Especially for a complicated, but simple to follow process like this one, I think it benefited much more from the wizard and the pain to make it was worth it.

Screenshot from 2018-09-08 19-28-04
An earlier version of the instruction page. As you can see, I put a lot of details in these instructions because to me, it was important that the program explains itself what to do instead of reading a guide on it.

Okay this was the hardest part so time to move on to the predictor, but also the settings system as I’ll explain why settings are necessary in this program.

The starter predictor, now with colors!

So, there’s one thing that I mentioned at the beginning about the runners wanting to have specific criteria of the stats with the starters, but the problem is only a small percentage are considered acceptable for runs.  This means I can’t just present the list as is and have the runner do a scavenger hunt for them. I mean they can even decide that none of the predictions are good and generate an additional team to have new ones.

What can I do with this problem?  Well I can do fun things with Qt and I never messed with INI settings before, but I had the idea of just storing the criteria the runner wants in an INI settings file or something and use color coding to indicate in the prediction if the criteria is met (green) or not (red).  This would allow people to save common criteria and also to very quickly visualize which predictions is good and if not, why it isn’t.  Having settings is also useful for other things like the margin of error of the clock or the max length the runner is ready to waste waiting on the naming screen.

Screenshot from 2018-09-08 19-36-36
A view of the criteria settings, this window by the way was very tedious to do 😦

The part with the colors was quite tedious to do (it’s a lot of boring conditions that are repetitive to type), but I learned that INI settings were VERY simple to do with Qt and I really liked doing them.  They were tedious however because there’s a lot of them and they are very repetitive (there’s 6 different IVs, there’s 25 natures and it just goes on and it’s just annoying, but not hard to do).  However at the end of the day, I finally got a nice looking settings screen as well as a really cool looking predictor, I remember I showed screenshots of early version and people seemed to love it 🙂

screenshot (copy)
This is how the predictor ended up, the color looks nice!

After that, I had to do miscellaneous stuff like a check box to hide all the red ones, a reroll button to signal the program that you generated an additional team etc…. and soon enough, I eventually ended up with a feature complete program WEEEEEEEEE!!!

Final tests and release

So eventually, I felt very confident in that I put all the basic features it would need for a first beta and so began the very last tests before release, this is extremely important because the project had about 4000 lines of codes at this point so it better work when I release it because as a project grows, debugging becomes much harder.

So I had to use yet another convoluted test setup, but this time, I was to sit for 2 hours straight of JUST testing the finder and the predictor, I had to go all in here because it HAD to be consistent.  To alleviate how tedious the process would be, I put the Kirby Air Ride OST on my phone speaker while I was doing the tests 🙂

img_20180909_004928.jpg
This is a pretty good depiction of what it took me to test this, I would find my seed and aim for a frame for 2 hours before noting the result in the text editor; 1 hour per game and it has to be consistent.  To note, this LCD monitor doesn’t support composite so I had to use a VERY crappy VGA converter 🙂  Notice also that eon timer ran in a VM.

Colosseum initially passed everything, but the tests detected an off by 8 frames errors in the predictor of XD making me really feel good I decided to do this much test.  After this fix, it passed so I FINALLY RELEASED THE FIRST BETA FULL VERSION OF THE PROGRAM!!!!

June 24 2018 is the date where RNG manipulation became a thing for these games 🙂 The project and its code is fully available on Github.

After the first version

Now this was a beta version so I expected to have some breakage…and of course it happened, but luckily, it didn’t affect directly the manip, it would still work, just that it needed some adjustment, but it did had a non major crash.  To be honest, I expected this release to go WAY worse so I was a bit relieved it was quite good 🙂 People did started to use it in run attempts so that was a fantastic start.

I got some minor feature request, but to me, this project was far from over because one thought that haunted me throughout the entire project is the fact this manip relies on a heuristics by that freaking clock (I hate it….).  You could still have failed the manip if you didn’t boot the game fast enough, the disc may have taken too long, oh and I forgot to mention, but doing this on a Wii was very annoying and even slower for the finder (the Wii’s clock is 1.5 times faster making it take longer to narrow it down).  Although to be fair, people would still have done the manip because it helped THAT much, but I hate this when it feels I am forced to do a very messy way of handling this problem and when I have this feeling, I constantly try to think to make it better.

Detaching us from the clock (because I hate it)

I really got crazy in ideas.  From improving the precalculation phase to many other things and I even ended up seriously considering using the graphics card to do all the math (because a graphics card is actually a beast for parallelism workflow like this one) using OpenCL.  Honestly, it was an insane idea, but what was done was SO INSANE I consider it miracle of craziness.

After the release of the program and the first bugs were fixed, Thurler, a member of the pokemon speedrun (PSR) community contacted me about a way to optimize the precalculation yet again, but it would be much better.  It was a complicated mess of clever use of data structure that would have increased the file size by a lot because it involved storing all the seeds AFTER the first pass so you could skip the overhead, but have a in my opinion negligible improvements compared to the huge file size (it was gigabytes I believe).  I was honestly very iffy on the idea so I suggested to experiment more with it before I can take a decision.

Then they handled the code to Dabomstew, another member of PSR who also made another tool for this game called the stat predictor.  Dabonstew experimented with this method when they noticed something incredible: after the first pass on ALL the ~4 billions seeds for ALL possible team combination in Colosseum, only a couple of hundreds of millions remained!  WHAT? HOW IS THAT POSSIBLE?

It turns out there’s something we have been overlooking this whole time: convergence.  You see, the game does call RNG a variable amount, yes, but if you started with all the seeds, because the number of calls varies per seed, they will get mixed up and since there’s so many different seeds, a lot will end up being the same in the list.  In fact, I was aware of this because I even got this duplication problem early in the project so I had to do some codes to remove the duplicates, it’s just we never imagined it would converge SO MUCH that if you take a team combination individually, you end up with less than 10 millions seeds all the time!  This is for ANY computer, nothing to go through, in fact, it even feels instant!

But the best part about this?  We can yet again offload this to generate an external big file that contains all the converged seed (we can make sure to know which team combination the lists are related to) and after that, once the user enter the information on the first pass, we just load the appropriate list in RAM and there we go!  But you know what’s even more awesome?  This file would have been generated from ALL possible seeds in theory and only keep the one that matters meaning….

THE CLOCK CAN BE FULLY SKIPPED!!!!

Yes, and that’s because we already have our list of seeds that matters and any computer can go through them easily, we no longer need the help of the clock because we already narrowed down the list to the point where you can operate on the full range of seeds FROM THE START!

If it sounds too good to be true, well there IS some catches, but they don’t actually matter!  The biggest one is well the file generation process is….a huge beast.  Like I am not kidding here the file takes with my 4 cores CPU 2-3 HOURS to generate!  This is because it has to go through all the seeds of the ~4 billions available, figure out the team combination it belongs and add it.  Eventually, duplicates are checked and removed and you have to do this for all the seeds before finally storing the file.  The other caveat is the file end up being very large: ~725MB for Colosseum and ~400MB for XD.

Screenshot from 2018-09-08 20-11-22
This warning is no joke, it will take your CPU hostage for hours before being done, crazy!

However….none of these caveats matters because since we are generating from the same pool of seeds (so all of them), the file is THE EXACT SAME NO MATTER THE CONFIGURATION!  So I can just be nice and generate the files myself, distribute it along with the release of the program and have people do no work for their CPU and just have the files ready to be used.  Now, I DID ended up leaving the file generation function in the program for good measure, but this is so insane, I almost consider it a good CPU benchmark function because it is crazy how much of a beast this is, I actually still can’t believe the complexity of this function 0_o

The result: everything is so quick between passes you barely have time to see the progress bar!  All of this is done while skipping the clock which to me is just insane, because this is probably one of the ONLY GameCube manip you are going to hear mainly due to that clock.  One thing I should mention about XD: because the HP stats would increase the number of combination by a ton and increase the complexity and size of the file by a HUGE margin, I decided to skip them on the first pass.  And THAT is why the current version of the program says on the first pass that “You will enter the Pokémon HP starting from the next pass”.

Screenshot from 2018-09-08 20-14-39
The reason this mysterious message displays there is due to a side effect of the precalculation optimization: I can’t easily sort the seeds by teams AND HP stats so I have to only keep the teams.

There’s some things however that I need to address since this project quickly influenced the runs of the games.

After the fact: what happened?

So both before and after the release of the program, I watched a lot of streams of speedrunner running each games, especially after manip because, look it’s fun to see people use your program live 😀  Because I done this, I can more clearly see as a viewer if the manip really did anything as far as running the game goes.

The first obvious thing I noticed is the number of attempts.  It was CLEAR that this helped a ton, we went from having no runs in a day to be common or maybe 1 or more to you can really expect to have 2-3 attempts per day (though the RNG can still hate you and not give you the secondary pokemon, more on that later).  As a viewer, this was a lot better because you get to see quicker the interesting and more challenging parts of the run…..and also their death, but at least it died to other reasons than you couldn’t even attempt to do much because of the starter which is VERY early.

One less obvious thing that I started to notice is the altitude towards having good stats has changed.  Instead of taking whatever that was “good enough”, runners started to be much stricter and even made routes based on specific stuff like the type of the hidden power attack.  This was done because it became so easy to get the starter you wanted that people figured you can sacrifice some annoyance with having to reroll more often or sometime reset because the nearest good prediction was too far all this to get better stuff.  Better stats and routes became more accessible which incurred easy time saves and also increased the rate of the run to go on further because your stats are better.

Finally and to be honest I didn’t quite expected this to happen, but people I never seen done a run of these games started to want to run the games now.  In fact, it even happened that some pokemon speedrunners I was watching got back to this game because the resets wasn’t a nightmare anymore, it’s still an annoyance, but way more manageable.

In the end, noticing all these positive changes, I am very happy with how the program turned out.  I feel accomplished when I finally release a project I worked hard with, but the best feeling is knowing that the program I did helped many other people, in fact, when I am doing a project, this is in itself a huge motivation for me.

There’s one last thing I need to bring up and that is the secondary pokemon used in each game’s run.

Possibilities of manipulating the secondaries

Not only each game’s run uses a starter pokemon, they also get another one later on (Croconaw on Colosseum and Teddiursa on XD).  It would be interesting to manipulate those, unfortunately, I quickly realized it was not possible.  On Colosseum, as soon as you enter gameplay phase, the RNG keeps rolling per frame making every input frame perfect if you wanted to track the seed.  Even if you wanted to save, the nearest save is in a pokemon center quite far from the trigger to the Croconaw battle so we have the same problem.  For XD, same deal, but even if XD has a save anywhere feature, it’s still not possible because to trigger the Teddiursa battle, you need to do 1-2 inputs frame perfect to track the seed.  Considering the runner has done one 10-15 minutes ago, it would be too much to add.

Essentially, it won’t happen, but hey, it’s already insane the starter can be manipped so it has to stop somewhere 🙂

In conclusion

This RNG manip is a beast and there’s 2 main reasons why it’s probably one of the most interesting that exist in speedrunning in general.

The first is the platform, the GameCube and Wii’s clock are very precise, but when I mentioned that Colosseum and XD used the clock as their initial seed, I forgot to mention it’s EXTREMELY common for this platform at all.  This is likely because this was probably a standard way of doing this by the SDK so most games followed it (and to be honest, it’s also a ubiquitous way to do it in general like I wouldn’t be surprised if most modern games ends up doing it).  What this means is pretty much most games you can think of on these consoles has this clock problem so to have a manip, you need to do like this manip one and have a way to narrow down to one seed AFTER booting the game and that’s assuming a computer can do it!  I am sure some games are dumb and don’t use the clock, but still they should be uncommon and again, having one that exist WITH the restriction is rare and probably won’t happen in a long time.

The second reason is how complicated the procedure is, but yet can be made so simple to the user.  The program is considered by many runners to be easy to use, but the reality is NOTHING about this program is simple!  This has to be one of the most complicated manip I ever heard of and yet, it can be done under a minute and one frame perfect input.  It seems very elegant in a way which I usually am a fan of in programming, I usually go for the most elegant solution because it’s nicer overall.

All in all, I loved this project and after 3 months of work and 4 thousands line of codes, I am actually still not done yet!  I plan to bring further improvements and features to the program with the first stable version being planned in the next month.  I am very happy with this project and I just hope an opportunity like this would come up again, maybe in another game, who knows!

10 thoughts on “Controlling luck in video games: an explanation of the RNG manipulation on Pokémon Colosseum and XD

  1. You’re about 7-8 years too late on your discovery, pal. Smogon Researchers started work on this back in 2011; RNG manipulation (on emulator) was possible later that year, the Japanese figured out Retail Abuse a couple years later, and there’s a crapton of RNG tools for both emulator + Retail abuse available on the web by this point.

    For reference:
    https://www.smogon.com/forums/threads/past-gen-rng-research.61090/page-28#post-3364100
    http://www.geocities.jp/ginzaru_xd/

    Like

    1. RNG manip on emu is really not hard for any game: find the seed address (requires some RE) and track the seed, you even have access to frame advance so it’s easy and you can do it on any game with minimal effort.

      HOWEVER, for retail, they appear to be using the same program I was talking about in the post. Now, the third link doesn’t work for me (where is the translation?), but what I know is on the tab I took the screenshot, you are supposed to MANUALLY enter a range of seeds then select IN ADVANCE all the combinations of the battle confirmation with no knowledge how much pass it will take you.

      As for the program itself…..I really tried hard to test it, but it was unbearably slow. Not slow as in it will take 10 minutes, no it would take HOURS to be able to print something meaningful. I confirmed it was inneficient very early on because I did a quick program in C++ to simulate bilions of RNG calls and it was orders of magnitude faster.

      What I am saying here is that the only possibility is that I didn’t performed a proper range limitation, but the only way to do this is to use the clock which I did at first, but it involved entering the number of seconds as margin of error and then it ended up we didn’t need the clock in the first place.

      I was aware the program existed years before, what I am getting is this is the first program to do this efficiently enough that it’s way more reliable, but also fast enough that speedrunners can use it. I couldn’t have known any of the progress Ginzaru made nor what he did in the program (there was no source code, I was aware of the original website) because the only thing I had was a Youtube video showing the usage of it and I didn’t speak Japanese.

      So I am late on the method of the manip, but it existed already. As for the reliability + efficiency, afaik, I would be the first on that.

      Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s