オオモノ湧きアルゴリズムを解析した

サーモンラン完全解析

サーモンランWAVE決定アルゴリズムについて

WAVE決定アルゴリズムイベント・潮位・キンシャケ探しイベントにおけるアタリ位置についてはゲーム開始時の初期シードから求めるアルゴリズムの解析をcontainer12345氏が達成しました。また、その成果を元にぼくがキンシ...

tkgstrator.work

2020.09.10

バイト開始時の初期シードから計算できる全てのパラメータを求めるアルゴリズムを解析しようという試みです。

現在のところ、以下の要素が初期シードから計算可能であることがわかっており、いくつかのものについては@container12345氏により完全解析されています。

パラメータ	進捗	クラス
潮位	完全解析済	Game::Coop::Setting
イベント	完全解析済	Game::Coop::Setting
キンシャケ探しアタリ位置	完全解析済	Game::Coop::EventGeyser
キンシャケ探しゴール位置	ほぼ解析済*	Game::Coop::EventGeyser
ランダム支給ブキ	未解析	未調査
支給スペシャル	未解析	未調査
オオモノ湧き順	未解析	Game::Coop::EnemyDirector
シャケ湧き方向変化	未解析	Game::Coop::EnemyDirector
ラッシュイベントのターゲット	未解析	Game::Coop::EnemyDirector
霧イベントの金イクラ	未解析	未調査

キンシャケ探しゴール位置は難破船ドンブラコと通常潮と満潮での特定の一箇所のゴール位置のみが計算できていません。これは3.2.0からキンシャケ探しイベントにおいてドンブラコのみ別の計算式が使われるようになったためです。

逆に言うとこれ以外のものは初期シードから簡単に決まらない可能性が高いです。ハコビヤイベントのシャケコプターの飛来位置やグリルイベントのターゲットも初期シードから決まっているはずなのですが、リトライしても同じ状態が再現されないためです。

前回までの進捗

さて、前回はGame::Coop::EnemyDirectorクラスが二つの乱数生成器をもち、一方はザコシャケの計算に使い、もう一方はオオモノ出現と湧き方向変化に使われていそうだという話をしました。

オオモノの湧きを完全解析するのであれば、乱数消費が「オオモノの湧き」によるものなのか「湧き方向の変化」によるものなのかを区別しなければなりません。

しかし、湧き方向変化はキケン度MAXとたつじん80%では8、それ以外では6という風になっているため、一律に定義することができません。なので今回は湧き方向変化を8回と決め打ちしてプログラムを組むことにしました。

WAVEの潮位とイベントの検索アルゴリズムも、実はたつじんとそれ以下では異なっています。でもアルゴリズムはたつじん以上にしか対応していません。それと同じように、本アルゴリズムもあくまでもキケン度MAXの湧きを計算するものにします。

逆アセンブラの擬似コードを解析する

最初に逆アセンブラから得られた生コードがこれでした。神プログラマはこれでもいけるのかもしれませんが、ぼくにとってはこれだけではほとんど意味不明でした。

各変数の構造体を推定し、これを手作業で正しいC++コードに修正する必要があります。

ここで気になるのはv12で、getArray()の返り値を使っていることから配列であることが予想されます。これは*(v12+1)と*v12と*(v12+1) + 4LL * v78という記述からも裏付けられます。

これはC++におけるポインタの挙動を示しており、v12は次のような構造をもっているのではないかと推察されるのです。

struct array {
  uint32_t mLength;
  uint32_t *ptr;
}

つまり、*v12が配列の長さを*(v12+1)がv12[0]を表しているというわけです。また、4LL * v78という記述から配列は4バイトずつズレています。4バイトズレるということは32ビットなのですから、配列はint型であることがわかるというわけです。

そして、このような構造体は実はキンシャケ探しイベントのアタリ位置を求める際に使われていました。それがまさにsead::PtrArrayImplクラスで、これはスプラトゥーンにおける標準的な配列クラスです。

