キンシャケ探しインデックスバグの詳細

WAVE1の初手アタリ位置の偏り

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

スプラトゥーンの乱数スプラトゥーンの乱数生成器は以下のようなPythonコードで表現できます。class NSRandom: mSeed1 = 0x00000000 mSeed2 = 0x00000000...

tkgstrator.work

2021.02.15

前回の記事でWAVE1に発生するキンシャケ探しにおいてアタリ位置が大きく偏っていることは解説したが、実際にどのくらい偏っているのかを調べたのが今回の記事の内容になります。

通常潮位の場合

前回の記事では絶対に初手でアタリ位置にならないポイントがあると述べましたが、それぞれのアタリの確率を全通り調べることでチェックしました。

	A	B	C	D	E	F	G	H	I
シェケナダム	0.0000%	12.2175%	12.2274%	12.4400%	12.6129%	12.7169%	15.5655%	11.1076%	11.1121%
ドンブラコ	0.0000%	13.6241%	14.1779%	14.4848%	14.6779%	18.0336%	12.5000%	12.5017%	–
シャケト場	0.0000%	12.2175%	12.2274%	12.4400%	12.6129%	12.7169%	15.5655%	11.1076%	11.1121%
トキシラズ	0.0000%	16.3615%	17.0888%	17.4402%	20.5351%	14.2890%	14.2855%	–	–
ポラリス	0.0000%	16.3615%	17.0888%	17.4402%	20.5351%	14.2890%	14.2855%	–	–

通常のキンシャケ探しでは全てのアタリ位置に対して二つ以上ゴール候補が存在するので、どこがアタリ位置になるかは初期シードとカンケツセン数だけで決まります。

なのでシェケナダムとシャケト場は必ず同じアタリ位置になりますし、トキシラズとポラリスも必ずおなじになります。特筆すべきはトキシラズとポラリスで、アタリ候補は7つあるので同様に確からしいとすればアタリの確率は約14.2875%のはずなのですが、インデックスバグにより初手は必ずAがアタリにならず、しかも本来Aがアタリになるべき期待値が残りの候補に均等に割り振られていないため、Eのアタリ確率が1/5よりも大きくなっています。

なので、開栓手数やコンテナとの距離などを考えなければトキシラズとポラリスにおいては初手Eを開けるのが最も良いということになります。

満潮の場合

	A	B	C	D	E	F	G	H	I
シェケナダム	–	–	–	–	0.0000%	28.4996%	31.4996%	19.9962%	20.0045%
ドンブラコ	–	–	–	–	0.0000%	50.0145%	24.9789%	25.0067%	–
シャケト場	0.0000%	28.4996%	31.4996%	19.9962%	20.0045%	–	–	–	–
トキシラズ	–	–	0.0000%	28.4996%	31.4996%	19.9962%	20.0045%	–	–
ポラリス	–	–	–	0.0000%	50.0145%	24.9789%	25.0067%	–	–

ポラリスに関してはアタリ位置に対してゴール位置が一つしかないため、ゴール位置を決めるときに乱数を消費しません。その結果、本来Dの位置がアタリになるべき確率が全てEに吸収されるという（まるでモンティ・ホール問題）異常事態が発生しています。また、同様にドンブラコでもEのアタリ位置の確率が全てFに吸収されています。

ポラリスはともかく、ドンブラコであれば初手は確実にF開けが良いでしょう。

連続しないアタリ位置

更に予想されたのは初手以外のカンケツセンのアタリ位置にも偏りが出てくるのではないかということです。

というのも、前回ポラリス満潮を検証したときにWAVE1である位置が三連続で同じ位置がアタリにならなかったためです。これを利用すれば、開栓手順がもっと効率化できる可能性があるわけです。

この章の解析はC++を使って全通り（4000万通り全て！）について検証したのでプログラムにバグがない限りは確実な精度を保証できます。

通常の場合

