【ポケモンコロシアム】瞬きを用いた現在seed特定処理の実装と高速化【乱数調整】

この記事はPokémon RNG Advent Calendar 2020 23日目の記事です。

adventar.org

f:id:yatsuna_827:20201223023605p:plain

ムウマは目が大きくて瞬きが見やすいことで非常に有名。

初めに

今年はポケモンコロシアム(2003年発売)の乱数調整にいくつもの大きな進展がありました。2月下旬にかけら(sina_poke)氏によってステータス画面におけるポケモンの瞬きを観測して現在seedを特定する手法が開拓され、スイクンを含む一部ポケモンの乱数調整の難易度が大きく緩和されたのをきっかけに、3月末にはライコウの乱数調整が可能になり(頑張りました)、現在ではフェナス/パイラ市中での戦闘になるポケモンを除いたほとんどのポケモンの乱数調整が現実的な難易度になっています。

sina-poke.hatenablog.com

 今回はそんなブレイクスルーのきっかけとなった瞬きによるseed特定アルゴリズムの実装についての考察をまとめました。

瞬き処理の概要

瞬き発生の具体的な処理はかけらさんが公開されています。

sina-poke.hatenablog.com

ものすごく要約すると

  • 前回の瞬きからの経過時間に依存して閾値が決定する(単調増加)
  • 瞬きが終わって4Fの間は瞬き判定が無い
  • 30F以降は閾値1/60.0で頭打ちになる
  • 90F目には閾値が1.0になり、必ず瞬きが発生する

ということです*1。この瞬きの間隔を十分多く観測すれば*2、現在seedを求めることができるというわけです。

動機

さて、この瞬きの観測ですが、人間がやるのはちょっと辛いです。主に目に優しくない。そこでPC上に映したGCの画面からテンプレートマッチングで瞬きを判定し、自動で瞬き間隔を収集するプログラム*3を書いたのですが、そこからseedの検索まで行ってくれた方が何かと嬉しいです。残念ながらかけらさんはCoToolに実装されている検索アルゴリズムまでは公開されていないので、自前でアルゴリズムを考察・実装する必要がありました。

考察

⓪要件

目視にしろプログラムによる自動観測にしろ、どうしても観測には誤差が生じます。そこで、ある程度の誤差を許した検索ができる必要があります。また、ポケモンコロシアムの主要な乱数消費手段はゲームロード後のダークポケモンのステータス画面を開いて放置することである都合上、検索範囲は数百万 ~ 数千万に及びます。*4

① ナイーブな実装

とりあえず考えられるのは『各seedから瞬きをシミュレートし、すべて入力から誤差以内になっているものを探す』です。

gist.github.com

②『次に瞬きするまで』をあらかじめ計算しておく

①の実装の『瞬きするまで乱数を進める処理』は無駄があるように思えます。たとえばi_0フレーム目からシミュレートを始めて、1回目の瞬きがi_1フレーム目、2回目の瞬きがi_2フレーム目だったという結果が得られたとしたら、次にi_1フレーム目からシミュレートを始めるときは先ほどの結果から、1回目の瞬きがi_2フレーム目に起こることはわかっています。しかしこの実装では同じ計算を再度行っているのです。

この発想をもう少し進めてみます。瞬きをシミュレートせずとも乱数値からただちに計算できることとして、『内部カウンタがいくつ以上なら瞬きが発生するか』があります。これを用いて『そのフレームで瞬きしたときに次に瞬きするのは何フレーム後か』を計算しておけば、シミュレート部分がかなり楽になります(これをa[n]で置いておきます)。

ここで『そのフレームで瞬きしたときに次に瞬きするのは何フレーム後か』を計算する部分ですが、『各iに対して、a[i+k]≦kを満たすような最小のkを、0から数え上げて探す方法』と、『各iに対して、i-85からi-a[i]で瞬きが発生していたらその次に瞬きが起こるのは少なくともiフレームの地点であることを利用する方法』があります。*5

