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

Hack

WAVE決定アルゴリズム

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

また、その成果を元にぼくがキンシャケ探しイベントのゴール位置のアルゴリズムを解析しました。

潮位とイベントだけでなくキンシャケ探しのアタリ位置まで予測可能になったことで最良のアタリ位置をもつシードを探し、キンシャケ探しの理論値がどのくらいかを検証することもできるようになりました。

しかし、まだ最も重要な部分がまだ解明できていませんでした。

それは、初期シードから「どのようにオオモノ出現テーブルが決まるのか」ということです。これを求めずしてサーモンラン解析が終わることはないと言っても良いでしょう。

オオモノ出現テーブルについての既知の知識

アルゴリズムが解析できていなくても、今までのイカッチャでのプレイの経験から以下のことはわかっていました。

オオモノの湧き順は初期シードで決まる

イカッチャではリトライをすると初期シードが固定されたままになります。また、リトライをするとイベント・潮位だけでなくオオモノの湧き順までもが同一のWAVEが繰り返されることがわかっていました。

つまり、オオモノの湧き順は初期シードから決まるということです。

上限にひっかかるとわずかに湧きが変わる

同一オオモノシャケは同時に三体までしかステージに存在できないのですが、イカッチャでオオモノをわざとたおさずに放置すると上限に達したオオモノの代わりに別のオオモノ(以後、代替オオモノと呼びます)が出現することが知られています。

「どれがどのオオモノに変化するかはランダムのようだ」というところまでしかわかっていません。

キケン度が下がるとオオモノ湧き順が変わる

通常プレイでは初期シードを固定したままキケン度を変化させることはできませんが、パッチを使ってそういう環境をつくることはできます。

200%から190%にキケン度を落とすとノルマが1減るのでオオモノ出現数も1減るため、一見すると200%のオオモノ湧き順のうち最後の一匹が出現しないようなWAVEになるのではないかという予想が立てられます。

しかし、実際には200%と190%では中盤以降全く違う湧き順になります。何故このようなことが起きるのでしょうか?

解析が困難な理由

イベント・潮位に比べてオオモノ出現テーブルのアルゴリズムを解析するのが困難な理由とはなんでしょう?

それは「どのアルゴリズムがオオモノ出現を司っているのかわからない」というのが最たる理由でした。アルゴリズムを解析するには「どのアルゴリズムを解析すべきか」ということがわかっていないといけないのです。

例えば、イベントと潮位に関してはGame::Coop::Settingというクラスがすべてのデータをもっています。これはクラス名からもなんとなくそんな雰囲気がわかりますよね。

更に、Game::Coop::SettingクラスにはchangeWaterLevel()というメンバ関数がありました。これは明らかに潮位の変化をするサブルーチンです。このように、関数名から非常に特定がしやすかったため潮位とイベントに関しては真っ先に解析が進みました。

それから遅れること半年ほど、ようやくキンシャケ探しイベントのアタリ位置のアルゴリズムが解析されました。キンシャケ探しのアタリ位置もリトライをすれば全く同じ位置がアタリになるので、初期シードから決まっていることはわかっていました。ただ、解析すべきアルゴリズムがなかなか特定されなかったのです。

最終的にぼくがGame::Coop::EventGeyserクラスのstateEnterIdle_()というメンバ関数内にあるsead::PtrArrayImpl::shuffle()という関数がカンケツセンの位置が入った配列をシャッフルして先頭にある位置がアタリになることが突き止めました。

ただ、アルゴリズム解析においては初学者だったので実際に初期シードからアタリ位置を計算する作業はcontainer12345氏がやってくれました。本当にありがとうございます。

そのコードを元にアタリ位置も計算することができ、キンシャケ探しイベントは完全解析することができました。

目星はついていた

とはいうものの、どのクラスがオオモノ出現テーブルを司っているのかはおおよその検討がついていました。

それがGame::Coop::EnemyDirectorで、これに目星をつけたのはキンシャケ探しイベントが解析されるよりも前のことでした。

ただ、これは本当に全てのシャケの挙動についてのクラスなので、実際にどのメンバ関数でオオモノ出現テーブルを生成しているのかが全くわかっていませんでした。

何しろメンバ変換数だけで120近くもあるのです。全てに目を通すだけで一苦労でした。

ブレイクスルーが訪れる

オオモノ出現テーブル解析が滞り、次第にぼくの興味も薄れていたのですがここでStarlight解析におけるブレイクスルーが訪れました。

それがShadowninja108氏が提案してくれたインスタンスを読み込むためのコードで、まあこれについては別記事で解説しようと思うのですが、とにかくStarlightで任意のインスタンスを呼び出すのがものすごく簡単になったのです。

これにより、検証したいコードを呼び出すために必要な作業が半分以下になりました。今までは検証するために一時間くらいかけ、違ったらまたやり直して一時間は無駄になるというとてつもなく骨が折れる作業だったのですが、このコードのおかげで一時間だった作業が一分もかからなくなりました。いや、ほんとすごいです。

