カンケツセン最小手数問題

カンケツセンとは

スプラトゥーン2のコンテンツの1つであるサーモンランにおける夜イベントの1つに金シャケ探し(カンケツセン)と呼ばれるものがあります。

7つほどのカンケツセンの中に1つだけアタリがあり、それ以外は全てハズレでなるべく少ない手数でアタリを見つけるのが目標です。

もしもあけたカンケツセンがアタリかハズレしかわからないのであれば、最善の解法は順番にあけていくという方法しかなく、仮にアタリの候補がnあったとすれば当然最悪手数はnになります。

このとき、平均手数sは次の式で求めることができます。

[mathjax]
\[
s = \frac{1}{n}\times\sum_{k=1}^n{k}
\]

最もカンケツセンの数が多いのは通常時のシェケナダムと海上集落シャケト場で候補数は9になります。

つまり、あけたときの情報がなにもないのであれば最悪手数9, 平均手数5ということになります。

カンケツセン情報

ところがカンケツセンには水脈という概念があり、あけたカンケツセンによって他のカンケツセンがアタリかハズレかがわかります。

カンケツセンをあけたときの例

左のカンケツセンはあけたときの光の量が少なく、隣接するカンケツセンにアタリがないことがわかります。

一方、右のカンケツセンは光の量が多く、隣接するカンケツセンにアタリがあることがわかります。

これを利用することで、全てのカンケツセンをあけなくてもアタリを見つけることが可能になります。

細かいところは違いますが、マインスイーパのようなものだと思っていただけるととっかかりやすいかもしれません。

カンケツセン最小手数問題

ここで、カンケツセン最小手数問題を定義します。

  • カンケツセン候補数をnとする
  • 全てのカンケツセンがアタリである確率は同様に確からしい(アタリには偏りがない)とする
  • カンケツセンが隣接しているかどうかの情報であるnxnの隣接行列をmとする

この3つからアタリを見つける最小手数を考えます。

理論的下限

実はこの問題は理想的な隣接行列が与えられれば最小手数を理論的に計算することができます。

理想的な隣接行列というのはあけたときに「隣接しているか」「隣接してないか」 の候補がちょうど半分に分かれるような場合です。

例えば、ジョーカーを除く52枚のトランプから1枚を当てるというゲームをするとしましょう。

あなたはその1枚を知っている人間に「はい」か「いいえ」で答えられる質問をすることが許されています。

「どんなカードを選ばれていてもその1枚を当てることができる最小の質問回数は何回でしょうか?」という問題があったとします。

このとき「スペードのAですか?」「スペードの2ですか?」…のように順番にきいていく質問はとても効率が悪いです。

運が良ければ一回目で当たる可能性がありますが、運が悪いと最後まで当たらない可能性があります。

正しいのは「赤いカード(ダイヤかハート)ですか?」という質問や、赤いカードであることがわかった上で「ダイヤですか?」という質問です。

これらの質問は答えが「はい」「いいえ」のどちらであっても候補を半分減らすことができるので、効率の良い質問なのです。

このとき、任意のカードを当てるための最小の質問数nは以下のように計算できます。

[mathjax]
\begin{alignat}{3}
2^n &\geq 52 \\
n &\geq \log_{2}52 \\
n &\geq 5.70043971814
\end{alignat}

5.7回という質問回数は存在しないので、6回質問すればどんなカードを選ばれていても当てることができることがわかります。

二分木

ちょうど候補を半分減らせるような情報がある場合は、次のようなものを考えることができます。

ノード(大きさ)数7、高さ(レベル)3の二分木

もしもカンケツセンの隣接関係がこのようになっているのであれば、カンケツセンの候補が7つであれば3回以内で必ずアタリを見つけられることになります。

アタリがこの二分木のどれかのノードであれば良いので、カンケツセン候補数がnの場合に理論的に求められる最悪手数wとは次のように求められます。

また、sは最適な二分木が構成できた場合の平均手数です。

