えいむーさんは明日も頑張るよ

スプラトゥーンの乱数実装ミスについて

サーモンラン Python

価格

# スプラトゥーンの乱数

スプラトゥーンの乱数生成器は以下のような Python コードで表現できます。

class NSRandom:
    mSeed1 = 0x00000000
    mSeed2 = 0x00000000
    mSeed3 = 0x00000000
    mSeed4 = 0x00000000

    def __init__(self):
        pass

    def init(self, seed):
        self.mSeed1 = 0xFFFFFFFF & (0x6C078965 * (seed ^ (seed >> 30)) + 1)
        self.mSeed2 = 0xFFFFFFFF & (0x6C078965 * (self.mSeed1 ^ (self.mSeed1 >> 30)) + 2)
        self.mSeed3 = 0xFFFFFFFF & (0x6C078965 * (self.mSeed2 ^ (self.mSeed2 >> 30)) + 3)
        self.mSeed4 = 0xFFFFFFFF & (0x6C078965 * (self.mSeed3 ^ (self.mSeed3 >> 30)) + 4)

    def getU32(self):
        n = self.mSeed1 ^ (0xFFFFFFFF & self.mSeed1 << 11)
        self.mSeed1 = self.mSeed2
        self.mSeed2 = self.mSeed3
        self.mSeed3 = self.mSeed4
        self.mSeed4 = (n ^ (n >> 8) ^ self.mSeed4 ^ (self.mSeed4 >> 19))

        return self.mSeed4

コードを見ると Xorshift に近い感じがするのですが、ひょっとしたら独自の乱数生成器なのかもしれません。排他的論理和とビットシフトしか使わないので非常に高速に乱数を生成できるのが強みです。

今回はこの乱数が主役となります。

# 乱数に偏りがありそう

Ocean Calc によって初期シードからイベント内容などを先読みできるようになり、いろいろと理想の WAVE を探す中で乱数による偏りがあるのではないかという予想がでてきました。

というのも、例えば満潮ラッシュで常に湧き方向が同じであるような WAVE を探すと WAVE2 か WAVE3 にしか存在しなかったり、満潮キンシャケ探しで同じ位置がアタリになりつづけるような WAVE も WAVE2 や WAVE3 にしか存在しなかったためです。

決め手となったのは WAVE1 のラッシュで初手の湧き方向が 1 であるシードがある程度調べても一つも見つからなかったことでした。スプラトゥーンの疑似乱数生成器に欠陥があると思われるのですが、一体どういう理由からこのような差が生じているのかを調べることにしました。

# WAVE シードの実装ミス？

まず最初に初期シードから各 WAVE のイベント情報を決めるときのアルゴリズムと、各 WAVE の内容を決定する WAVE シードの選び方に問題があるのではないかと考えました。

