fixedpoint.jp


手掛りのないマインスイーパで生き残る確率と離散ワイブル分布 (2020-07-05)

この記事では、手掛りがないマインスイーパで生き残る確率の極限として離散ワイブル分布が現れることを述べます。

マインスイーパというゲームでは、中身の分からないブロックが並ぶ平面が与えられ、開けたブロックに示される数字のヒントを手掛りにして、隠れている爆弾のブロック以外を開けていきます。ここでは、与えられる平面が縦に\(h\)個、横に\(w\)個ブロックが並んでおり、そのうちのランダムに選ばれた\(n (\gt 0)\)個に爆弾が配置されているとします。さらに、ルールを変更して、数字という手掛りが一切出ないことにします。そうなると、このゲームは最早ロジックパズルでは無くなり純粋に確率的なものとなります。各ブロックに同様の確からしさで爆弾が隠れていると考えるので、最初に選んだブロックで即爆弾に当たってしまう確率は\(p := \frac{n}{h w}\)ということになります。

このとき、幸運にも全ての爆弾を回避しつつ爆弾のないブロックを全部開けてゲームをクリアする確率は\[\frac{n! (h w - n)!}{(h w)!}\]になります。

では、\(x+1\)回目までに開けたブロックのいずれかで爆弾に当たってしまいゲームオーバーになる確率\(q_1(x)\)はどうなるでしょうか?先ほどの通り、\(q_1(0) = p\)です。\(w\)や\(h\)が十分大きいとすると、\(q_1(1) = q_1(0) + (1-p)p\)、\(q_1(2) = q_1(1) + (1-p)^2 p\)、\(q_1(3) = q_1(2) + (1-p)^3 p\)、...となります。即ち、\(w, h \rightarrow \infty\)のとき\(p \gt 0\)なら、\(q_1(x)\)が幾何分布の累積分布関数に近似されることが分かります。これはまた、shape parameter \(\beta = 1\)の離散ワイブル分布とも言えます。そのscale parameter \(\alpha\)は\[\alpha = - \frac{1}{\ln{(1-p)}}\]です。

では、平面上の縦横\(x+1\)個正方形状に並んだブロックを全部開けたときに、爆弾に当たってゲームオーバーになってしまう確率\(q_2(x)\)はどうでしょうか?\(w\)や\(h\)が十分大きいとすると、\(q_2(x) = q_1(x^2 + 2x)\)となります。したがって、\(w, h \rightarrow \infty\)のとき\(p \gt 0\)なら、\(q_2(x)\)はshape parameter \(\beta = 2\)の離散ワイブル分布の累積分布関数に近似されます。そのscale parameter \(\alpha\)は\[\alpha = \sqrt{- \frac{1}{\ln{(1-p)}}}\]です。


© 2006-2020 fixedpoint.jp