解析が進む

さて、120もあるメンバ関数全てに目を通すことはできませんが、どこでオオモノ出現順が決められているか、ある程度の検討をつけることができます。

というのも、シードの値が1でも違えば潮位やイベントと同様にオオモノの出現順が全く異なることです。つまり、オオモノの出現に関して乱数生成器が使われていることはまず間違いないのです。

スプラトゥーンにおいては乱数生成器はsead::Randomというクラスが担っているのですが、Game::Coop::EnemyDirectorクラスでこのsead::Randomが呼び出されている周辺を探せば見つかる可能性があります。

実はGame::Coop::EnemyDirectorクラス自体はかなり解析が進んでいて、以下のような構造を持つことがわかっています。

#pragma once

#include "types.h"
#include "Lp/Sys/actor.h"
#include "Cmn/Actor.h"
#include "Lp/Utl.h"
#include "sead/random.h"
#include "sead/array.h"

namespace Game
{
    namespace Coop
    {
        class EnemyArray
        {
        public:
            sead::PtrArrayImpl ptrArray;
            char mBuffer;
            _BYTE gap_0x11[183];
        };

        class EnemyDirector : Cmn::Actor, sead::IDisposer
        {
        public:
            Game::Coop::EnemyArray mEnemy[3];
            _QWORD qword5C0;
            _DWORD dword5C8;
            sead::Random mRandom[2];
            _BYTE gap5EC[4];
            _QWORD qword5F0;
            _QWORD qword5F8;
            _QWORD qword600;
            _QWORD qword608;
            _QWORD qword610;
            _QWORD qword618;
            _DWORD dword620;
            _BYTE gap624[4];
            _QWORD qword628;
            _DWORD mEnemyAppearId;
            _BYTE gap634[96];
            _DWORD mActiveEnemyMax[2];
            _DWORD mActiveEnemyNum;
            _BYTE gap694[240];
            _DWORD dword76C;
            _QWORD qword770;
            _QWORD qword778;
            _QWORD qword780;
            _DWORD dword788;
        };
    }; // namespace Coop
};     // namespace Game

なんだこれって思うかもしれませんが、これがGame::Coop::EnemyDirectorクラスの全貌です。そしてよく見るとsead::Randomクラスのインスタンスを二つもっていることがわかります。これらに着目すればなにかわかるのではないかと考えました。

最初の目論見、成功する

最初、乱数生成器から調べようと思っていたのですがそれよりも目を引いたのがmEnemyAppearIdというメンバ変数でした。これがもし出現するオオモノのIDが入っているのであれば、ここの値が生成されているメンバ関数を調べればいいのです。

ということで、まずはStarlightを使ってここにどんな値が入っているのかを調べました。すると、不思議なことにこの値は1, 2, 3のいずれかの値しか持たないことがわかったのです。

これはおかしなことで、オオモノシャケは九体いるので最低でも0~8までの値をとらなければいけません。これがオオモノシャケのIDでないのなら、何を意味するのでしょうか?

何度かの検証の末、ようやくこの値の意味にたどり着くことができました。mEnemyAppearIdとはオオモノが出現する「位置」だったのです。これは俗に言う「湧き方向」というやつですね。

例を挙げると、シェケナダムの干潮時の湧き方向はコンテナからみて「左」「正面」「右」の三つがありますが、右から順にIDが1, 2, 3と割り当てられています。この画像では3になっているので、3の位置である「左」からカタパッドやドスコイが出現しているのです。

乱数生成器の解析

出現位置を司る変数がわかったのは良いことですが、本当に知りたいのはオオモノの湧き順です。どうすれば知ることができるでしょうか?

そこで、先程見つけた乱数生成器に注目することにしました。Starlightでは「どこかのサブルーチンで乱数が生成されたときの乱数の値」を知ることはできませんが「乱数が生成されたかどうか」は知ることができます。

u32 Random::getU32()
{
    u32 n = mSeed1 ^ (mSeed1 << 11);

    mSeed1 = mSeed2;
    mSeed2 = mSeed3;
    mSeed3 = mSeed4;
    mSeed4 = n ^ (n >> 8) ^ mSeed4 ^ (mSeed4 >> 19);

    return mSeed4;
}

それは、スプラトゥーンにおける疑似乱数生成器が上のようなコードになっているからです。内部状態であるmSeed1 ~ mSeed4から乱数が生成されるのですが、見てわかるように乱数が生成されると内部のシードが一つずつズレるのです。つまり、生成された乱数はわからないものの(今回の場合はmSeed4を見ればわかるのだが)、内部状態がズレたことを見れば乱数生成器が動作したことがわかるのです。

乱数が生成され、内部状態が変わることを「乱数が消費された」ということがあります。

