もうすぐ去年のセキュキャンから1年ですねー
ということでこのリレーブログ企画も一区切りするようで、おそらく僕の記事はこれで最後になるかと思います。
今回のテーマは擬似乱数です。ということで、ポケモンのゲームに使われている擬似乱数のアルゴリズムをいくつか紹介してみようと思います。
アルゴリズムの紹介が本記事の目的なので、ポケモンの乱数調整に興味がある方向けの記事にはなっていません。また、セキュリティっぽい話ではないけど、暗号用途に適していない擬似乱数を使うと予想できちゃうということが分かりやすいかなと思ったという意図があります。
擬似乱数とは
今得られている数字の列から、次の数字が予測できないような数字の列のことを乱数列といい、乱数列の各要素のことを乱数といいます。
擬似乱数とは、乱数列のように見えるが、実際には確定的な計算によって求められている数列（=擬似乱数列）の各要素のことです。
擬似乱数は、例えば確率的現象のシミュレーションや、暗号を生成するために使われます。暗号用途に擬似乱数を用いる場合は、暗号学的に安全であるものを用いる必要があります（今回紹介するアルゴリズムはいずれも暗号用途に用いてはいけません）。
ポケモンにおける擬似乱数
上で述べたように、擬似乱数は確定的な計算に従っているので、入力初期値（seed値）がわかれば擬似乱数列自体を特定することが可能になります。
これを利用したのがポケモンの乱数調整です。例えば、伝説のポケモンで色違いで高個体値なものが出るような内部パラメータXがわかれば、それは疑似乱数生成器によって生成されているので、その値が出るような初期seed値を狙って出せさえすれば、初期seed値から乱数の生成（擬似乱数の計算式で次の値を求めること、ポケモンの乱数調整の文脈では「乱数を消費する」などといわれる）を繰り返して、狙ったパラメータXを得ることができます。
私はDS世代の乱数調整経験者なので、DSの場合について少し説明すると、初期seedはDS本体のMACアドレス、DS本体の時刻を基準としたソフトの起動時間などで決まり、1/30秒単位の操作が必要とされるものでした。
今回は線形合同法、TinyMT、xoroshiro128+を紹介してみようと思います。
線形合同法
線形合同法は、漸化式 $$ \begin{align} x_{n+1}=Ax_n+B\mod M \end{align} $$ に従って疑似乱数 $x_n$ を生成する方法です（ただし $ A,B,M $ は定数）。
ポケットモンスターシリーズの第3〜5世代（RSE、DPTHGSS、BW）で使われているアルゴリズム*1で、$ A,B,M $の値として $ A=1103515245,B=24691,M=2^{32} $、16進数で書けばA=0x41c64e6d, B=0x6073, M=0x100000000が使われています。
線形合同法の弱点として、$ M $が偶数の場合、この規則で生成される乱数列は偶数と奇数が交互にくるものが生成されてしまうというものがあります。ポケモンでは $ M $ が偶数になってしまっているので、0埋め右シフト>>>を使ってx_n >>> 16、つまり、16進数表記で $ x_n $ は8桁で表現（上位桁がなくても0があるとみなす）されますが、そのうちの上位4桁を擬似乱数として使っているようです。
TinyMT
ポケットモンスターXY（第6世代）において、また、ポケットモンスターサン・ムーン（第7世代）では、孵化（タマゴ）に関係するところにこのアルゴリズムが使われているようです。取扱説明書のライセンスの記述で発覚したとかなんとか。サン・ムーンはそれ以外のところにはMTの改良版であるSFMT（SIMD oriented Fast Mersenne Twister）というものが使われているようです。（MTはMersenne Twisterの略です）
使われている更新式はここから見ることができます。引用します。
内部状態にはstatus[4]として4つの数字の組、そしてmat、mat2、tmatというパラメータが使われているようです。
struct TINYMT32_T {
uint32_t status[4];
uint32_t mat1;
uint32_t mat2;
uint32_t tmat;
};
inline static void tinymt32_next_state(tinymt32_t * random) {
uint32_t x;
uint32_t y;
y = random->status[3];
x = (random->status[0] & TINYMT32_MASK)
^ random->status[1]
^ random->status[2];
x ^= (x << TINYMT32_SH0);
y ^= (y >> TINYMT32_SH0) ^ x;
random->status[0] = random->status[1];
random->status[1] = random->status[2];
random->status[2] = x ^ (y << TINYMT32_SH1);
random->status[3] = y;
int32_t const a = -((int32_t)(y & 1)) & (int32_t)random->mat1;
int32_t const b = -((int32_t)(y & 1)) & (int32_t)random->mat2;
random->status[1] ^= (uint32_t)a;
random->status[2] ^= (uint32_t)b;
}
ポケモンではリポジトリ内のsample.cで設定されているのと同じ値にmat、mat2、tmatは設定されているようです。具体的にはmat1 = 0x8f7011ee、mat2 = 0xfc78ff1f、tmat = 0x3793fdffです。
ちなみに、この更新式は頑張ると $ s_{n+1}=s_n A $ みたいな連立方程式の形で表現できるらしいです。
xoroshiro128+
xoroshiroというのは、「xor」「rotate」「shift」「rotate」を略したもので、xorshiftという擬似乱数生成法の改良版にあたるようです。
ポケットモンスターソード・シールド（第8世代）のレイドバトルではこのアルゴリズムが利用されているらしいです。
xoroshiro128plus.cをみると、内部状態を $ (s_n^0, s_n^1) $ のペアで持ち、更新式は
ただし $ R_l (s,x) $ は64bit整数 $ s $ を $ x $ bitだけ左シフトして、あふれた桁を右側に付け足すようなものになっています。（イメージとしては、「12345」を2つ左シフトすると「34500」になり、あふれた「12」を右に付け足して、結果として「34512」を得る、みたいなことを2進数でやっている関数です。）
最後に、これで得られた $ (s_n^0, s_n^1) $ を用いて、 $ s_n^0 + s_n^1 $ で疑似乱数を得るようなアルゴリズムとなっています。
次の記事はこちらです
*1:第5世代ではメルセンヌツイスターも併用しているとかなんとか
