【ポケモンBW乱数】初期seed検索を高速化しました【5世代乱数】

概要

　表題の通りです。(おい)
　5世代の乱数調整は初期seedの計算に不可逆な関数(sha-1)が使われているので、地道に全日付を総当たりするしかありません。また、初期seedを計算する際のパラメータにDS本体固有の値(macアドレス。厳密にはwifiモジュール依存なのでwifiモジュールを付け替えれば変更可能)が含まれるので、4世代のように起動時刻を共有するといったこともできません。
　各種条件を指定して初期seedと起動時刻を検索するツールは、さびたコイルさんのSSS4が有名で、ネットに転がっている解説記事などもほとんどがSSS4の使用を前提にしています。例えば6Vメタモンを捕まえる場合、おおまかな手順としては
0. パラメータを求める(実はほとんど固定なので不要です).
1. SSS4を回して6V個体が出現する起動時刻を求める.
2. 性格値乱数列のオフセットを求める(実は初期seedから計算できます).
3. リストからメタモンが出現する消費数を探し, ペラップをしばいてから甘い香りを使ってエンカウントする.
4. 6VメタモンGET! すごい!
といった感じだと思います(「オフセット」等の用語はここでは解説しません)。

　ここで一番時間がかかるのは1. です。だいたい半日～丸一日PC計算させて放置しておく必要があります。ここを解消できれば5世代乱数はさらに快適かつ簡単になりますね(「10年前のゲームで今でも乱数調整するような人は新規に検索をかけることはほとんどない」？ ﾊｲｿｳﾃﾞｽﾈ…)

本題

　SSS4は十分高速に動作するアプリケーションですが、実はまだ検索化の高速化の余地を残しています。1つは並列計算。もう1つはこの記事にある手法です。前者はSSS4を複数立ち上げて同時に計算させて疑似的に実現させることもできますが、飽くまで『疑似的に』です。後者について簡単に説明すると、
・個体値の生成に使われるMTの初期seedは32bit。
・MTの初期化処理は結構重ため。
・検索するときに指定される個体値はそんなに種類多くない(6Vとか5VA0とかめざ氷理想とか)。
・個体値と初期seedのペアを事前に総当たりで計算しておけば、初期化処理を通す必要が無くなる(実際に個体値を生成して確認する必要は無く、初期seedの一致だけを見ればいい)。
ということです。さらにこの「個体値から初期seedを総当たりする処理」についても、乱数を取得する位置と回数が固定であるため、MTの更新処理を必要最低限に抑える実装が可能になります(一般的な実装では初期化時点で乱数取得624回分の計算を終えてしまう)。

実装と実行

　以上の方針でツールを作り、計算してみました。

BWで6V個体が出る初期seedが約20分で計算できてしまいました。先の記事に載っていたものともちゃんと一致しています。

　そして起動時刻の総当たりを並列で計算するツールも作りました。

(165個もseed候補があるのは5VA0個体や各種めざパ理想個体の初期seedも計算してつっこんだからです)
こちらも約20分で計算が終わりました。合計しても40分ほどです。

で、そのツールはどこにあるの？

こちらです。例のごとくwindowsでしか動作しないと思います。
使い方は大雑把に書いてあるので、わからないところがあればTwitter(@sub_827 )に直接リプ飛ばしてください。