def getWaveInfo(self):
    mEventProb = [18, 1, 1, 1, 1, 1, 1]
    mTideProb = [1, 3, 1]
    self.rnd.init(self.mGameSeed)

    for wave in range(3):
        sum = 0
        for event in range(7):
            if (
                (wave > 0)
                and (self.mEvent[wave - 1] != 0)
                and (self.mEvent[wave - 1] == event)
            ):
                continue
            sum += mEventProb[event[
            if (self.rnd.getU32() * sum >> 0x20) < mEventProb[event]:
                self.mEvent[wave] = event
        sum = 0
        for tide in range(3):
            if tide == 0 and 1 <= self.mEvent[wave] and self.mEvent[wave] <= 3:
                continue
            sum += mTideProb[tide]
            if (self.rnd.getU32() * sum >> 0x20) < mTideProb[tide]:
                self.mTide[wave] = 0 if self.mEvent[wave] == 6 else tide

これは Python コードですが、WAVE の潮位やイベントを決める際には初期シードである mGameSeed を使って乱数生成器を初期化しています。

def setWaveMgr(self):
    self.rnd.init(self.mGameSeed)
    self.rnd.getU32()
    self.mWaveMgr = [
        WaveMgr(0, self.mGameSeed),
        WaveMgr(1, self.rnd.getU32()),
        WaveMgr(2, self.rnd.getU32())
    ]

そして、WAVE でのオオモノシャケの出現などを決定する WAVE シードは初期シードから計算されるのですが、何故か WAVE1 の WAVE シードには初期シードが使われてしまっています。そして、意味もなく（全く何にも使われていない）一回無駄に乱数が生成されることがわかっています。

これは確認のしようがない以上推測に委ねるしかないのですが、本来は以下のように三回ちゃんと初期シードから生成された乱数を WAVE シードにするはずが、任天堂の実装ミスで初期シードを WAVE シードにしてしまったのではないかと考えられるのです。

def setWaveMgr(self):
    self.rnd.init(self.mGameSeed)
    self.mWaveMgr = [
        WaveMgr(0, self.rnd.getU32()),
        WaveMgr(1, self.rnd.getU32()),
        WaveMgr(2, self.rnd.getU32()),
    ]

そしてこの WAVE シードの実装ミスと思われる不可解なコードがラッシュイベントにおけるランダム性に影響を与えることになりました。

# WAVE1 における偏り

WAVE1 は WAVE シードが初期シードになっているため、一番影響が大きいと思われる WAVE です。

具体的にどんな偏りがあるのかを、イベントごとに調べてみました。

なお、昼イベントとドスコイ大量発生、霧では湧き方向とオオモノの種類にしか影響しないのでここでは考えないことにしました。

# ラッシュ

ラッシュは WAVE1 に発生した場合、何故か初手は 1 湧きになりにくいことが知られていました。1000 万通りくらい調べても初手 1 湧きがないので「ないだろう」という予想だったのですが、実際に調べてみることにした。

1 湧き 2 湧き 3 湧き
干潮 - - -
通常 0.0000%(0 通り) 52.6085%(70050477 通り) 47.3914%(63103715 通り)
満潮 0.0000%(0 通り) 47.3500%(21131287 通り) 52.6499%(23496525 通り)

というわけで、実際に WAVE1 のラッシュは絶対に初手は 1 湧きではないことが確定しました。

では何故 WAVE1 のラッシュの初手 1 湧きが発生しないのかということになるのですが、これはラッシュのイベント ID が 1 であることが重要になってきている気がします。

というのも、オオモノの湧き方向は 1 湧きが連続しないことは知られているのですが、最初の湧き方向を決める前に一回「ゲーム内では発生しない湧き方向変化」を初期化として行っていることが分かっています。そして、その後に最初のオオモノの湧き方向変化をするのですが、この「ゲーム内では発生しない湧き方向変化」がラッシュの場合では常に 1 になっている可能性があります。

これは実際にアルゴリズム解析をしなければわからないのですが、初期シードは「WAVE1 のイベント ID が 1 となるような乱数」を返したので、同じ初期シードで初期化された「WAVE1 の最初の湧き方向変化」も 1 が返ってきていてもおかしくありません。

少なくとも「アルゴリズム内には WAVE1 のラッシュの場合は初手 1 湧きにしない」といったコードは書かれていないので、これは任天堂の実装ミスの弊害の可能性があります。

# グリル

グリルに関しては初手湧きは正しく 1 湧きが発生しました。

1 湧き 2 湧き 3 湧き
干潮 - - -
通常 22.2694%(29718747 通り) 38.8657%(51866811 通り) 38.8649%(51865710 通り)
満潮 22.2440%(9930800 通り) 38.8861%(17360628 通り) 38.8699%(17353391 通り)

# キンシャケ探し

盛大にバグってしまったのがこのキンシャケ探し。

キンシャケ探しのアタリ位置の決め方なのですが、

  1. カンケツセンの数だけループ（ポラリス満潮なら 4 回）
  2. 乱数を生成してカンケツセン数による剰余を計算
  3. その剰余をインデックスとする（ポラリス満潮なら 0 ~ 3 のどれかになる）
  4. ループ回数目とインデックス番目のカンケツセンの中身を入れ替える

そして、ループが終わった後の 0 番目のカンケツセンの位置がアタリ位置になっています。

文字だけだとわかりにくいので簡単に説明すると、ポラリスの満潮の場合だと、[A, B, C, D]というような初期状態の配列を持っています。配列の中にはカンケツセン数の分だけ文字が入っているというわけです。

で、ゲーム開始前のカウントが 0 になった瞬間に乱数を生成してインデックスを計算します。ここでは仮にインデックスが 3 となったとしましょう。するとアルゴリズムは 3 番目のカンケツセンと 0 番目のカンケツセンの中身を入れ替えます。プログラムでは配列は 0 番目からスタートするので 3 番目である D と 0 番目である A を入れ替えて[D, B, C, A]となります。そして、これを 4 回繰り返します。もしもインデックスが 0 であれば 0 番目と 0 番目の位置を入れ替えるということなので、配列は変化しません。

で、最終的に[C, A, B, D]という配列になったとしましょう。アタリ位置は常に 0 番目なのでこの場合は C の位置のカンケツセンがアタリになります。

そしてここが WAVE シード実装ミスによる最大の弊害なのですが、初回のアタリ位置決定アルゴリズムを実行すると「配列の 0 番目の値は必ず初期配置から変化している」というとんでもないバグが見つかったのです。

絶対に 0 番目の値が初期配置から変化するということは「アタリ位置が必ず初期配置から変わっている」ということを意味しており、これはつまり「WAVE1 にキンシャケ探しがきたら満潮か通常かに関わらず、初手で"絶対にアタリではないカンケツセン"が存在する」と言えるということになります。

全てのステージと潮位においてカンケツセンの初期配置は分かっているので、どこが絶対にアタリにならないかは確実に判断することができます。

# まとめ

ラッシュの湧き方向バグによる恩恵はそんなにないと思うが、キンシャケ探しによるインデックスバグは結構大きいのではないかと思っている。

更に追加で調べていると初手以外にも大きく偏りがあり、Ocean Calc の補助なしにアタリ位置を高い確率で予測できることがわかりました。つまり、パターンを覚えておけばハズレの開栓数を減らすことができるということです。

これは便利なのではないでしょうか、どうでしょう？

価格
    えいむーさんは明日も頑張るよ © 2021