Study 7 「確率分析からの知見」

Study 6では単に全未確定マスの確率を計算したらどうなるか、ということを考えただけでしたが、 結果を見てみるとおもしろいことがいくつかわかります。Study 6の図３５を再掲してみたのが図１です。

たとえば、左下の23%, 77%の並びは、どちらか不明な２択なので普通50% 50%と思ってしまうのではないでしょうか？ しかし、実際は片方に危険性が寄るといった状況が見られます。 他にも、右上の方の13%, 44%, 44%, 13%という並びでは、ここも不明な３択ですが、 実際には13%というこの画面上で最も安全な場所が出現しています。

こうしてみると、絶対安全な場所はこれ以上見つけることはできなくても、 比較的安全な場所なら見つかるかもしれないのではないでしょうか。 もちろん確実でなくても地雷のある確率の低いところを選んで開ける方が失敗しにくいはずです。

では、地雷のある確率の低いところとはどんな場所でしょうか。 それを探すことがここでの課題です。

均等にならない原因

まず、さきほどの例で確率が均等にならないのはなんでだったかを思い出してみましょう。 図１のもとの状態の一部分を切り出した図２，３を見てください。

　　　　　＊＊
　■■■■＊４
　＊３２＊＊３
　＊２１２３＊

｜　　■　　
｜　　３２３
｜　　■１２
｜■■■２２
｜２＊４＊２
｜２２４＊２

図２の■の場所では、両端に地雷がある場合、真ん中２つのどちらかに地雷がある場合の計３通りがあります。 図３では、左下、右下、右上の３つに置く場合と、間の２つに置く場合の計２通りがあります。 Study 6の図２７−１〜８を見てもこれだけのようです。

そこで、図１と見比べてください。図２では両端２カ所に置くパターンが13%で、 真ん中のどちらか１カ所に置くパターンが44%です。 図３では３つ置くパターンが23%、２つ置くパターンが77%です。

地雷をたくさん置くパターンでは確率が低くなる傾向があるようです。 ちゃんと理由もありまして、 ここに地雷をたくさん置くということはその他の（数字に隣接しない）場所の地雷が減るということで、 よっぽど特殊な状況でない限り、数字に隣接しない場所の地雷が少ない方が、パターン数も少ないからです。

ちゃんと数学的に処理すれば、_nC_rと_nC_r-1を、 r＜n/2のときに比べてどうなるかを計算すればわかります。
_nC_r:_nC_r-1
=n!/r!(n-r)!:n!/(r-1)!(n-r+1)!
=1/r!(n-r)!:1/(r-1)!(n-r+1)!
=1/r*(n-r)!:1/(n-r+1)!
=1/r:1/(n-r+1)
=(n-r+1):r
で、n-r+1＞n-n/2+1＝n/2+1＞n/2＞rですから、_nC_rの方が_nC_r-1 よりも大きいことがわかります。この計算で何を求めたかというと、 数字に隣接しない領域での地雷の置き方のパターン数（の比）でしたから、全部の地雷の個数がmだったとすると、 残りnマスに残り地雷r個を置くというのは、数字隣接領域にはm-r個の地雷を置いて、 残りnマスに残り地雷r-1個を置くというのは、数字隣接領域にはm-r+1個の地雷を置いているということです。 つまり、数字隣接領域の地雷の数が多い置き方の確率のが小さい、ということになります。

補足ですが、r＜n/2という前提を解説すると、数字非隣接領域に置く地雷の率は50%未満ということです。 マインスイーパは上級でも99/480=20.625%から始まるゲームですし、50%になることは本当の終盤以外はめったに見ません。 つまりr≧n/2となることはめったにないと言えます。なのでその逆の前提を置いてみたわけです。

逆に言えば、終盤などで数字非隣接領域が1つとか2つとかいう時は、この方法に頼っていてはかなり危険度が高いと言えるでしょう。

法則１：地雷を最も少なく置くパターンすべてで地雷を置かない場所は比較的安全