上記の2つの方法ですが、今回は後者の方が効率的に計算することができます。それは瞬き判定の閾値が1/60で頭打ちになってしまうことに依ります。すなわち、与えられる疑似乱数は59/60の確率で『前回瞬きしてから90F経過していないと瞬きが発生しない乱数』なのです。つまり、前者の処理を行えば59/60の確率でループを86回回す羽目になりますが、後者の処理では59/60の確率でループが1回で済みます。

以上の発想で実装したのが以下のコードです。

gist.github.com

③配列上の探索処理の効率化

これはかなりのガバなのですが、FindIndexは線形探索をしているので死ぬほど遅いです。しかも上記の通り、ほとんどのseedは最後尾まで探索しないと条件を満たさないので、処理効率的には最悪です。素直に二分探索しましょう。*6 処理回数が数百万回 ~ 数千万回に及ぶので、かなりの時間短縮が期待できます。*7

gist.github.com

④配列上の探索処理をもっと効率化

乱数の取り得る値は65536通りしかないので、各0から65535の値に対してあらかじめUpperBoundしておいた結果を配列にキャッシュしておくことで、『そのフレームで瞬きしたときに次に瞬きするのは何フレーム後か』は配列へのアクセスだけで(つまり計算量O(1)で)取得できるようになります。

現在私がGithubで公開している、ポケモンコロシアムの乱数調整汎用ライブラリPokemonCoRNGLibraryに実装してあるのはこれになります。

github.com

実行時間の計測

実際に計測してみないことにはどれが優れているのか、どの程度優れているのかを比較して語ることはできません。以下のコードで計測してみました。*8

なおExectionTimer.MeasureはActionを渡して10回実行した平均時間を返す自前のメソッドです。

f:id:yatsuna_827:20201223021242p:plain

 結果がこちら。

f:id:yatsuna_827:20201223021924p:plain

ナイーブな実装の2.5倍くらい速くなりました。やったー。そしてやっぱり②遅いですね……。上の画像は検索範囲を600万で取っていますが、1億くらい取っても④の実装なら5~6秒で計算が終わります。*9

f:id:yatsuna_827:20201223022731p:plain

最後に

もっと良い実装があればライブラリにプルリク送ってください。待ってます。

あと良ければライブラリ使ってくださると嬉しいです。ほとんどの処理をイテレータで処理できるようにしてあるので、乱数ツールの肝になるリストの列挙等をほとんど脳死でコーディングできるようになっていると思います。

*1:厳密にはステータス画面に入った直後のみ、FPS変更のタイミングのせいか、2→5→7→…とカウンタが途中から奇数で動くのですが、誤差を考慮するならこれが大きく影響することはほとんどないでしょう

*2:これは厳密に証明したわけではなく経験則ですが、10~15回分ほどの瞬き間隔のデータが得られれば誤差±20でもほとんど一意的に現在seedが求まります

*3:COReaderという名前で公開しています。ただし2020/12/23現在公開しているバージョンの検索アルゴリズムは、ちゃんとテストしていなかったので、ナイーブな実装よりも遅いです

*4:あらかじめ消費速度をしっかり計測しておくことで、もっと細かく絞り込むこともできなくはないのですが、ざっくりした範囲指定で特定できるに越したことはありません。瞬きによるseed検索は検索範囲が広くても必要な入力数はほとんど変動しないのでなおさらです。

*5:いわゆる『貰うDP』と『配るDP』に似てるな~と思った。

*6:しかしC#LinqにはBinarySearchしかなく、UpperBoundが無い(悲しい)。ここは自力で実装しました。

*7:あるいはかなりの無駄を生むカスコードを書いてしまったとも言えます

*8:コードブロックではなく画像なのは見たまま編集でここまで書いてしまったからです

*9:ただし要素数10^8の配列を作るのでメモリ使用量がえらいことになります。幸い範囲を適当に分割してやっても"被り"は入力の要素数*85程度しか発生しないので、適当に内部で分割してやってもいいかもしれません。要検討。