BDSPの乱数調整に関するメモ

# BDSPの乱数調整に関するメモ ## はじめにあけましておめでとうございます. [**ニアト**](https://twitter.com/21i10r29)です. 2022年もよろしくお願いいたします. さて, BDSPが発売されてから一か月以上経ちますが, 剣盾にて証乱数が発見されたことによって乱数界隈ではダイパリメイクのことが忘れ去られつつあるように感じます. このままPokémon Legendsが発売したら完全に忘れされられてしまいそうな気がしたので, BDSPに関連するお話を一つ書き留めておくことにします. ## BDSPの乱数生成アルゴリズムについてポケモンBDSPでは, GlobalRNGとLocalRNGの2つの乱数生成器が存在しており[^tworng] [^dayrng], 基本的にはGlobalRNGを用いてランダムな事象を決定しています. [^globrng] LocalRNGには, 剣盾でも用いられているXoroshiro128+が使われており, 剣盾にて先駆者がいくつかの調査がなされていることから, 今回の話ではGlobalRNGに用いられているXorshift128について取り上げることにします. Xorshift128について, 数学的な説明をざっくりとしておきます. Xorshift128は, 4つの32bit変数$\boldsymbol{x}_n, \boldsymbol{y}_n, \boldsymbol{z}_n, \boldsymbol{w}_n\in\mathbb{F}_{2}^{32}$からなる, 計128bitの内部状態を持つ乱数生成器です. ある時点での内部状態を並べて, $\boldsymbol{r}_{n}=(\boldsymbol{x}_n^\top,\, \boldsymbol{y}_n^\top,\, \boldsymbol{z}_n^\top,\, \boldsymbol{w}_n^\top)^\top\in\mathbb{F}_{2}^{128}$と表したとき, $\boldsymbol{r}_{n}$を$\boldsymbol{r}_{n+1}$に更新する遷移行列$T$が存在します. (言い換えれば, $T$は $\boldsymbol{r}_{n+1} = T\boldsymbol{r}_{n}$を満たす行列になります.) 具体的な$T$の形は, [Xorshift128の遷移行列とその逆行列を考える#遷移行列の生成](https://hackmd.io/@niart/rkU_MngqK#%E9%81%B7%E7%A7%BB%E8%A1%8C%E5%88%97%E3%81%AE%E7%94%9F%E6%88%90)をご覧いただければと思います. また, 出力は内部状態の下位32bit, 即ち$\boldsymbol{w}_n$となります. [^tworng]:https://twitter.com/SciresM/status/1461396129463947265 [^dayrng]:厳密には日替わりの事象を決定する乱数生成器も存在する(https://bzl.hatenablog.com/entry/2021/12/03/002525)ため3つです [^globrng]:https://twitter.com/SciresM/status/1461396133079441408 ## 手法の吟味乱数調整をする際に用いられる手法は2通り存在します. 1つは乱数生成器に与えられる初期状態(seed)を調整してから目的の内部状態まで遷移させる手法で, もう1つはある時点での内部状態を出力から逆算してから目的の内部状態まで遷移させる手法です. 近年(第六世代以降)では, 初期状態を人為的に操作することが困難なことから, 後者の手法が採られることが多いですね. 今回についても, 後者の手法を採用します. 内部状態の復元手法についてですが, 実のところSM, USUMの孵化乱数(TinyMT)[^smusum]や剣盾の証乱数(Xoroshiro128+)[^swsh]と似たような手法が使えます. 同じ方法が使えるならそれで殴れば良いじゃないかということで具体的に殴っていきましょう. [^smusum]:https://xxsakixx.com/archives/55570518.html [^swsh]:https://hackmd.io/@yatsuna827/ByqFSb6KK ## Xorshiftの内部状態の復元(1) 乱数生成器の内部状態を復元するには, その出力を十分な量だけ観測して, 内部状態を逆算してやる必要があります. ゲーム中にGlobalRNGが使われている場面は数多くありますが, 今回はフィールド上での主人公の瞬きに注目します. 主人公の瞬きを決定するために, 約1秒に1回の間隔で乱数消費が行われます. このときの乱数生成器の出力$w$によって, 瞬きの種類が決定します. これは次のような関数$f(w)$で表すことができます.[^blinkfunc] \begin{align} f(w)= \begin{cases} \text{single} & (w\&\text{0xF} = \text{0x0})\\ \text{double} & (w\&\text{0xF} = \text{0x1})\\ \text{nothing} & (\text{otherwise}) \end{cases} \end{align} ここで, 演算子$\&$はbitごとのAND演算を表すものとし, $\text{single}$は1回瞬き, $\text{double}$は2回瞬き, $\text{nothing}$は瞬きをしないことを表すものとします. つまりこの関数は, 主人公が瞬きをしたときの乱数生成器の出力の下位4bitが観測できることを意味しています. 補足: >「瞬きが発生した場合は、瞬きの種類に従って、乱数値の下位4bitが0000か0001であることが確定する」ということですね。 (夜綱氏によるコメント) しかしながら, 瞬きをしていない時の出力からは殆ど情報を得ることが出来ないため, これまでのような "連続する$n$個の乱数列の下位$k$ビットの出力から逆算する" 手法をそのまま使うのは難しそうです. [^blinkfunc]:https://github.com/zaksabeast/BDSP-RNG-Reference/blob/main/src/timeline.rs ## Xorshiftの内部状態の復元(2) 主人公の瞬き以外に乱数を要する要素が存在しないことを仮定します. 先ほどの話の通り, 瞬きから連続する乱数列の情報を得ることは困難ですが, 主人公が瞬きをしたある時点を基点として, 何消費目に瞬きが生じる出力となったかを観測することは出来ます. 基点から瞬きが起こった時点までの経過秒数がほぼそのまま消費数となることを利用しましょう.[^blinkintvl] 考察に移ります. 瞬きの種類$\text{single}, \text{double}$に対して, それぞれ$0, 1$が割り当てられているものとします. 最初の瞬きを基点として, 発生した$n$回の瞬きに対して, $k$回目の瞬き$b_k\in\{0,1\}$が発生した時の消費数(=経過秒数)を$d_k$(但し, $d_1=0$)とします. このとき, 瞬きから得られる$4n$ bitの情報を並べることでできる瞬きベクトル$\boldsymbol{b}\in\mathbb{F}_{2}^{4n}$を次のように定めます. \begin{align} \boldsymbol{b} = (0\,, 0\,, 0\,, b_1\,, 0\,, 0\,, 0\,, b_2\,, \cdots\,, 0\,, 0\,, 0\,, b_n)^\top \end{align} 基点でのxorshiftの内部状態$\boldsymbol{r}\in\mathbb{F}_{2}^{128}$から$\boldsymbol{b}$を計算する$4n\times128$行列$S$を考えます. (このときの行列は正方行列とは限らないことに注意してください.) そのような行列$S$は, 遷移行列$T$を$d_k$乗したあとの第$i$行目の成分$(T^{d_k})_i$を用いて次のように表すことができます. \begin{align} S\boldsymbol{r} &= \boldsymbol{b}\\ \left( \begin{array}{c} (T^{d_1})_{125} \\ \vdots\\ (T^{d_1})_{128} \\ (T^{d_2})_{125} \\ \vdots\\ (T^{d_2})_{128} \\ \vdots\\ \vdots\\ (T^{d_n})_{128} \\ \end{array} \right) \boldsymbol{r} &= \left( \begin{array}{c} 0 \\ \vdots\\ b_{1} \\ 0 \\ \vdots\\ b_2 \\ \vdots\\ \vdots\\ b_n \\ \end{array} \right) \\ \end{align} あとは, $\mathbb{F}_2$上の計算であることに注意しつつ, $4n$本からなる128元一次連立方程式とみなしてGauss-Jordanの消去法を適用してやることでxorshiftの内部状態$\boldsymbol{r}$を復元することが出来ます. [^blinkintvl]:実際は1秒よりも僅かに長いようです ## 余談行列$S$を正方行列と限定しないのは, 行列$S$が正方行列だとしても必ずしも正則になるとは限らないためです. 実用上は32個より多くの瞬きを観測したうえで行列$S$を生成し, $\text{rank}(S)=128$となるようにするべきでしょう. また, この記事を記述する際に, [**夜綱**](https://twitter.com/sub_827)氏にお力添えをいただきました. この場をお借りして御礼申し上げます.