配列ということはわかったのですが、ここでそれは一度置いておいて、それ以外のコードを見やすくするところからはじめました。

ちなみにwhileの終了条件が間違っているのですが、スルーでお願いします。

最後のif文は要らなさそうだったので削除し、また途中のv75 >= 0x17はIPSwitchで該当する命令を無効化しても湧き順に全く変化が起きなかったため（おそらくオオモノ数が上限に達した場合にのみ使われる）、同様に削除しました。

ここまでくると割とスッキリしてなんだかわかりそうな気がしてきます。

実機での検証

次に先程推定したsead::PtrArrayImplのコードを入れ、見やすくしたものが上になります。

ここで問題となるのはWhile文の終了条件で、これはmEnemyArray.mLengthの長さに依存していることがわかります。この値は果たして定数なのか、それとも変数なのかという問題です。

また、同様にmRareTypeも同じことが言えます。わざわざ二度呼び出しているということは呼び出すたびに値が変わるような関数なのでしょうか？

mTmpIdの値を固定する

さて、ここで気になるのは一度仮のオオモノIDとしてmTmpIdを計算し、それがある条件を満たしたときのみmRareIdに代入して最終的なオオモノIDとして使われているということです。

そこでIPSwitchを使い、このmTmpIdを常にmRareType[0]を返すようにしました。こうすることでEnemyRareTypeの配列の0番目に何が入っているのかがわかるというわけです。

// Always load mRateType 0 [tkgling]
@disabled
00546718 48818A9A

すると、全てのオオモノがバクダン化しました。よって、配列の先頭はバクダンを示す値が入っていることがわかりました。

そしてぼくは先頭の要素がバクダンになるような配列を既に知っていました。よくイカリングを見ている方ならわかると思うのですが、イカリングにおけるオオモノシャケの並び順なのです。

もしもイカリングにおける配列と、プログラムにおける配列が同じであれば、mRareType = {"Steelhead", "Flyfish", "Scrapper", "Steel Eel", "Tower", "Maws", "Drizzler"}となり、二番目のオオモノはカタパッドになるはずです。

それを検証するため、次はWhileの継続条件であるmLengthを弄ることにしました。これは結局配列を先頭から見ていき、「バクダン出現の条件を満たすか」「カタパッド出現の条件を満たすか」という風にオオモノ出現チェックを行うアルゴリズムです。

つまり、このチェックは配列の長さである七回実行され、七回あるために全てのオオモノの出現チェックがされるわけです。よって、ここのチェック回数を二回にしてしまえば「バクダンかカタパッド」の出現チェックしか行われないことになり、出現するオオモノがバクダンとカタパッドだけになるはずです。

// Change mLength to 2 [tkgling]
@disabled
005466E4 56008052

そして、このパッチを当てたところ予想通り出現するオオモノがバクダンとカタパッドだけになりました！断定するには早いですが、オオモノの配列はイカリングのものと同じと考えて良さそうです。

復元したC++コード

そしてwhile文をfor文に変換しておしまいです。

実はここにいたるまでに乱数生成器の初期化に定数をいれてどんなオオモノが出力されるか検証していました。その結果が画像の上の方のやつで0と1ならテッパン、2ならタワーという感じです。

問題はこれが正しいかどうかをチェックすることです。要は、コードが合っていたとしても考えがどこかで間違っていたら正しいコードを書いても意味がないからです。オオモノ湧きアルゴリズムが正しいかどうか試すためには、このアルゴリズムに対して適当な初期シードを与え（先程調べた0や1が望ましい）、実機と同じ予測ができるかを確かめる必要があります。

いちいちコンパイルするのがめんどくさかったので、これをJavascriptに移植し、動作テストをしてみることにしました。

Javascriptはポインタ・構造体・32ビット以上のビットシフトが使えないことを除けば基本的にはC++と互換性があるのでほとんど同じようにコードを書くことができました。