–	A	B	C	D	E	F	G	H	I
シェケナダム	×	◯	◯	◯	◯	◯	◯	◯	◯
ドンブラコ	×	◯	◯	◯	◯	◯	◯	◯	–
シャケト場	×	◯	◯	◯	◯	◯	◯	◯	◯
トキシラズ	×	◯	◯	◯	◯	◯	◯	–	–
ポラリス	×	◯	◯	◯	◯	◯	◯	–	–

また、追加で調べたところ三連続同じアタリ位置も存在することがわかりました。

つまり、通常潮位では使いみちがありません。

満潮の場合

WAVE1の満潮の場合、ドンブラコとポラリス以外は同じ場所が初手から二連続でアタリになることは絶対にありません。

–	A	B	C	D	E	F	G	H	I
シェケナダム	–	–	–	–	×	×	×	×	×
ドンブラコ	–	–	–	–	×	◯	◯	◯	–
シャケト場	×	×	×	×	×	–	–	–	–
トキシラズ	–	–	×	×	×	×	×	–	–
ポラリス	–	–	–	×	◯	◯	◯	–	–

これが一体何に使えるんだということになりますが、例えばトキシラズだと対岸のどちらかがアタリなら、次は両方開ける必要がないケースが存在することになります。

トキシラズのカンケツセンの内部IDはこのようになっていますが、例えば初手でCがアタリなら二回目はCは絶対ではアタリではありません。なので二回目はDを先にあけ、大ならEがアタリとわかるのでCよりも優先してDを開けたほうが良いことがわかります。ちなみにDが小の場合はCが大か小かでアタリ位置がFかGかが変わってくるのでこの場合はどちらも開けなければ確定させることはできません。

これが一つ増えて三連続となると、全てのステージで初手から三連続アタリとなるようなパターンは存在しません。

–	A	B	C	D	E	F	G	H	I
シェケナダム	–	–	–	–	×	×	×	×	×
ドンブラコ	–	–	–	–	×	×	×	×	–
シャケト場	×	×	×	×	×	–	–	–	–
トキシラズ	–	–	×	×	×	×	×	–	–
ポラリス	–	–	–	×	×	×	×	–	–

満潮のGraphNode出力

このままだとわかりにくかったので、とりあえず100万通りくらいのカンケツセンアタリ位置のフローチャートを出力してみました。

Pythonが遅すぎるので全部で4000万通りある中で100万通りしか検証していないため、ここで取得漏れしている組み合わせがあるかもしれませんが、まあ多分ないでしょう（無責任

1. 初手は必ずEではない
2. 初手と二回目は同じアタリ位置ではない

三つ目からは普通に候補が五つでてきているのでそれ以上の面白い成果は特にありません。

1. 初手は必ずEではない
2. 二回目と三回目は同じアタリ位置ではない

ドンブラコについては少し変わっていて、初回と二回目は連続する可能性があるものの、二回目と三回目は違うアタリ位置になるようです。

1. 初手は必ずAではない
2. 初手と二回目は同じアタリ位置ではない

というわけで、シャケト場はシェケナダムと同じようですね。

1. 初手は必ずCではない
2. 初手と二回目は同じアタリ位置ではない

というわけで、トキシラズはシャケト場やシェケナダムと同じようですね。

1. 初手は必ずDではない
2. 二回目と三回目は同じアタリ位置ではない

ポラリスはドンブラコと同じ法則になっていて、二回目と三回目が必ず違うアタリ位置になります。

ちなみに、ポラリスとドンブラコは四回目以降のアタリ位置も調べてみたのですが「絶対にアタリにならないカンケツセン」は存在しませんでした。どうも、四回目以降については気にしなくて良さそうです。

確率も計算させてみた

プログラムのコーディングの問題で直接確率を出せなかったのでとりあえず場合の数だけ表示してみました。

プログラムで0x1000000通り調べようとしたらミスって0x1000001通り出力されているのですが、そこはスルーでお願いします。実際にはWAVE1が満潮キンシャケ探しであるシードは4000万通りもあるので、全体の2.5%くらいしか調べられていないのですが、まあこれだけ調べれば洩れている組み合わせはないと思います。

ちなみに四回目に偏りがあるかどうか調べてみたのですが、有意な差は見つかりませんでした。