[mathjax]
\begin{alignat}{3}
\sum_{k=1}^w2^{k-1} &\geq n \\
2^w – 1 &\geq n \\
w &\geq \log_{2}(n+1) \\
\end{alignat}

これを用いて、各ステージの最悪手数を求めると次のようになります。

[table id=36 /]

このことから、シェケナダム・ドンブラコ・シャケト場の通常カンケツセンではどんなに効率的なあけ方をしても4回かかってしまうアタリの配置があることがわかります。

トキシラズとポラリスでは通常でも3回でアタリを見つけられる可能性がありますが、理論値がちょうど3なので完全二分木が構成できない場合には3回でアタリを当てることができません。

満潮に関しては、全てのステージで3回以内(ハズレは2つ)でアタリを当てることができる可能性があります。どのステージも理論値が2.60以下な(余裕がある)ので理想的な隣接行列から少しくらいはズレていても3回以内でアタリを見つけられそうです。

実現可能な値を求める

まずは理論値が達成できるかどうか微妙なトキシラズいぶし工房の通常カンケツセンを考えます。

与えられる情報はカンケツセン数nと隣接行列mです。

カンケツセン数は7なので、n=7です。では、隣接行列mはどんな値でしょうか。

[mathjax]
\begin{equation}
m =
\begin{pmatrix}
0 & 1 & 1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 \\
\end{pmatrix}
\end{equation}

計算方法

ここからやたらと専門的な内容になります。

苦手な人は読み飛ばしてください。

これは、与えられた行列から二分木を構成したときに最も高さを小さくした場合にいくらになるかを求める問題となります。

決定問題に言い換えるのであれば「与えられた行列を満たすように高さkの二分木は構成できるか」という問題になります。

決定問題(けっていもんだい、decision problem)とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。

出典: フリー百科事典『ウィキペディア(Wikipedia)』

最悪の場合でも高々ノード数nだけこの質問を繰り返せば良いので、この質問を常にO(1)で解を返すオラクル(神託機械)があれば多項式時間で計算できることは明らかです。

神託機械(しんたくきかい、英: oracle machine)または預言機械(よげんきかい)は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託(oracle)と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。

出典: フリー百科事典『ウィキペディア(Wikipedia)』

さて、この問題を解くのはどのくらい難しいのでしょう?

行列の大きさはノード数nの二乗なので、O(n^2)くらいあれば解けそうな気がするのですが…

Construct Binary Tree

日本語で検索してもさっぱりでてこなさそうだったので”binary tree matrix algorithm”とググったところ一発でめぼしそうなサイトを発見しました。

コーディングはのちのち書きます。

ヒューリスティック

今回のケースではカンケツセン数が高々9なので手計算でも十分解けます。

コーディングする前に頭の中で考えたほうがコーディングが捗りそうだったので、まずは頭で考えます。

今回はトキシラズ通常とポラリス通常が理論的下限である3回でアタリを見つける方法があるかどうかを考えます。

カンケツセン数が2の累乗-1の場合、この問題は先程述べたように「完全二分木が構成できるか」という問題と等価です。

完全二分木を構成するためには、まず先頭のノードが自身を除いたノードの集合を二等分できなければいけません。

これを数式で書くと…えーっとこんな感じでしょうか?

[mathjax]
\[
S = \{s \in \sigma – \{x\} \}\\
=\{ x | x \in \sigma, = \} \\
\]

