2021-11-06

湧き方向アルゴリズム完全に理解した

価格

# 湧き方向アルゴリズム

湧き方向を求めるアルゴリズムは解析済みで以下のようなコードになることがわかっていました。

u8 WaveMgr::getEnemyAppearId(u64 random, u8 id)
{
    u8 mArray[3] = {
        1, 2, 3
    };

    u8 x9, w9, x10, x11, x12, v17;
    u8 *x7, *w7;
    u64 x8, w8;
    u8 v5 = id;
    u8 x6 = 3;
    u8 w6 = 3;
    w7 = mArray;
    if (!(v5 & 0x80000000))
    {
        if (!w6)
            return v5;
        w8 = w6 - 1;
        do
        {
            v17 = w8;
            w9 = *w7;
            if (*w7 < v5)
                break;
            w6 -= w9 == v5;
            if (w9 == v5)
                break;
            w8 = v17 - 1;
            ++w7;
        }
        while (v17);
    }

    if (w6 < 1)
        return v5;

    x7 = mArray;
    x8 = random * w6 >> 0x20;
    while (1)
    {
        x9 = *x7;
        x10 = x8 == 0 ? 0 : x8 - 1;
        x11 = x8 == 0 ? *x7 : id;
        x12 = x9 == v5 ? 5 : x8 == 0;
        if (x9 != v5)
        {
            x8 = LODWORD(x10);
            id = x11;
        }
        if ((x12 & 7) != 5 && x12 & 7)
            break;
        --x6;
        ++x7;
        if (!x6)
            return v5;
    }
    return id;
}

ただしこれはバイナリを解析して得られたアセンブラを直接 C++に書き直しているだけなので可読性が非常に悪く、なんで 1 湧きが連続しないのかということはわからないままでした。

ただエミュレートしているだけでアルゴリズム解析ができていない以上、ひょっとしたら超低確率で湧き方向 1 が連続する可能性もあったわけです。

今回、このコードを Swift に移植するにあたり高速化のためにより深く解析を行うことにしました。

# Swift

そして解析した結果得られたコードが以下の通りで、二つのループ文を消した上で変数も二つにまで減らすことができました。

private func getEnemyAppearId(random: UInt32, lastAppearId: UInt8) -> UInt8 {
    let w6 = lastAppearId == 1 ? 2 : 3
    let x8 = UInt8((UInt64(random) &* UInt64(w6)) >> 0x20)
    switch lastAppearId {
        case 0, 3:
        	return x8 + 1
        case 1:
        	return x8 + 2
        case 2:
        switch x8 {
            case 0:
            	return 1
            case 1:
            	return 3
            case 2:
            	return 2
            default:
            	return 0
        }
        default:
        	return 0
    }
}

最終的にどんな湧き方向になるかは「一つ前の湧き方向」と「生成された乱数の剰余」だけで決定することがわかります。

# わかりやすい表

前回の湧き方向/剰余	0	1	2
0	1	2	3
1	2	3	-
2	1	3	2
3	1	2	3

湧き方向 0 について

湧き方向 0 は一番最初の初期化にしか使われない。

結論から言えば、湧き方向 1 が連続しないのは前回の湧き方向が 1 の時に除数として 2 が選ばれるために剰余が 0 か 1 のどちらかしか発生しないことが原因です。

プログラム的には前回の湧き方向が 1 で剰余が 2 であれば湧き方向は 1 になるはずなのですが、剰余が絶対に 0 か 1 しかありえないのでこのパターンは存在しないことになります。

よって、ありとあらゆるシードにおいて 1 湧きは連続しないことが証明されました。

では、結局どの湧き方向が一番多いのでしょうか？

# 湧き方向確率を考える

事前の総当り的な解析から次のことがわかっています。

湧き方向	1	2	3
初手	0.2252	0.3874	0.3874
全体	0.2490	0.3755	0.3755

といってもこれはたった 100 万件を調べて程度なので真の値を反映しているとは言えません。

# 前提条件

とはいっても、実際に全通り試さずに結果を予測するのですから予めある程度の前提条件が必要になります。

疑似乱数生成器(以降 PRNG とする)の出力は一様に分布している

今回必要になる条件はこれだけですが、スプラトゥーンの PRNG は Xorshift の亜種のようなものなので一様なのかと言われればかなり疑問が残ります。

が、これを前提にしないと全く始まらないのでここでは「ほぼ一様分布である」と仮定して話を考えます。

# 初手の湧き方向

初手の湧き方向を求めることは簡単です。まず、初期化によって湧き方向(この値は実際には使われない)が決定されます。

その湧き方向(以降 X0 とする)から初手の湧き方向が求められるのですが、X0 が 1 であれば 1 湧きは連続しないことから初手湧きは必ず 1 ではありません。

PRNG の出力が一様分布であれば以下のような表になるはずです。

初期化	1	2	3
1	-	50%	50%
2	33.3%	33.3%	33.3%
3	33.3%	33.3%	33.3%

つまり、湧き方向が 1 になるのは(1/3 * 1/3) * 2 = 0.2222...となります。

すると総当り解析で得られた 0.2252 という値は非常に近く信頼できそうな気がしてきます。

ちなみに 2 湧きと 3 湧きは確率が等しく、(1/3 * 1/3) * 2 + 1/3 * 1/2 = 0.3888...となります。

湧き方向	1	2	3
初手	2/9(0.2222)	7/18(0.3888)	7/18(0.3888)
全体	-	-	-

# 全体の確率を考える

N+1 回目の湧き方向を求めたければ N 回目の湧き方向の情報から計算すれば良いので、

のようなグラフを考えて漸化式を解いて一般式を求めれば良い。でもそれってめんどくさいですよね？

なので十分長いマルコフ連鎖として考えます。

すると、ノードが三つだけになるのでめちゃくちゃ考えやすくなりますね。

# 得られる方程式

$p_1 = p_2 * \frac{1}{3} + p_3 * \frac{1}{3}$

$p_2 = p_1 * \frac{1}{2} + p_2 * \frac{1}{3} + p_3 * \frac{1}{3}$

$p_3 = p_1 * \frac{1}{2} + p_2 * \frac{1}{3} + p_3 * \frac{1}{3}$

$1 = p_1 + p_2 + p_3$

これを計算すると、

$3p_1 = p_2 + p_3$

$p_2 = p_3$

$1 = p_1 + p_2 + p_3$

が得られ、最終的に解として、

$p_1=\frac{1}{4}, p_2=p_3=\frac{3}{8}$

が求められます。

MathJax

Vuepress + mathjax って複数行で数式かけないんですかね？

# 理論値と実測値の差異

では理論値と実測値を比較してみます。

# 理論値

湧き方向	1	2	3
初手	2/9(0.2222)	7/18(0.3888)	7/18(0.3888)
全体	1/4(0.25)	3/8(0.375)	3/8(0.375)

# 実測値

湧き方向	1	2	3
初手	0.2252	0.3874	0.3874
全体	0.2490	0.3755	0.3755

というわけで、いい塩梅に落ち着いたのではないでしょうか。

恐らくこれで間違ってはいないはずです、多分。

価格