![見出し画像](https://assets.st-note.com/production/uploads/images/121806299/rectangle_large_type_2_fb380a37f4cc7ae07e07b3a208605963.png?width=1200)
マインスイーパをワンクリックでクリアできる確率を検証するプログラムの構築
本noteは、Luck Game RTA 2023で走った、マインスイーパーオンライン(カテゴリ:one click)におけるクリア確率について記載したものです。
確率の検証を行う2種類の方法
クリア確率の検証にあたっては、全通りの検証を行う方法と、一定数検証を行った上で近似確率を求める方法の2種類がある。
全通りの検証を行う場合、
nCr=nPr/r!
=(77×76×75×74×73×72×71×70×69×68) / 10!
=1,096,993,404,430通り
(1兆969億9340万4430通り)
と、1兆通り以上を検証する必要がある。私のプログラム技術ではこの検証には700年以上が掛かるため、一定数の検証を行った上で近似確率を求める方法を採用する。
クリアが不可能となる地雷配置について
次の条件を満たした場合、ワンクリックでのクリアは不可能となる。
条件その1:外側から 2 マス目に地雷があり、かつ、その隣の端のマスに地雷が無い場合、クリア不可能
![](https://assets.st-note.com/img/1700055665935-THdsWVuNUF.png?width=1200)
条件その2:並んだ 3 マスについて、地雷マス、安全マス、地雷マスという並びがあればクリア不可
![](https://assets.st-note.com/img/1700055802870-LxXej1hEsP.png)
条件その3:並んだ4マスについて、地雷マス、安全マス、安全マス、地雷マスという並びがあればクリア不可
![](https://assets.st-note.com/img/1700055890646-oBV1m1mp0Q.png)
以上の条件を満たした時点で検証をスキップするプログラムを構築することで、従来のプログラムよりも処理速度が向上する。
なお、第四条件以降については、第三条件までで十分カバーでき、かつ、プログラムの構築が複雑になるため、ここでは省略する。
検証結果
以上の条件を満たした時点で処理をスキップするプログラムを作成し、約1か月間プログラムを回した結果が以下のとおり。
![](https://assets.st-note.com/img/1700056133852-tvOzSOAuaW.png?width=1200)
countにあるように、約5億5千万回の検証を行うことができた。
参考記事:マインスイーパをワンクリックでクリアできる確率は?【Windows 7・Vista】
この記事が気に入ったらサポートをしてみませんか?