あとで数学のプロにきいてちゃんと書きます(勉強しなきゃ

つまり、自身を除いた集合を二分割できる要素が一つもなければ完全二分木は作れないことになります。子ノードも同様のことを繰り返せばよいのでこれは再帰関数を用いて実装することができそうですね。

問題はノードがもつ集合の要素の数が偶数の場合ですが、これは要素の数の差が1になるように分割できれば最適な二分木が構成できます。

トキシラズいぶし工房

トキシラズの場合、隣接行列は以下のように与えられました。

[mathjax]
\begin{equation}
m =
\begin{pmatrix}
0 & 1 & 1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 \\
\end{pmatrix}
\end{equation}

このうち、完全二分木を構成できるノードは2, 4, 5, 6行目です。

このままでは呼びにくいので「1行目をA、2行目をB」と呼ぶことにします。すると候補となる2, 4, 5, 6行目はそれぞれB, D, E, Fと言い換えることができます。。

候補が0ではないので二分木を構成できる可能性があるため、先程の動作を繰り返します。

まず、最初に親ノードとしてBを選択します。するとBは{1010010}という要素を持つので、{ACF}, {DEG}という二つのノードを子にもちます。

Bを親とする二分木

次に{ACF}の集合について二分木が構成できるか考えます。

すると、Aを親にすると{CF},{φ}という分割になってしまい、二分木を構成することができませんが、CかFのどちらかであれば{A}{F}のように二分木を構成できます。

同様のことを{DEG}で行うと、次のような完全二分木が構成できます。

Bを親とする完全二分木

したがって、トキシラズいぶし工房の通常カンケツセンは三回以内でアタリを当てることができるということが証明できました。

朽ちた方舟ポラリス

隣接行列mは以下のように与えられます。

[mathjax]
\begin{equation}
m =
\begin{pmatrix}
0 & 1 & 1 & 1 & 1& 0 & 1 \\
1 & 0 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 0 & 1& 1 & 1 & 0 \\
1 & 1 & 1 & 0 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}
\end{equation}

大前提として、自身がアタリでなければ大にしかならないノードEが存在するため、Eを親とする完全二分木が構成できません。つまり、Eが葉となることは確定します。

また、完全二分木を構成できる親ノードはGしかありません。

Gを親とする二分木

このとき、Gが大であればAの大小を見ることでE, Fのどちらがアタリかは判断することができますが、B, C, Dはどれをあけてもアタリでなければ大になるので判断することができません。

よって、{B, C, D}は完全二分木をつくることができず、よってポラリス通常のカンケツセン配置は完全二分木をつくることができません。

従って、ポラリス通常カンケツセンを三回以内でアタリを見つける方法はないことがわかります。

シェケナダム

シェケナダムのカンケツセンマップ

カンケツセンマップは以下のサイトより引用させていただいた。

なにか問題があればご連絡ください。即刻削除いたします。

https://wikiwiki.jp/splatoon2mix/

カンケツセンの位置によっては死ぬほど遠いので二人で効率よくあけないと、時間をかけたのに金シャケがマズルートだとほぼほぼ間違いなく納品不足に陥る。

シェケナダム2オペ理想ムーブ

理解者が自分以外に一人いるなら、この動きが高速にアタリを発見できると思われる。

赤いカンケツセンはプレイヤー1があけ、青いカンケツセンはプレイヤー2があける。

それぞれ最初の一回ずつカモンとナイスで連絡を取り合う。

ナイスがきたら目の前のカンケツセンを開け、カモンが来たら次に行くべき場所に移動する。

二回目以降にカモンもナイスも不要なのは、二回目以降は二人が近くにいるためアタリかハズレかを目視で確認できるためである。


今度ちゃんと覚えて、どのくらい早く当てられるかやってみたい所存。

ただ、このあけ方は絶対に広まっていなのでフレンド以外でわかっている人がいると思わないほうがいい。最悪、なんでいきなりAをあけてるんだよって思われても仕方ない。

AがハズレならF以外はハズレなので、Aがハズレでザコシャケが湧いてきても残りの二人が適当にシバいておけば大丈夫と思われる。

何故ならAがハズレの場合、コンテナ左側のカンケツセンは他にあけないからだ。

Iがハズレの場合はコンテナ左側のカンケツセンであるFを開けることになるが、そのときはFは確定でアタリなのでザコシャケであふれかえるという心配もない。

海上集落シャケト場

難破船ドンブラコ