バトルシップはマインスイーパーのようなゲームで昔からあるボードゲームです。映画バトルシップのモトネタになりました。
ルールは説明するよりプレイしたほうが早いんでこちらを。
http://www.sousakuba.com/flash-games/battleship-game.html
例えば単純化して3x3のマスに1x2の駆逐艦だけを置く場合を考えます。置き方は以下の１２通り。
□■□ □□□ □□□ □□□ □■□ □■□ □■■ ■■□ □□□ □■□ □□□ □□□ ■■□ □■■ □□■ □□□ □□□ □□□ □□□ ■□□ □□□ □□□ □□■ □□■ □□□ □□□ ■□□ ■□□ □□□ □□□ □□□ □□■ □■■ ■■□ ■□□ □□□
これをランダムに選んだ場合、初手で真ん中を攻撃すると当たる配置は上の４通りで、当たる確率は4/12=1/3。角を攻撃すると当たる確率は2/12=1/6。角の間だと3/12=1/4。真ん中を攻撃するのがよさそうに見えます。
では相手が真ん中を攻撃すると知っていてその裏をかきたい場合、真ん中を避けて下の８通りからだけ選んで、それを相手も知っている場合は、相手は外側を攻撃します。その場合当たる確率は1/4。さっきより置く側が若干有利です。
さらに置く側は裏をかいて、上の４通りを確率p/4ずつ、下の８通りを確率(1-p)/8ずつでランダムに選ぶとします。
攻撃側は（１）真ん中を攻撃すると当たる確率はp、（２）角を攻撃すると当たる確率(1-p)/4、（３）角と角の間のマスだと確率(1-p)/4+p/4=1/4で当たることになります。（２）より（３）のほうが常に大きいので（１）か（３）かということになります。
どちらが大きいか考えると、p＜1/4の場合は（３）を攻撃、p＞1/4の場合は（１）を攻撃すればいいということになります。
置く側はこの確率を下げたい。それにはp≦1/4であればよくて、1/4で当たることになります。改善はなし。
と、ここまでは初手のみを考えた場合ですが、二箇所に当てるのにかかるターン数を最小にしようと思うと、真ん中は当たる確率大きいけど次に仕留めるのに最悪４ターンかかってしまうのに対し、角で当たった場合は最悪でも２ターンで終わるので、そのあたりも考える必要があります。
ごちゃごちゃと計算すると置く側は１２通りを完全にランダムに1/12の確率で選べば、相手が仕留めるまでのターンの期待値を一番大きくできることが分かります。これがもっと複雑な場合でも成り立つのか、つまり単純素朴に何も考えずに船を配置していけば相手が一番困る、のかどうか。なんとなく最大エントロピーとかの概念で証明できるような気もしますが、たとえば上の例で駆逐艦を二隻に増やしたらもうそれだけで計算が爆発しちゃうんでよくわかりません。
1x3の船を置く場合は計算が簡単で成り立つことは確認しました。
まずは、
Conjecture1: 攻撃側は各ターンで得られる情報エントロピーの期待値を最大にするようなマスを選べばターン数の期待値が最小になる
あたりを証明できれば。
３ｘ３の場合の戦略
□１□ ２□３ □４□
１，２，３，４の順に当たるまで攻撃。
Ａ＊Ｃ □Ｂ□ □□□
トドメをさせる確率はＡとＣで(1-p)/2、Ｂがp。よってp＞1/3ならＢＡＣの順に攻撃、p＜1/3ならＡＣＢの順に攻撃。
置く側はp=1/3にすれば最適。
ランダムに置く方法
たとえば長さ５の空母をランダムにどこかに置いて、空いてる場所に長さ４の船を置いて、、という方法では完全にランダムにはなりません！空母が真ん中にある配置はそれが邪魔になって他の船を置く場合の数が減るけど、端に空母を置く場合は邪魔にならないので場合の数が増えます。最初に空母を置く場合は他の全ての船を置く場合の数を数え上げて、それに比例した確率でマスを選ばないといけないのです。しかしそれは計算量が爆発して困難。
別の方法として、重なっても気にしないで全ての船をランダムに配置し、一箇所でも重なっていたらやり直し、という方法ならば効率は悪いけど実際のゲーム程度の船の密度ならなんとかなります。