なので、インデックスバグが使えるのは初手から三回だということになります。

満潮キンシャケ探し最良手順

少なくとも、めちゃくちゃ偏っているポラリスの満潮については確実に変わります。

今までの最良手順は全てのアタリ位置が同様に確からしいという前提になっていましたが、その前提が崩れてしまったからです。

[決定版] カンケツセン最小手数問題

最小手数とは以下の記事で考察しているのだが、カンケツセンには理論的下限と実際に実現可能な最小解が存在します。理論的下限というのはカンケツセ

tkgstrator.work

2021.02.17

以前の解析ではポラリス満潮については、最良手順で開栓をした場合に平均手数2.00、最悪手数3.00であることがわかっています。また、理論的な下限として最悪手数2.32という値も得られています。

更に良い開栓手順を考えて平均手数を2.00よりどのくらい下げることができるか考えてみましょう。

考え方

偏りがあったとしても、結局は手数を最小化すれば良いだけなので今までと同じ解析手法が使えます。

プログラムを組んでもよいのですが、ヒューリスティックに解を求めてみましょう。

一回目

まず初手ですが、Dが絶対にアタリではないのでカンケツセンが実質三つしかありません。なので二手で確実にアタリ位置を見つけることができます。例えばGを開けて大ならEで確定、小ならFで確定です。乱獲においてはDあけがスタンダードになりつつありますが、WAVE1であれば絶対に当たらないDを真っ先に開ける意味は全くないです。

このとき、GをあけるかEを開けるかはなかなか難しい問題になります。Gを最初にあければ盤石ですが、Gをあけても無駄に終わる可能性が50%もあるためです。しかし期待値を重視してEをあけてスカだった場合にコンテナ横がザコシャケまみれになります。連携ができていればGスカからの即EあけないしはFあけはできると思うので、初手Gが良いのかなという気はします。

	平均手数	最悪手数
初手G	1.75	2.00
初手E	1.50	2.00

二回目

二回目は全てのカンケツセンがアタリ候補になりますが、二連続同じ場所になる確率が一番高いです。

同様に確からしいならば25％のはずですが、同じ場所がアタリになる確率は29%ほどあります。もちろん、全てが候補になる以上いたずらに手数を増やすFやコンテナ横のEはこの4%程度の差のためにわざわざ開けなくていいと思います。

ですが、一回目でGがアタリだった場合はこの4%の恩恵を受けるためにDではなくGをあけたほうが僅かに得になります。

三回目

二回目がアタリだったカンケツセンがアタリにならないため候補が三通りになります。

一回目の場合は候補が三通りかつ偏りがありましたが、三回目の場合は偏りは存在しません。なので、前回アタリでなかったところを無視して最小手数となる手順を選択します。

二回目のアタリ位置	初手	初手が大の場合	初手が小の場合	平均手数	最悪手数
D	G	E	F	1.67	2.00
E	–	–	–	2.00	3.00
F	D/G	E	G/D	1.67	2.00
G	D	E	F	1.67	2.00

すると上のような図になります。二回目がEがアタリのときだけは有効活用することができません。D, F, Gのどこをあけても必ず小になります。Fがアタリだった場合はDでもGでも期待値は変わりません。

事前にどちらに揃えておくか相談しておくと良いでしょう。

まとめ

思っていたより偏っていて、最大三回までこの恩恵を受けることができるとわかった。

ポラリスとドンブラコ以外は二回までしか偏りがないのだが、二回目に絶対に出現アタリにならないカンケツセン+偏りがあるので、利用できる情報の数はどのステージでも差がない。が、やはり利用できる回数が重要だと思うので、ポラリスやドンブラコの方が利用価値は高いだろう。

本記事では紙面の都合上（めんどくさい）ポラリス満潮しか取り扱わなかったが、他のステージでもより良い開栓手順が見つかる可能性が多分にある。

それは読者の皆様への宿題ということにしておこう（めんどくさい）

記事は以上。

Amazonほしい物リストを一緒に編集しましょう

www.amazon.co.jp