ということで、ここではこの法則の正確さを実証します。 サンプルとして、今までにさんざん用いた２つを含め、新たに18サンプル足して、 全20個のサンプルを用意しました。 いずれも私が行き詰まった状態で記録したものです。 ただし数字隣接領域が多すぎるものはブラウザが凍るので省いてあります。 あまりいいサンプリングじゃありませんが怒らないでください。 （ちなみにver.1時代の話です、ver.2でかなり改善されました。）

これら20個のサンプルで、どの程度の精度があるかを求めたいです。 …求めたいのですが、いまいち知識がないので我流な推測統計でいきます。 （しかし20サンプルとは少ない。）

さて、この法則がどれだけ有用かを見たいわけですが、 ここで、「有用」とはどういう状態かはっきりさせておく必要があるでしょう。 いままで目的をあまりはっきりさせてきませんでしたが、 「当てずっぽうよりはましな手を探すこと」としてみたいと思います。 そうすると、当てずっぽうの定義のしかたにもよってきます。 当てずっぽうを単純に盤面の均した確率と考えることもできるでしょうし、 数字非隣接領域の確率と考えることもできるでしょう。 比べるために表１にまとめて書きました。

ということで、求めたい対象の候補を６通り考えてみました。確率そのもの、最小値をとる場所、 単純に盤面の均した確率以下の場所、単純に盤面の均した確率未満の場所、数字非隣接領域の確率以下の場所、 数字非隣接領域の確率未満の場所の６つです。 これらについて、地雷を最も少なく置くパターンすべてで地雷を置かない場所とどれが関連が強いかを調べてみましょう。

いきなり表を書いてもいいのですが、ここで便利なのがAICです。これはどのモデルが最もよく関連を表しているかを計算するものです。 しかも今回は「最小値をとる場所」といったような０か１かで表されるようなデータを含んでいます。 こうした関連を見るのに使えるのはCATDAPでしょう。CATegorical DAta Processの略らしいですが、 まあ大雑把に言えばいちばんいけてる（相関の高い）クロス表を見つけてくれるプログラムです。 統計学的にはずいぶんいい加減なこと書いてますが許してください。 オンラインでもCATDAPは使えます。 マニュアルがなくて細かいことはわかりませんが、でも便利です。

そこで、以上の対象から変数を定め、すべての数字隣接領域点を１データとして表を作りました。 この表をもとに、CATDAPに処理してもらいます。

目的変数は「最少0」(最少配置パターンで一切地雷を置かない)に加えて、「最少1」(最少配置パターンで常に地雷を置く)と、 「最多0」(最多配置パターンで一切地雷を置かない)と、「最多1」(最多配置パターンで常に地雷を置く)と、 を合わせて結果を見てみました。

まず表１のAIC TABLEを見ます。これはできたクロス表をいけてる順にならべたものです。 いけてる度合いがAICの値になっていて、小さい（負の値が大きい）ほどいけてるってことです。 AIC値が1違うだけでモデルとしての良さが違うと見られます。 例えば目的変数を「最少0」にしたときはこうなりました。

その他の目的変数も試したのですが、どれをとっても「最少0」が最もよいモデルになっていました。 説明変数も８つ用意しましたが、「確率」「非隣接領域確率差」「非隣接領域以下」ぐらいでよさそうですね。 では、これらのクロス表を見てみましょう。

表２を見ると、配置パターンなしでは半数弱が18%以下、６割以上が20%以下です。 逆に20%以下でも配置パターンありのものは2%しかありません。 20%と言うと、99/480=20.625%より低く、特に終盤のこうした部分には地雷が固まりやすいことも考えると、 かなりいい判断基準になっていると言っていいでしょう。

では非隣接領域と相対的にどうかと考えたのが表３，４です。が、結局全く同じことになっていますね。 これも0以下と0.01以上で大きく傾向が違っているのが見て取れると思います。 配置パターンなしでは77%が0以下にいます。

