ご無沙汰しております. ニアトです.
ダイパリメイクことブリリアントダイヤモンド・シャイニングパール(以下BDSP)は, 既に忘れ去られたゲームとなりつつありました.
しかし, オーキドのてがみ配布やてんかいのふえの実装, 更には某掲示板の乱数調整スレにBDSPにおけるID調整手法が書き込まれたことにより, 再度日の目を見ようとしています.
せっかくの機会ですから, BDSPにおけるID調整手法の原理を書き残しておくことにします.
注意:
この記事は具体的な乱数調整手順/ツールの使い方/etc..の解説は一切行いません.
改めて, BDSPの乱数生成アルゴリズムを確認しておきましょう. とはいえBDSPの乱数調整に関するメモでも解説はしているので, 必要最低限の部分だけ確認しておきます.
BDSPにおけるランダムな要素(ex. 野生ポケモンの種類, 性格, 個体値, etc…)を決定するのには, Xorshift128が使われており, Unityの標準乱数生成アルゴリズムがそのまま流用されています.
トレーナーカードに表示されるIDについても, ここから取ってきた値に基づいて決定されています.
実質的なトレーナーIDの決定タイミング[1]は, 主人公の顔写真を選択した時です. (下図参照)
従って, ゲーム開始時から顔写真選択までの乱数契機から, 乱数生成器の内部状態を復元しなければなりません.
その区間で乱数を消費している観測可能なオブジェクトといえば… …
ゴンベ「ごんぬ…」
実はゴンベの瞬きタイミングの決定に乱数が用いられており, 乱数消費を起こすオブジェクトは存在しません. つまり, ID決定タイミングまでにゴンベ以外の乱数契機は存在しません.
ゴンベが瞬きしたとき, 乱数生成器の出力を用いて, 次の瞬きまでの待機時間[sec]を決定しているのです.
瞬き間隔を調査したところ, その間隔は概ね3~12秒, 言い換えればはに含まれていることが分かりました. また, この待機時間は整数ではなく浮動小数によって決定されています.
主人公の瞬きの場合とは異なり, Xorshiftの出力値に対して剰余をとって計算されているようでもありませんでした. 恐らく, Unityの標準乱数ライブラリの何らかのメソッドを呼び出して計算しているものと思われます.
そんなわけで標準ライブラリの仕様を調べてみると, Andante氏が仕様を詳細にまとめてくださっていました. [2]
Andante氏の調査結果に基づくと, interval
の決定は, r
を乱数生成器の出力として次のような処理になっていると考えられます.[3]
この処理をと表すことにします.
また, 出力された結果interval
を基に, 元の乱数生成器の出力の下位23bitを逆算することもできます.
具体的には, 観測された瞬き間隔をinterval
, 逆算結果をr_
として, 次のようになります. (Andante氏による逆算式を用いました)
同様に,この逆算処理をと表すことにしましょう.[4]
手順としては, interval
の計算式をt
について解いて, 8388607.0
を掛けてマスクし直しただけです.
interval
の計算式に除算が含まれている都合上, 復元して得られる結果には微小な計算誤差が生じますが, 下位数bitにしか影響しないことと, 後述する問題点を踏まえれば些細な問題でしょう.
どうやらゴンベの瞬き間隔からXorshiftの出力が得られそうなことは分かりました.
しかしながら, 肝心の瞬き間隔の観測はどのように行えばよいでしょうか?
前回の主人公の瞬きの場合は約1秒ごとに判定があることが分かっていましたし, 観測精度についてもそこまでの厳密性は必要ありませんでした.
しかしながら, 今回の場合はいつ次の瞬きが生じるかが予測できませんし, そもそも瞬き間隔そのものが逆算における重要なファクターとなっています.
なるべく計測誤差を抑えて観測を行いたいのですが, 諸々の観点から誤差を0にすることは困難です.
そこで, 今回は計測誤差についてアレコレするのは諦めて, 逆算手法を工夫することで対処します.
乱数生成器の出力を次のような形で表すことにします.
あるタイミングで得られるゴンベの瞬きの間隔(瞬き間隔の秒数)について, その真の値[5]をとおきます.
真の値から逆算して得られる, 乱数生成器の出力の下位23bitをとすると,
となります.
乱数生成器の内部状態の復元にはを直接使うことは出来ないため, 代わりに計測によって得られる観測値を用いる方法を考えましょう.
但し, 真の値と観測値の誤差が高々で抑えられること, 即ちを満たすことを仮定します.
に対して同様にして逆算を行えば, の推定値としてが計算できます.
さて, 内部状態の復元に下位bitから bitの部分を用いるのであれば,
を満たす必要があるのは明らかです.
しかしながら, 誤差を踏まえると, この誤差による繰り上がり/繰り下がりが生じることで当該bitまで伝播してしまう場合があります.
具体的には, 区間に含まれる観測値に関しては, 所与の等式を満たさない可能性があります.
, 即ち下位23~20bit()を用いる場合, 繰り上がり繰り下がりの範囲を数直線上で図示すると以下のようになります.
下位23~20bitの部分が変化する境界値を中心とする前後秒が該当区間である, と言うとピンとくるかもしれませんね.
数直線の上部の値は観測値が上記の区間に含まれる場合は復元に失敗する恐れがあるため, そのような観測値を無視する必要が生じます.
取り合えずここまでの話を纏めると,
ということが分かりました. これらを踏まえて, Xorshiftの内部状態の復元手法を考察します.
前提条件として, 瞬き間隔の誤差が高々で, 乱数生成器の出力の推定値のうち下位 bitから bitの計 bitを用いることを仮定しましょう.
個の連続する瞬き間隔を, それらから逆算することで得られる乱数生成器の出力の推定値をとおきます.
から, 無視しなければならない瞬き間隔を取り除いて得られる, 個の要素からなる部分列を求めましょう.
区間を次のように定義します.
から定義される添え字列を用いることで, 部分列は次のように構成されます.
も同様にして部分列を求めることができます. すなわち,
です.
回りくどい書き方となりましたが, 要するにの意味するところは"復号に利用できない値を取り除いて得られる乱数生成器の出力(の推定値)"となります.
を求めることが出来れば, あとは以前の記事の手法(Xorshiftの内部状態の復元(2))と同様です.
の各値を二進数表記に直して, 下位 bitから bitまでを一列に並べることで得られる, 次元上のベクトルを定めて,
Xorshiftの遷移行列を用いて, 内部状態からを計算する行列を次のように構成し,
(遷移行列を乗したあとの第行成分をと表しています. )
得られた本からなる上の連立方程式を解くことでXorshiftの内部状態が復元できますね.
ゴンベの瞬きを用いたXorshiftの内部状態の復元の実装は, この手法に基づいたものとなっています.
各種パラメータについては, (一つの瞬き間隔から得るbit数), (計測誤差), (瞬きの観測数), (実際に復元に用いる瞬きの数)としています.
残念ながらこれらのパラメータについては議論の余地があります. の値は環境によって大きく異なるでしょうし, 少なくともの値は決め打ちにするのは望ましく無さそうです[6].
本来のID決定タイミングは名前入力完了時です. しかしながら, 主人公の顔写真を選択した時点で乱数消費が止まり, 主人公の名前入力の完了まで消費が生じないことから, 顔写真選択時が事実上のID決定タイミングと見なすことができます ↩︎
Andante. “UnityEngine.Random の実装と性質”. 屋根裏工房改. 2020/12/01.
https://andantesoft.hatenablog.com/entry/2020/12/01/225931, (2022/03/14閲覧) ↩︎
出力の結果と, 文献に記載されているRandomクラスの実装を鑑みるに, 恐らくRandom.Range
メソッドが呼ばれていると思われます. ↩︎
厳密には逆関数ではないのですが, 逆算の意味を分かりやすくするためにこのような表記をとりました. ↩︎
乱数生成器の出力に基づいて計算される値のこと ↩︎
実は復元に用いるための瞬きが十分な数得られなかったことがindex error
が送出される原因にもなっています. 観測数を増やすことで解決できるかもしれません. ↩︎