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

Hack

スプラトゥーンの乱数

スプラトゥーンの乱数生成器は以下のような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 &amp; 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の補助なしにアタリ位置を高い確率で予測できることがわかりました。つまり、パターンを覚えておけばハズレの開栓数を減らすことができるということです。

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

コメント

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