Anonymous user
RNG correlation (Generation I): Difference between revisions
m
→Mechanics: Undid a superfluous change when doing text replacement ("~" for approximation should not be changed).
>Bbbbbbbbba (A lot of analysis that may not be easy to understand...) |
m (→Mechanics: Undid a superfluous change when doing text replacement ("~" for approximation should not be changed).) |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 20:
* For each value of the low byte, there are two ranges of the high byte.
* For each value of the high byte, there are three ranges of the low byte.
For grass with encounter rate 25, when the low byte is 0, the two ranges of the high byte are 13
Note that, in unusual cases, an extra lag frame may happen between encounter check and DV generation. This may allow some "impossible" DVs to be generated.
==Effect on the catch rate==
In Generation I, whether a thrown Poké Ball successfully catches a wild Pokémon is determined by two random bytes, the first of them drawn by rejection sampling if the ball is better than a regular one: A Great Ball guarantees it to be in the range 0
Ostensibly, this means that the catch rate is min((C + 1) / B, 1) * min((F + 1) / 256, 1), where C is the base catch rate, F is the HP factor, and B is 256 for regular Poké Balls, 201 for Great Balls, and 151 for Ultra Balls and Safari Balls. However, when B is not 256, the rejection sampling would create an RNG correlation that may significantly affect the catch rate.
Line 31:
For example, consider Tauros in the Safari Zone. Without throwing bait or rock, C is 45, and a typical value of F is 87 (it can vary a little depending on the max HP of Tauros). Therefore the success rate of each Safari Ball should be (46 / 151) * (88 / 256) ≈ '''10.472%'''. However, simulation shows that, due to RNG correlation, the actual catch rate is only about '''6.633%'''.
In fact, this is close to the most devastating effect RNG correlation can have on the catch rate. When the first RNG value tried in the rejection sampling is between 0 and 150, the probability 10.472% should be accurate. Meanwhile, when the first RNG value tried is not between 0 and 150, the probability of success drops to about 1.113%. In general, the catch rate with RNG correlation is at least 151/
Some concrete analysis will illustrate why the effect is so large in this case. Experiment shows that each iteration of the rejection sampling takes 516 cycles (2.015625 rDIV periods), and there are 23960 cycles (93.59375 rDIV periods) between the last RNG call in the rejection sampling and the RNG call for the second random byte.<ref>Thanks entrpntr for those numbers.</ref> Assuming that the rejection sampling did not get 0
# The second-to-last iteration of the rejection sampling, which must be in the range 151
# The last iteration of the rejection sampling, which must be in the range 0
# The second random byte, which must be in the range 0
Denoting those values as r<sub>1</sub>, r<sub>2</sub>, and r<sub>3</sub>, we have (r<sub>3</sub> - r<sub>2</sub>) - (r<sub>2</sub> - r<sub>1</sub>) = 93 or 94 (depending on the "sub-rDIV" value). However, those ranges are very "misaligned",
* r<sub>1</sub> must be in the range 151 ~ 184,▼
[[File:Tauros RNG correlation.png|center]]
* r<sub>2</sub> must be in the range (r<sub>1</sub> - 94) / 2 ~ 45.▼
** This range shrinks as r<sub>1</sub> increases: It is 29 ~ 45 for r<sub>1</sub> = 151, and only 45 for r<sub>1</sub> = 184.▼
From the graph, it can be seen that the only way for all three values to be in their respective ranges is that:
▲** This range shrinks as r<sub>1</sub> increases: It is 29
Furthermore, there is no way to put another iteration of rejection sampling before this and still make a consistent RNG sequence. Therefore the second-to-last iteration is in fact the first iteration.
To put this in perspective, one can estimate the probability of success, given that the first RNG value is not between 0 and 150. Ideally, this probability should still be 10.472%, since the first value is rejected and should have no effect. In reality:
* To have a chance of success, this first value, i.e. r<sub>1</sub>, must be in the range 151
* The next RNG value, i.e. r<sub>2</sub>, must hit a range with average length (1 + 17) / 2 = 9, which happens with probability 9/256.
Therefore, this conditional probability can be estimated as 34/105 * 9/256 ≈ 1.138%. (The actual probability is even lower, because the above analysis is optimistic about the "sub-rDIV" value.)
| |||