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


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

図1
232323232323232350
232323232323232350
232323232313444413
2323232323
2323232350
2350235050
2350
235077
237723

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

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

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

均等にならない原因

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

図2
     **
 ■■■■*4
 *32**3
 *2123*
図3
|    
|  323
|  12
|■■■22
|2*4*2
|224*2

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

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

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

ちゃんと数学的に処理すれば、nCrnCr-1を、 r<n/2のときに比べてどうなるかを計算すればわかります。
nCr:nCr-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ですから、nCrの方がnCr-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つとかいう時は、この方法に頼っていてはかなり危険度が高いと言えるでしょう。

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

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

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

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

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

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

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

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

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

表1:AIC TABLE@「最少0」
説明変数 カテゴリー数 AIC
確率 11 -247.98
非隣接領域確率差 8 -214.85
均一確率差 9 -213.50
数字非隣接領域以下 2 -195.14
均一確率未満 2 -183.44
均一確率以下 2 -166.91
最小値 2 -112.19
数字非隣接領域未満 2 -79.82

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

表2:確率 / 最少パターン クロス表
確率 / 最少パターン 配置パターンあり 配置パターンなし
0.00〜0.18 1 68 69
0.19〜0.20 2 22 24
0.21〜0.22 9 0 9
0.23〜0.29 9 15 24
0.30〜0.30 2 0 2
0.31〜0.32 0 5 5
0.33〜0.36 41 8 49
0.37〜0.45 10 14 24
0.46〜0.60 67 5 72
0.61〜0.62 1 1 2
0.62〜0.97 56 1 57
198 139 337
表3:非隣接領域確率差 / 最少パターン クロス表
確率 / 最少パターン 配置パターンあり 配置パターンなし
-0.23〜-0.06 3 46 49
-0.05〜-0.03 4 9 13
-0.02〜0 5 52 57
0.01〜0.06 19 11 30
0.07〜0.15 28 2 30
0.16〜0.21 18 8 26
0.22〜0.42 66 10 76
0.43〜0.92 55 1 56
198 139 337
表4:非隣接領域以下 / 最少パターン クロス表
非隣接領域以下 / 最少パターン 配置パターンあり 配置パターンなし
より大きい 186 32 218
以下 12 107 119
198 139 337

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

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

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

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

コンパートメント

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

図4
┌───────────
|        32
|        **
|     ■■■■*4
|     *32**3
|    ■*2123*
| ■■■320011
| ■323*42111
| ■12***11*
|■■■22243212
|2*4*212*101
|224*22*3101

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

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

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

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

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

図5−1
     **
  ?  *4
 *32**3
 *2123*
図5−2
     **
   ? *4
 *32**3
 *2123*
図5−3
     **
 ?  ?*4
 *32**3
 *2123*

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

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

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

表5:AIC TABLE
説明変数 カテゴリー数 AIC
非隣接領域確率差 2 -73.93
確率 3 -71.25
数字非隣接領域以下 2 -69.14
表6:非隣接領域確率差 / 最少パターン クロス表
非隣接領域確率差 / 最少パターン 配置パターンあり 配置パターンなし
-0.1〜0 0 47 47
0.17〜0.75 25 2 27
25 49 74
表7:確率 / 最少パターン クロス表
確率 / 最少パターン 配置パターンあり 配置パターンなし
0.00〜0.38 0 46 46
0.43〜0.48 3 2 5
0.52〜0.9 22 1 23
25 49 74

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