そして、このコードを実行させたところmInitialSeedを与えることで正しく実機と同じオオモノ予測をすることができました！

湧き方向とオオモノ出現

ここまでできれば根幹となる計算アルゴリズムは正しいので、次は各WAVEの乱数消費回数の文だけループさせてやればいいことになります。

WAVE1ですとオオモノの湧きは20回で、湧き方向変化が8回（変化が8回ということは9回消費されている）なので20+8+1回乱数が消費されることになります。

Starlightで乱数生成器の中身を覗くとゲーム開始時に一度乱数が消費されている事がわかっていたため、次のような感じで乱数が消費されていき、初期化も合わせて30回呼び出されているのではないかと予想できます。

回数	意味
1	初期化？
2	一回目湧き方向計算
3	一匹目オオモノ出現

Starlightで湧き方向変更回数を調べる

そこでStarlightを使い、乱数生成器の内部状態が変わった回数をカウントするコードを書きました。

すると29回乱数が消費されなければいけないにも関わらず何故か25回しかカウントされませんでした。これは何故でしょうか？

乱数消費はクロックレベルのオーダー

これは当然のことで、Starlightは「常に」乱数生成器の内部状態を見れているわけではありません。チェックする間隔というものが当然存在します。そして、その頻度に比べて乱数消費の間隔があまりにも速すぎるのです。

つまり、本当は二回消費されているにも関わらず、あっという間に二回消費されてしまうためにその変更を検知できず、一回とカウントしてしまうところに問題があったわけです。

しかし、以前の研究ではStarlightはオオモノが同時に二体出現した場合でも正しく乱数生成をチェックできていました。速すぎてチェックできない状況というのはどういうケースでしょうか？

それは湧き方向変化とオオモノ出現が同時に行われるケースです。

乱数消費表

書くのがめんどくさいのでWAVE1のものだけ載せておきます。詳しく知りたい人はソースコードを読んでください。

	内容	秒数
0	初期化
1	湧き方向
2	オオモノ出現(1)
3	オオモノ出現(2)
4	湧き方向	88秒
5	オオモノ出現(3)
6	オオモノ出現(4)
7	湧き方向	78秒
8	オオモノ出現(5)
9	オオモノ出現(6)
10	オオモノ出現(7)
11	湧き方向	68秒
12	オオモノ出現(8)
13	オオモノ出現(9)
14	オオモノ出現(10)
15	湧き方向	58秒
16	オオモノ出現(11)
17	オオモノ出現(12)
18	オオモノ出現(13)
19	湧き方向	48秒
20	オオモノ出現(14)
21	オオモノ出現(15)
22	オオモノ出現(16)
23	湧き方向	38秒
24	オオモノ出現(17)
25	オオモノ出現(18)
26	オオモノ出現(19)
27	湧き方向	28秒
28	オオモノ出現(20)
29	湧き方向	18秒
30	湧き方向	8秒

最初、湧き方向変化は8回かと思っていたのですが、乱数は10回消費されていることがわかりました。まあひょっとしたら乱数が消費されているだけで湧き方向は変わっていないのかもしれませんが。

今後の展望

結局これをやって何がしたかったというと、サーモンランのWAVEとして取りうるものの中から、最も難しい（と思われる）WAVEをプレイしたかったんですよね。

いや、本当にそれだけです。Ocean Calcとかぶっちゃけどうでもいいです。

問題は「難しい」をどうやって評価するかなのですが、まあざっくりいえばカタパとコウモリばっかり湧けばかなりきついと思います。通常潮で遠くのタワーとカタパばっかりっていうのもまあ難しそうな気はするのですが、回収が難しいというよりも処理が難しいという方に重点を起きたい感じはします。

アシックス（@asicssix）氏がサーモンランの統計データから各オオモノの金イクラ納品期待値を計算してくれているので、それを使って期待される納品数が最低のWAVEとかを探してみるのも面白いかもしれませんね。

記事は以上。