# 乱数調整における検索処理の高速化戦略

## あいさつ

この記事は[Pokémon Past Generation Advent Calendar 2023](https://adventar.org/calendars/8746) 1日目の記事です。

内容はタイトルの通りです。いきなりオタク向け記事ですまんな。

## 基本
LCGとMTに関する知見は[さき先生の記事](https://xxsakixx.com/archives/54754255.html)にまとまっています。読んでおきましょう。

### 複数消費を高速に行う（ジャンプ）
LCGは[oupo先生の記事](https://oupo.hatenadiary.com/entry/20100112/1263306151)を参照してください。

MTはたぶん無理です。素直に線形に進めましょう。

XorShift系は [この前考察した](https://hackmd.io/b9MlPsCDTlW4DGMvkW_pTA?view)ので、そちらを参照してください。[C#での実装](https://github.com/yatsuna827/PokemonPRNG/blob/master/PokemonPRNG.XorShift128/XorShift128.cs#L223)もあります。

基本的にはどのような場合でも使えるなら使った方がいいです。コードの可読性も上がります。

### 2つのseed間の距離を求める
これはLCGのみ可能です。詳細は[oupo先生の記事](https://oupo.hatenadiary.com/entry/20121122/1353554591)に譲ります。
ちゃんと考察したわけではないのですが、おそらくLCGの群としての性質に由来するアルゴリズムです。位数が2冪になっていないMTやXorShiftの系統で同様の実装ができたとしても、あまり現実的な性能にはならないと思います…。

必要な消費数を求めるときに使うほかにも、生成処理を通したあとの消費数が欲しい場合に内部でカウンタを持っておいて返すようなことをする必要がなくなり、実装がスッキリします。

### メモ化
最も初歩的なテクニック…ですが、メモ化もノーコストではない（配列へのアクセスコスト）ため、特にLCGでは普通に計算するのと差が無いことも多く、あんまり出番はない印象です。メモ化することで実装の複雑さが上がってしまうデメリットもあります。

一方でMT/SFMTでは『1回の生成に複数個の乱数を使う処理を1消費ずつずらして計算する』ような場面（たとえば個体生成のリスト表示）では、さすがに内部状態を毎回コピーしていては大変なことになるので、乱数のメモ化が大きく効きます。

[乱数のキャッシュを組み込んだMT/SFMTの実装](https://github.com/yatsuna827/PokemonPRNG/blob/master/PokemonPRNG.SFMT/CachedSFMT.cs)も公開しています。

## 応用

### 条件を絞る
seed特定などで「愚直に全探索すると組み合わせが爆発するけど、プレイヤーに追加の操作を求めることで条件を緩和して簡単に解ける問題に落とし込める」というパターンです。たとえばCoの瞬きは素直に探索すると始点を1消費ずつ変えながら瞬きの系列を計算する必要がありますが、瞬き画面で一定時間放置してから計測してもらうことで、適当なseedから計算した系列の部分列を調べるだけでよくなります。Co瞬きに限らず『seedに応じて消費数が決まる』処理では、1ステップ後のseedが同じになるようなseedが複数あるため、次第に系列が合流していき、場合によってはただ1通りの系列に収束します。収束までの速度は処理によって異なりますが、大抵はこのテクニックが使えます（ただしプレイヤーの手間と所要時間は増えるため、バランスを考える必要はあります）。

### 並列化
コアの分だけ速くなる魔法です。

ただし、まず並列化できるような実装に落とし込む必要があります。クラスの内部状態を書き換えているような実装とは相性が悪く、たとえば7世代の個体検索の検索範囲を広く取るような場合には使えません。

並列計算は他にも意識すべき実装上の問題が増えるため、計算時間が膨れ上がることがわかっている場合だけ使うようにしましょう。32bit LCGを1周する程度なら不要です。

小手先のテクニックとしては、(言語にもよりますが、少なくともC#では)スレッドを立てるオーバーヘッドが案外バカにならないので、スレッドごとの処理量が均等になるよう、なおかつコア数きっちり使い切るようにタスクを分割するのが良いです。

### SIMD
うきさんが[6世代基準seed検索を高速化させた](https://github.com/ukikagi/poke6-seed-finder/blob/master/src/multi_mt.rs)コードを読んで知ったテクです。

SIMD自体はSFMTのテーブル更新に組み込まれていますが、実はSFMT以外でも使えます。テーブル更新ではなく、『複数の初期seedから計算される系列』を並列化して持っておくことで、1回の演算で一気に8個分ないし16個分の初期seedを計算することができます。また、スレッド並列化との併用もできる。

ビット演算とは相性が良い一方で、算術演算にはあまり有効ではないようで、手元の環境ではLCGをSIMDで書き直しても速度はほとんど変わりませんでした。

## 実例

[以前作ったBWの計算ツール](https://note.com/sub_827/n/naf3514955225)を[高速化させました](https://github.com/yatsuna827/5genInitialSeedSearch)。

手元の環境でも2分程度、めちゃくちゃ強いマシンを持っている方に試してもらったら数秒で計算が終わりました。まだこれでも5genSearchには届いておらず、C言語の壁を感じるわけですが…。C#だけでunsafeを使わずに可読性を保ったまま高速化できるということを加味すれば、なかなか悪くない結果だと思います。

## 最後に
明日の記事は、すのーさんの GBA育成すべきポケモン20選 です。徐々にオフ会の開催も増えてきたのでこれからGBA対戦を始めようと思っているそこのあなたは必見ですね。ほなまた。