このデータには今の前提(r＜n/2)に明らかに合わないサンプル３(n=1, r=1)も入れています。 もちろんこれを除けばもうちょっとましになるでしょう。

ということでこの法則はそこそこ精度は高いようですが、地雷の個数が最少のパターンを数えるのは瞬時には難しいものが あります。ではこの法則を応用してもう少し何かわかりやすい判断基準をさがすことはできないでしょうか。

コンパートメント

ここで、コンパートメントという概念を定義したいと思います。定義としては、 「地雷のありなしのパターンが他の部分と独立に生成されるひとまとまりの領域」としましょう。 例えばもう何度も出てきているサンプル１１では、図４で色付けした部分がコンパートメントと言えます。

┌───────────
｜　　　　　　　　■３２
｜　　　　　　　　■＊＊
｜　　　　　■■■■＊４
｜　　　　　＊３２＊＊３
｜　　　　■＊２１２３＊
｜　■■■■３２００１１
｜　■３２３＊４２１１１
｜　■■１２＊＊＊１１＊
｜■■■２２２４３２１２
｜２＊４＊２１２＊１０１
｜２２４＊２２＊３１０１

赤・緑の部分に関しては一目瞭然でしょう。 青の部分に関しては若干とまどうかもしれませんが、 間に挟まった３の右側の２に着目すると、２の上と右上のどちらかに１つ地雷があって、 残る左上と左下にもう１つ地雷がある、そして挟まっている３はこのどちらであろうと干渉できないので、 青のコンパートメントはこの部分となるわけです。

こういったイメージはおそらく配置のパターンの探索を何度も手でやっていれば次第に見えてくるものだと思います。 独立に考えてよい、というのはとても手間を省くのによいものですから…。

さて、このコンパートメントは大きいものも小さいものも出てきます。 大きいと瞬時にどこからどこまでかを判断するのは無理ですが、 小さいものならば判断もしやすいですし、その中で地雷を置くパターンを探すこともできます。 ということで適用しやすいように法則１を書き換えてみました。

法則２： 小さいコンパートメントの中で地雷を最も少なく置くパターンすべてにおいて地雷を置かない場所は比較的安全

図４の赤いコンパートメントに関して、地雷を置くパターンをすべて探すことは簡単でしょう。 図５−１〜３しかありません。

　　　　　＊＊
　　？　　＊４
　＊３２＊＊３
　＊２１２３＊

　　　　　＊＊
　　　？　＊４
　＊３２＊＊３
　＊２１２３＊

　　　　　＊＊
　？　　？＊４
　＊３２＊＊３
　＊２１２３＊

１つしか置かない図５−１，５−２が最も少ないパターンですので、 ここで地雷が置かれている真ん中の２つは危険、両端の２つはどちらにも置かれていないので比較的安全、と言えるでしょう。 青のコンパートメントについても同様のことが言えます。

この法則が成立するというのは演繹的にすぐわかります。というのも、コンパートメントを 「地雷のありなしのパターンが他の部分と独立に生成される」と定義したからです。 全体で最少のものは、独立な一部分では必ず最少であるはずです。

では、コンパートメントに限ったときのAICをまた見てみたいと思います。 見慣れれば最少配置パターンがすぐ発見しやすいコンパートメントで、 内部で地雷の個数が変化するコンパートメントを２０サンプルから選んで書き出しました。 分析した全コンパートメント一覧は別ページ参照。

抽象的な法則１もここまで限定化すればわりと使いやすく、精度も高くなったと思います。 しかし、ここではあまりに「小さい」目で見て最少配置パターンが一瞬でわかるようなコンパートメントに限定してしまっていて、 若干使い勝手が悪いです。もう少し使い勝手のあるような法則を見つけたいものです。

• 前章：Study 6
• 次章：暫定版あとがき

• Notional InterJection #0
• パズル的マインスイーパ攻略法研究
• Study 7