満潮のカンケツセン解析

これまでのあらすじ

カンケツセンの配列をSwapすることで少々バグがありながらも、任意の位置のカンケツセンをアタリにすることができました。

ところが何故かドンブラコのカンケツセンだけバグがあって、2と3のカンケツセンをそのままアタリにするとフリーズしました。

その後、container12345氏によってカンケツセンのアタリ位置を決定するshuffle()が完全解析され、シード値からのアタリ位置の完全予測ができるようになりました。

オリジナルのコードはPythonで書かれていて、一般的なWindowsマシンで動かせるようにするのと、コードの高速化のためにC++に移植したものが以下になります。

多分最新版はLinuxでしか動作しない、まだね。

今回の発展

さて、container12345氏のコードでアタリの位置を求めることはできましたが、ゴールの位置についてはわからないままでした。

ただ、shuffle()のコードから面白い事実がわかったので、今回はshuffle()の内容について簡単に解説したいと思います。

shuffle()の中身

shuffle()は大雑把に以下のような動作をします。

  • カンケツセンの数だけ要素を持った配列をつくる
    • 満潮ポラリスなら4、満潮トキシラズなら5といった感じ
    • これを[0, 1, 2, 3, 4]のように表現する
  • 以下、要素数の数だけループする
    • 乱数を生成し、それを要素数でかけて32ビットシフトする
      • これは乱数を要素数で割ったあまりに等しい
      • つまり、要素数が5なら返ってくる値は0, 1, 2, 3, 4のどれか
      • 返ってきた値をjとする
    • (要素数-i)番目とj番目を入れ替える
  • ループ終了後に0番目にある値がアタリ

偏りがあるかどうか

よくわからんので実際に実行して調べてみました。

まず最初は、シード値を固定して(要するに一回のカンケツセンにおいて)アタリを1677万回くらい当てた場合の出力を見てみました。

アタリ位置出現回数確率
0419564025.008%
1419305724.993%
2419251924.989%
3419600025.010%

というわけで、やはり単純に計算した場合は全く偏りがないようです。

ただ注意しなくてはならないのは潮の高さやイベントを決定するのも同じ乱数生成器(違うインスタンスを使ってはいるが)、満潮カンケツセンになるような値が生成されるときにはアタリの位置が偏ってしまう可能性も無きにしもあらずです。

スプラトゥーンは線形合同法と呼ばれる擬似乱数生成器を使っているのですが、これは擬似乱数としては質が悪い(詳しくはwiki参照)のでひょっとしたら何らかの欠点がスプラ内で発現するかもしれません。

が、基本的にはランダムであり偏りがないと実用的には問題ないでしょう。

ゴール位置の求め方

さて、ゴールの決め方なのですがcontainer12345氏のコードではアタリの位置までしか求められるようになっていなかったので多少手を加えて改良しました。

といっても、アタリを求めるコードに比べてゴール位置を求めるのはコード自体が非常に短いのでぼくでも十分くらいで実装できました。

以下、アタリを求めるルーチンです。

  • アタリ位置がreusableかチェックする
    • そうなら疑似乱数を生成する
    • 疑似乱数をアタリ位置に対するゴール候補数で割った余りkを求める。
    • アタリ位置に対するdist配列の(k-1)番目がゴール

このルーチンの面白いところは、アタリの位置によって再度乱数を生成するかどうかが決まるというところです。

再度生成した乱数でゴール位置をランダムに決めているということですね。

ところが、広く知られているように満潮ポラリスでは各カンケツセンに対してゴール位置が一つしかないので「ゴール位置を決める」という処理が不要なのです。

なので、満潮ポラリスは全てのカンケツセンに対してreusableフラグがFalseになっています。

ただ、dist配列はカンケツセンの初期配列みたいに簡単に求められないので実際にプレイして確かめないといけない…

また、勘の良い方は気づかれたと思うのですが、reusableフラグがfalseならば「その位置がアタリならゴール位置がたった一つしかない」ことがわかります。

満潮カンケツセン

この前、四時間くらいかけて頑張って調べました。

満潮時はどのステージもゴール位置はアタリ位置に対して最大で二つしか存在しないようです。

ポラリス

posreusabledist
0false3
1false2
2false3
3false2

満潮ポラリスは全てのreusableフラグがfalseで、ゴール位置であるdistも一つしかありません。

トキシラズ

posreusabledist
0true4, 2
1true3, 4
2true0, 0
3true1, 1
4true1, 0

満潮トキシラズはちょっと変な感じになっていて、2と3の位置のカンケツセンはゴールが一つしかないと思うのですが何故かreusableフラグがtrueになっていて意味もなく乱数を生成しています。

シャケト場

posreusabledist
0false3
1true2, 3
2true4, 1
3true4, 1
4true2, 3

シャケト場は0の位置のカンケツセンはゴール位置が決まっているのでreusableフラグがfalseになっています。

つまり、長年の疑問だった「カンケツセンは必ず逆ルートも存在するのか」というのが否定的に解決されたことになります。

0→3のルートはあるけど、3→0のルートはない!

シェケナダム

posreusabledist
0true3, 3
1true2, 3
2true1, 1
3true4, 1
4true3, 2

ここも満潮時は0と2の位置はゴールが一箇所しかない気がするのですが(検証不足なだけの可能性もある)、reusableフラグがtrueになっています。

ちなみに、別記事で紹介しているカンケツセンマップなんですが3と4の位置が逆です、すみません…

ドンブラコ

posreusabledist
0true2, 3
1false3
2true?, ?
3true1, 1

3がアタリならゴールは一つしかないのにreusableフラグがtrue担っているかと思えば、1ではゴール位置が一つでちゃんとfalseになっている頓珍漢なステージ。

配列を直接弄ってアタリ位置を強制的に入れ替えるとゲームがクラッシュする上に、2がアタリだとゴール位置がどうやっても求められなかったという意味不明なステージ。

候補が二つあるので、distは2のはずなんですがどうやっても上手くいかなかった。

こんなおかしなことになっているのは見た目だけ無効化されている消されたカンケツセンが影響している気がします。なにより、配列をスワップして落ちるというのが意味がわからん。

まとめ

アタリ位置に加えてゴール位置も求められたことで、満潮カンケツセンについては99%以上が解析できたことになります。

唯一謎なままなのがドンブラコがスワップして落ちる理由と、ゴール位置がうまく求められないことでしょう。まあ、実際にこれを解明してどのくらい役に立つかはわからないのでぼくはノータッチを貫こうと思います。

同様の手法で満潮以外も当然調べられるのですが、調べる意味がなさすぎるので多分やりません。

リクエストがあればやりますが、何故調べたいのかを140字以内で提出することを要求します!!(めんどくさいんだぞ)

記事は以上。