マインスイーパをワンクリックでクリアできる確率を検証するプログラムの構築

本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年以上が掛かるため、一定数の検証を行った上で近似確率を求める方法を採用する。

クリアが不可能となる地雷配置について

次の条件を満たした場合、ワンクリックでのクリアは不可能となる。

条件その１：外側から 2 マス目に地雷があり、かつ、その隣の端のマスに地雷が無い場合、クリア不可能

左図のように、一番外側のマスから1マス内側に地雷があり、かつ、外側のマスに地雷が無い場合はクリアできない。逆に、右図のように、一番外側のマスから1マス内側に地雷があるが、外側のマスにも地雷がある場合はクリアの可能性が残される。

条件その２：並んだ 3 マスについて、地雷マス、安全マス、地雷マスという並びがあればクリア不可

縦方向、横方向のいずれでも適用される。

条件その３：並んだ４マスについて、地雷マス、安全マス、安全マス、地雷マスという並びがあればクリア不可

第二条件と同じく、縦方向でも適用される。

以上の条件を満たした時点で検証をスキップするプログラムを構築することで、従来のプログラムよりも処理速度が向上する。
なお、第四条件以降については、第三条件までで十分カバーでき、かつ、プログラムの構築が複雑になるため、ここでは省略する。

検証結果

以上の条件を満たした時点で処理をスキップするプログラムを作成し、約1か月間プログラムを回した結果が以下のとおり。

countにあるように、約5億5千万回の検証を行うことができた。

参考記事：マインスイーパをワンクリックでクリアできる確率は？【Windows 7・Vista】