# BDSPのID調整の原理に関してのメモ

## はじめに
ご無沙汰しております. [**ニアト**](https://twitter.com/21i10r29)です.

ダイパリメイクことブリリアントダイヤモンド・シャイニングパール(以下BDSP)は, 既に忘れ去られたゲームとなりつつありました.

しかし, オーキドのてがみ配布やてんかいのふえの実装, 更には某掲示板の乱数調整スレにBDSPにおけるID調整手法が書き込まれたことにより, 再度日の目を見ようとしています.

せっかくの機会ですから, BDSPにおけるID調整手法の原理を書き残しておくことにします.

**注意:**
**この記事は具体的な乱数調整手順/ツールの使い方/etc..の解説は一切行いません.**

## BDSPの乱数生成アルゴリズムについて(復習)
改めて, BDSPの乱数生成アルゴリズムを確認しておきましょう. とはいえ[**BDSPの乱数調整に関するメモ**](https://hackmd.io/@niart/B1S6AaniF)でも解説はしているので, 必要最低限の部分だけ確認しておきます.

BDSPにおけるランダムな要素(ex. 野生ポケモンの種類, 性格, 個体値, etc...)を決定するのには, [**Xorshift128**](https://ja.wikipedia.org/wiki/Xorshift)が使われており, Unityの標準乱数生成アルゴリズムがそのまま流用されています.

トレーナーカードに表示されるIDについても, ここから取ってきた値に基づいて決定されています.

## 準備(1)
実質的なトレーナーIDの決定タイミング[^iddetermine]は, 主人公の顔写真を選択した時です. (下図参照)

[^iddetermine]:本来のID決定タイミングは名前入力完了時です. しかしながら, 主人公の顔写真を選択した時点で乱数消費が止まり, 主人公の名前入力の完了まで消費が生じないことから, 顔写真選択時が事実上のID決定タイミングと見なすことができます

従って, ゲーム開始時から顔写真選択までの乱数契機から, 乱数生成器の内部状態を復元しなければなりません.

その区間で乱数を消費している観測可能なオブジェクトといえば... ...



ゴンベ「ごんぬ...」

実はゴンベの瞬きタイミングの決定に乱数が用いられており, 乱数消費を起こすオブジェクトは存在しません. つまり, ID決定タイミングまでにゴンベ以外の乱数契機は存在しません.

ゴンベが瞬きしたとき, 乱数生成器の出力$r$を用いて, 次の瞬きまでの待機時間$t$[sec]を決定しているのです.

瞬き間隔を調査したところ, その間隔は概ね3～12秒, 言い換えれば$t$は$[3,12]$に含まれていることが分かりました. また, この待機時間は整数ではなく浮動小数によって決定されています.


主人公の瞬きの場合とは異なり, Xorshiftの出力値に対して剰余をとって計算されているようでもありませんでした. 恐らく, Unityの標準乱数ライブラリの何らかのメソッドを呼び出して計算しているものと思われます.

そんなわけで標準ライブラリの仕様を調べてみると, Andante氏が仕様を詳細にまとめてくださっていました. [^andante]

Andante氏の調査結果に基づくと, `interval`の決定は, `r`を乱数生成器の出力として次のような処理になっていると考えられます.[^interval]

float tmp = (r&0x7fffff) / 8388607.0
float interval = 3*tmp + 12.0*(1.0 - tmp)

この処理を$f(\boldsymbol{r})=t$と表すことにします.

また, 出力された結果`interval`を基に, 元の乱数生成器の出力の下位23bitを逆算することもできます.

具体的には, 観測された瞬き間隔を`interval`, 逆算結果を`r_`として, 次のようになります. (Andante氏による逆算式を用いました)

float norm_f = (12.0-interval)/(12.0-3.0)
float norm_i = (int)(norm_f*8388607.0)
r_ = norm_i & 0x7FFFFF

同様に,この逆算処理を$f^{-1}(t)=\boldsymbol{r}$と表すことにしましょう.[^inv]
[^inv]:厳密には逆関数ではないのですが, 逆算の意味を分かりやすくするためにこのような表記をとりました.

手順としては, `interval`の計算式を`t`について解いて, `8388607.0`を掛けてマスクし直しただけです.

`interval`の計算式に除算が含まれている都合上, 復元して得られる結果には微小な計算誤差が生じますが, 下位数bitにしか影響しないことと, 後述する問題点を踏まえれば些細な問題でしょう.

## 取り組むべき問題
どうやらゴンベの瞬き間隔からXorshiftの出力が得られそうなことは分かりました.
しかしながら, 肝心の瞬き間隔の観測はどのように行えばよいでしょうか?

前回の主人公の瞬きの場合は約1秒ごとに判定があることが分かっていましたし, 観測精度についてもそこまでの厳密性は必要ありませんでした.

しかしながら, 今回の場合はいつ次の瞬きが生じるかが予測できませんし, そもそも瞬き間隔そのものが逆算における重要なファクターとなっています.

なるべく計測誤差を抑えて観測を行いたいのですが, 諸々の観点から誤差を0にすることは困難です.

そこで, 今回は計測誤差についてアレコレするのは諦めて, 逆算手法を工夫することで対処します.

## 準備(2)
乱数生成器の出力を次のような形で表すことにします.
\begin{align}
\boldsymbol{s} = s_{32}s_{31}\dots s_{2}s_{1}
\end{align}

あるタイミングで得られるゴンベの瞬きの間隔(瞬き間隔の秒数)について, その真の値[^truevalue]を$d$とおきます.

真の値$d$から逆算して得られる, 乱数生成器の出力の下位23bitを$\boldsymbol{d}$とすると,
\begin{align}
\boldsymbol{d} &= 00\dots 0 d_{23}d_{22}\dots d_{23-k}\dots d_{2}d_{1}
\end{align}

となります.

乱数生成器の内部状態の復元には$\boldsymbol{d}$を直接使うことは出来ないため, 代わりに計測によって得られる観測値$s$を用いる方法を考えましょう.

但し, 真の値と観測値の誤差が高々$\varepsilon$で抑えられること, 即ち$|d-s|\le\varepsilon$を満たすことを仮定します.

$s$に対して同様にして逆算を行えば, $\boldsymbol{d}$の推定値として$\boldsymbol{\bar{s}}$が計算できます.

\begin{align}
\boldsymbol{\bar{s}} &= 00\dots 0 s_{23}s_{22}\dots s_{23-k}\dots s_{2}s_{1}
\end{align}

さて, 内部状態の復元に下位$23$bitから$23-k$ bitの部分を用いるのであれば,
\begin{equation}
d_{23}d_{22}\dots d_{23-k}=s_{23}s_{22}\dots s_{23-k}
\end{equation}
を満たす必要があるのは明らかです.

しかしながら, 誤差$\varepsilon$を踏まえると, この誤差による繰り上がり/繰り下がりが生じることで当該bitまで伝播してしまう場合があります.

具体的には, 区間$G_i=[f^{-1}(i\times 2^{23-k})-\varepsilon, f^{-1}(i\times 2^{23-k})+\varepsilon]$$(i=0,1,2, \dots 2^k)$に含まれる観測値$s$に関しては, 所与の等式を満たさない可能性があります.

$k=4$, 即ち下位23~20bit($r_{23}r_{22}r_{21}r_{20}$)を用いる場合, 繰り上がり繰り下がりの範囲を数直線上で図示すると以下のようになります.


下位23~20bitの部分が変化する境界値を中心とする前後$\varepsilon$秒が該当区間である, と言うとピンとくるかもしれませんね.

数直線の上部の値は観測値$s$が上記の区間に含まれる場合は復元に失敗する恐れがあるため, そのような観測値を無視する必要が生じます.

## Xorshiftの内部状態の復元
取り合えずここまでの話を纏めると,

* ゴンベの瞬き間隔から乱数生成器の出力を部分的に逆算できる
* 但し, 観測精度を考慮するとXoroshiroの内部状態の復元に利用できない瞬きが存在する

ということが分かりました. これらを踏まえて, Xorshiftの内部状態の復元手法を考察します.

前提条件として, 瞬き間隔の誤差が高々$\varepsilon$で, 乱数生成器の出力の推定値のうち下位$23$ bitから$23-k$ bitの計$k$ bitを用いることを仮定しましょう.

$n$個の連続する瞬き間隔を$D_n=\{d_1, d_2, \dots d_n\}$, それらから逆算することで得られる乱数生成器の出力の推定値を$\bar{S}_n=\{\boldsymbol{\bar{s}}_1, \boldsymbol{\bar{s}}_2,\dots, \boldsymbol{\bar{s}}_n\}=\{f^{-1}(d_1), f^{-1}(d_2), \dots,f^{-1}(d_n)\}$とおきます.

$D_n$から, 無視しなければならない瞬き間隔を取り除いて得られる, $m$個の要素からなる部分列$D'$を求めましょう.

区間$G_i$を次のように定義します.

\begin{align}
G_i&=[f^{-1}(i\times 2^{23-k})-\varepsilon, f^{-1}(i\times 2^{23-k})+\varepsilon] ~~ (i=0,1,2, \dots 2^k-1)
\end{align}

$G_i$から定義される添え字列$\{a_m\}=\{j|\forall i, d_j\notin G_i\}$を用いることで, 部分列$D'$は次のように構成されます.
\begin{align}
D'=\{{d_{a_1}, d_{a_2},\dots, d_{a_m}}\}
\end{align}

$\bar{S}_n$も同様にして部分列$\bar{S}'$を求めることができます. すなわち,
\begin{align}
\bar{S}'=\{\boldsymbol{\bar{s}}_{a_1}, \boldsymbol{\bar{s}}_{a_2},\dots, \boldsymbol{\bar{s}}_{a_m}\}=\{f^{-1}(d_{a_1}), f^{-1}(d_{a_2}), \dots,f^{-1}(d_{a_m})\}
\end{align}

です.

回りくどい書き方となりましたが, 要するに$\bar{S}'$の意味するところは"復号に利用できない値を取り除いて得られる乱数生成器の出力(の推定値)"となります.

$\bar{S}'$を求めることが出来れば, あとは以前の記事の手法([Xorshiftの内部状態の復元(2)](https://hackmd.io/@niart/B1S6AaniF#Xorshift%E3%81%AE%E5%86%85%E9%83%A8%E7%8A%B6%E6%85%8B%E3%81%AE%E5%BE%A9%E5%85%832))と同様です.

$\bar{S}'$の各値を二進数表記に直して, 下位$23$ bitから$23-k$ bitまでを一列に並べることで得られる, $km$次元上のベクトル$\boldsymbol{b}\in \mathbb{F}_{2}^{km}$を定めて,
\begin{align}
\boldsymbol{b}=((\bar{s}_{a_1})_{23},(\bar{s}_{a_1})_{22}, \dots (\bar{s}_{a_1})_{23-k}, (\bar{s}_{a_2})_{23}, \dots \dots , (\bar{s}_{a_m})_{23-k})
\end{align}

Xorshiftの遷移行列$T$を用いて, 内部状態$\boldsymbol{r}\in \mathbb{F}_2^{128}$から$\boldsymbol{b}$を計算する$km \times 128$行列$U$を次のように構成し,
\begin{align}
U\boldsymbol{r} &= \boldsymbol{b}\\
\left(
\begin{array}{c}
(T^{a_1})_{128-23} \\
\vdots\\
(T^{a_1})_{128-(23-k)} \\
(T^{a_2})_{128-23} \\
\vdots\\
(T^{a_2})_{128-(23-k)} \\
\vdots\\
\vdots\\
(T^{a_m})_{128-(23-k)} \\
\end{array}
\right) \boldsymbol{r} &=
\left(
\begin{array}{c}
(\bar{s}_{a_1})_{23} \\
\vdots\\
(\bar{s}_{a_1})_{23-k} \\
(\bar{s}_{a_2})_{23}\\
\vdots\\
(\bar{s}_{a_2})_{23-k}\\
\vdots\\
\vdots\\
(\bar{s}_{a_m})_{23-k} \\
\end{array}
\right) \\
\end{align}

(遷移行列$T$を$a_i$乗したあとの第$j$行成分を$(T^{a_i})_j$と表しています. )

得られた$km$本からなる$\mathbb{F}_2$上の連立方程式を解くことでXorshiftの内部状態$\boldsymbol{r}$が復元できますね.

## 実装について
ゴンベの瞬きを用いたXorshiftの内部状態の復元の実装は, この手法に基づいたものとなっています.

各種パラメータについては, $k=4$(一つの瞬き間隔から得るbit数), $\varepsilon=0.1$(計測誤差), $n=64$(瞬きの観測数), $m=36$(実際に復元に用いる瞬きの数)としています.

##### 余談

残念ながらこれらのパラメータについては議論の余地があります. $k, \varepsilon$ の値は環境によって大きく異なるでしょうし, 少なくとも$m$の値は決め打ちにするのは望ましく無さそうです[^indexerr].

[^indexerr]:実は復元に用いるための瞬きが十分な数得られなかったことが`index error`が送出される原因にもなっています. 観測数を増やすことで解決できるかもしれません.

[^andante]:Andante.　“UnityEngine.Random の実装と性質”. 屋根裏工房改. 2020/12/01.
https://andantesoft.hatenablog.com/entry/2020/12/01/225931, (2022/03/14閲覧)

[^interval]:出力の結果と, 文献に記載されているRandomクラスの実装を鑑みるに, 恐らく`Random.Range`メソッドが呼ばれていると思われます.

[^truevalue]:乱数生成器の出力に基づいて計算される値のこと