解析用のコード

もしも、Starlightが実行できる環境にあるのであれば以下のコードを書けば検証することができます。

Game::Coop::EnemyDirector *mEnemyDirector = Cmn::Singleton<Game::Coop::EnemyDirector>::GetInstance_();

if (mEnemyDirector != NULL)
{
    textWriter->printf("EnemyAppearId: %X\n", mEnemyDirector->mEnemyAppearId);
    textWriter->printf("ActiveMax: %02d / %02d\n", mEnemyDirector->mActiveEnemyNum, mEnemyDirector->mActiveEnemyMax[0]);
    textWriter->printf("ActiveMax: %02d / %02d\n", mEnemyDirector->mActiveEnemyNum, mEnemyDirector->mActiveEnemyMax[1]);
    textWriter->printf("EnemyArray: %03d\n", mEnemyDirector->mEnemy[0].ptrArray.mLength);

    textWriter->printf("sead::Random[0] %08X %08X %08X %08X\n", mEnemyDirector->mRandom[0].mSeed1, mEnemyDirector->mRandom[0].mSeed2, mEnemyDirector->mRandom[0].mSeed3, mEnemyDirector->mRandom[0].mSeed4);
    textWriter->printf("sead::Random[1] %08X %08X %08X %08X\n", mEnemyDirector->mRandom[1].mSeed1, mEnemyDirector->mRandom[1].mSeed2, mEnemyDirector->mRandom[1].mSeed3, mEnemyDirector->mRandom[1].mSeed4);
}

二つの乱数生成器の意味

何故乱数生成器が二つあるのか、その意味もわからないままコードを実行してみることにしました。

すると、ゲーム開始から実際にバイトが始まるまでに数回乱数が消費されていることがわかります。

実際にゲームが始まってから観察すると、Random[1]は頻繁に更新されているのに対してRandom[0]がなかなか更新されていません。

しかし、自分のプレイと見比べてすぐに「シャケをたおすとRandom[1]が消費される」ということに気が付きました。正確にはこれは正しくないのですが、解析の一歩になったことは間違いないです。

乱数消費のロジック

Random[1]についてはまるでシャケをたおすと消費されているように見えますが、実際にはシャケが出現したときにのみ再消費されます。ただ、この「シャケ」に「タマヒロイ」が含まれるかどうかはわかっていません。含まれないような気がしますが、まあちゃんと検証すればわかるので後回しです。

Random[0]については「オオモノシャケが湧いたとき」か「湧き方向が変化したとき」に消費されます。つまり、キケン度200%と190%でまるっきり湧きが変わってしまったのはこれが原因だったのです。

というのも、キケン度MAXでは湧き方向変化は八回あるにも関わらず、199.9%(存在するかは知らんが)では六回しか変化しないからです。つまり、単純にオオモノが一体減っただけではなく、湧き方向変化が二回減ったために合計で乱数消費が三回も減ってしまったのが原因だったのです。

乱数生成器の生成

ではその肝心の乱数生成器はどうやって生成されているのでしょう?試しにイカッチャでリトライを繰り返してみると、乱数生成器の初期の内部状態はキケン度に関わらず一定でした。

しかし、リトライ以外では内部状態が変わるので「内部状態が初期シードで決まる」ということは間違いないでしょう。そのまま初期シードで乱数生成器を初期化してくれていたら楽なのですが、キンシャケ探しアルゴリズムではインスタンスが生成されてから何度か乱数が消費されたり、生成された乱数で別の乱数生成器を初期化していたりしたので油断は禁物です。

かといって今の内部状態がどんなシードで初期化されたかは逆算できません(できないことはないがめんどくさい)

なので、以前作ったWAVEのシード検索アプリを改造して使ってみることにしました。

リンク先のウェブサイトで初期シードを入力し、GENERATEを押すと「内部状態として使われていそうな」値をガンガン生成してくれます。

テスト機能なので色々適当ですが、これで一応調べることができます。

するとあっさりと見つけることができました。オオモノが出現されるたびに消費される「オオモノ出現に関係していそうな乱数生成器」であるRandom[0]は初期シードで初期化されていることがわかりました。

今後の展望

まだ「オオモノ出現に関係していそうな乱数生成器」の特定と「その初期シード」を見つけただけにすぎず、実際に乱数生成器がつくる乱数から出現するオオモノを調べるという作業が残っている。

また「湧き方向変化」で乱数が消費されることから「湧き方向が変わる」「オオモノが出現する」正確なタイミングを知る必要がある。キケン度MAXだけわかればとりあえずなんとかなるが、最終的にはノルマごとにいろいろ調べて成果を発表したい。

一人だと解析は大変なので他の方の協力を仰ぎたいところである。長々と書いてしまったが、サーモンランのWAVE決定アルゴリズムの解析は確実に進んでいる。

記事は以上。

コメント

タイトルとURLをコピーしました