カービィのエアライド - seed 値検索を少しだけ高速化

(C 言語を読める人向けです。)

カービィのエアライドにおいて、ゲーム内の事象から seed 値を特定する際、総当たりで検索するとあまりにも時間がかかりすぎるので、少しだけ高速化を施しました。最大で 60 秒かかっていた検索が最大で 0.03 秒ほどになり、実用上気にならない程度の速度になりました。

おそらく、線形合同法が使用されていてかつ (seed 値を R として ) R * n >> m の形で seed 値から結果を生成するタイプのゲームに流用でき、手法も難しくないので備忘録がてら共有します。

カービィのエアライドにおける疑似乱数の生成式と、結果の生成

seed 値はゲームの起動時にタイムベースレジスタで初期化されます。 1 秒で 4050 万ほど変動するので、調整は現実的ではありません。また、更新は以下の式で行われます。一般的な線形合同法です。

s = (s * 0x343FD + 0x269EC3) & 0xFFFFFFFF;

デスマッチ 1 にて NPC がマシンを選択する際に、以下の式でマシンが選択されます。

m = (s >> 16) * 15 >> 16;

2~4P (NPC) の選択したマシンを十分な数観測し seed 値の列に当てはめることで、 seed 値を特定することができます。

seed 値の特定

以下、コード全文。

code.c

#include <stdio.h>
#include <stdbool.h>

typedef unsigned long long u64;

u64 s = 0x00000000;
u64 lcg_a = 0x343FD, lcg_b = 0x269EC3;

typedef struct rstep{
    u64 mul;
    u64 target;
    u64 tmin;
    u64 tmax;
    u64 offset;
} RSTEP;

u64 next();

int main(int argc, char *argv[]){
    u64 i, j, h, lm, la;
    bool f;
    RSTEP r[12], tmp;

    for (i = 0; i < 12; i++){
        if (argv[1][i] >= '0' && argv[1][i] <= '9'){
            r[i].target = argv[1][i] - '0';
        } else if (argv[1][i] >= 'a' && argv[1][i] <= 'f'){
            r[i].target = argv[1][i] - 'a' + 10;
        } else if (argv[1][i] >= 'A' && argv[1][i] <= 'F'){
            r[i].target = argv[1][i] - 'A' + 10;
        }
    }

    r[0].mul = 1;
    r[0].tmin = 0x100000000 / 15 * r[0].target;
    r[0].tmin = (r[0].tmin & 0xFFFF0000) + ((r[0].tmin & 0xFFFF) != 0) * 0x10000;
    r[0].tmax = 0x100000000 / 15 * (r[0].target + 1);
    r[0].tmax = (r[0].tmax & 0xFFFF0000) + ((r[0].tmax & 0xFFFF) != 0) * 0x10000 - 1;
    r[0].offset = 0;
    s = r[0].tmin;

    for (i = 1; i < 12; i++){
        r[i].mul = (r[i - 1].mul * lcg_a) & 0xFFFFFFFF;
        r[i].tmin = 0x100000000 / 15 * r[i].target;
        r[i].tmin = (r[i].tmin & 0xFFFF0000) + ((r[i].tmin & 0xFFFF) != 0) * 0x10000;
        r[i].tmax = 0x100000000 / 15 * (r[i].target + 1);
        r[i].tmax = (r[i].tmax & 0xFFFF0000) + ((r[i].tmax & 0xFFFF) != 0) * 0x10000 - 1;
        r[i].offset = next();
    }

    lm = r[11].mul;
    la = r[11].offset;

    h = 12;
    f = false;

    while (h > 1 || f){
        if (h > 1) h = h / 1.3;
        f = false;
        for (i = 0; i < 12 - h; ++i){
            if (r[i].mul > r[i + h].mul) {
                tmp = r[i];
                r[i] = r[i + h];
                r[i + h] = tmp;
                f = true;
            }
        }
    }

    for (i = 0; i < (r[0].tmax - r[0].tmin); ){
        for (j = 1; j < 12; j++){
            s = (i * r[j].mul + r[j].offset) & 0xFFFFFFFF;
            if (s >= r[j].tmin && s <= r[j].tmax){
                continue;
            } else {
                while (!(s >= r[j].tmin && s <= r[j].tmax)){
                    if ((r[j].tmin - s) > r[j].mul){
                        i += ((r[j].tmin - s) & 0xFFFFFFFF) / r[j].mul + 1;  
                    } else {
                        i += 1;
                    }
                    s = (i * r[j].mul + r[j].offset) & 0xFFFFFFFF;
                }
            }
            break;
        }
        if (j == 12){
            printf("seed:%08X\n", (i * lm + la) & 0xFFFFFFFF);
            break;
        }
    }

    return 0;
}

u64 next(){
    s = (s * lcg_a + lcg_b) & 0xFFFFFFFF;
    return s;
}

何をしているか簡単に解説します。

まずゲーム上で NPC が選択したマシンの種類を 12 連続で観測します。
(9 連続だと一致するパターンが複数ありました。)
このコードでは、ジェット、フォーミュラ、ウィング、ワープ、ライト、デビル、ワゴン、ルインズ、ロケット、ターボ、ヘビー、スリック、バイク、スクーター、レックスの順に ID を 0~E とし、それを 12 文字の文字列としてコマンドライン引数に渡しています。

(s >> 16) * 15 >> 16 で結果が生成されるということは、結果からそれぞれの seed 値の範囲を絞り込めるということになります。具体的には、結果が 0 なら 0x00000000~0x1111FFFF, 1 なら 0x11120000~0x2222FFFF … 14 なら 0xEEEF0000~0xFFFFFFFF という具合。

なので、 1 つ目の結果が 0 だった場合、 1 つ目の seed 値 (r[0] とします ) は 0x00000000~0x1111FFFF であり、検索を開始する seed 値を約 1/15 に絞り込めます。
この範囲を r[0].tmin, r[0].tmax とします。

次に、 r[0] の取りうる範囲内で検索を開始し、 r[1] が一致するか確かめます。

(以下、出てくる値は全て & 0xFFFFFFFF で丸められます。)
ここで、線形合同法の性質を考えます。
r[0] を進めるステップ数を i として疑似乱数の生成式に当てはめると、 r[1] = (r[0] + i) * a + b と表せます。
つまり、 r[0] が i 進むと、 r[1] は i * a 進むことが分かります。
同様に、 r[2] は i * a^2, r[3] は i * a^3 … r[11] は i * a^11 進みます。
この a^n を r[n].mul として設定します。

最初に r[0].min で 11 回乱数を消費し、それぞれの値を r[1~11].offset として設定し、そこに r[1~11].mul * i を足せば、検索している seed 値が r[1~11].tmin から r[1~11].tmax の範囲に入っているか分かります。
入っていなかった場合は、入る seed 値になるまでステップをスキップします。
スキップするステップ数は (r[n].tmin - (r[n].mul * i + r[n].offset)) / r[n].mul + 1 で求め、入らなかった場合は入るまで同様にスキップして処理を続行します。
( ここ、tmin <= (mul * N + offset) mod 2^32 <= tmax が成り立つ N の条件が思いつきませんでした…。 )

この処理を r[1] から r[11] まで続け、全てが tmin から tmax の範囲に入っている seed 値が、ゲームで観測した事象と一致する seed 値になります。
なお、スキップ数をより多く稼ぐために、探索の処理を始める前に mul の値で配列を昇順にソートしています。

以上です。

( 追記 : 文字だけでは少し分かりづらいかもしれないので、画像を追加します。 )
↑追記 : 「 a^j 増える」は「 i*a^j 増える」の間違いでした。