次回 >>（最終回のため、なし）
はじめに
今度こそ某有名パズルゲームを解く話です。
いよいよ明かされる某有名パズルゲームの正体とは…
ズバリ、マインスイーパーです！！！
まあ、半年間ずっと𝕏(旧Twitter)でマインスイーパーソルバーの話をポスト(旧ツイート)してたので、何も隠せてないのですが…
この記事でやること
- マインスイーパーをZDDで解く方法のざっくり解説
※本記事において、式番号をつけた等式は全てZDDの新たな演算として導入したものになります。詳細な説明は省きますので、詳しい実装を知りたい方はGitHubを参照してください。
マインスイーパーに関する諸定義
説明に使う用語
- 盤面上の開示された数字をヒント数字と呼ぶ。
- 爆弾がないと確定したマスにつける目印を旗と呼ぶ。
- ヒント数字も旗もないマスを未開放マスと呼ぶ。
- 未開放マスのうち、8方向の隣接したマスにヒント数字が1つ以上存在するマスを隣接マスと呼び、それ以外の未開放マスを非隣接マスと呼ぶ。
細かい設定
- 爆弾総数の情報はプレイヤーに開示されているものとします。
マインスイーパーのZDDによる解法
ZDDによる爆弾配置の表現
隣接マスを台集合とし、条件を満たすような隣接マス内の各爆弾配置に対して、爆弾のあるマスの集合を組合せ集合とします。以下、特に断りのない限り台集合を 、爆弾配置を列挙したZDDを
と表記します。
例えば、次の盤面（盤面1）では となります。さらに、この時点でマス
に爆弾がないこととマス
に爆弾があることが確定します。
より一般的に書くと、に対して
\begin{equation}\label{1} \mathcal{P}.\text{items}() := \bigcup_{P \in \mathcal{P}} P \tag{1} \end{equation}
\begin{equation}\label{2} \mathcal{P}.\text{flags}() := \bigcap_{P \in \mathcal{P}} P \tag{2} \end{equation}
とおくと
- 爆弾がないと確定する隣接マスの集合：
\begin{equation} U \setminus \mathcal{P}.\text{items}() \end{equation}
- 爆弾があると確定する隣接マスの集合：
\begin{equation} \mathcal{P}.\text{flags}() \end{equation}
と表せます。よって、 を作ることさえできればマインスイーパーを解き進めることができそうですね。
式 \ref{1}、\ref{2} はメモ化再帰により実装できます。
ここで、返り値の集合を表すデータ構造として前回の記事で導入した共有リストを利用すれば、メモリの消費量を少し抑えられると期待できます*1。
新たな隣接マスの追加
マスを開くと、非隣接マスの一部が隣接マスに変化するため、それらを台集合に追加する操作が必要になります。
そこで、暫定のZDDとして、 の根に、新たなマスをラベルに持つ節点の0-枝と1-枝を突き刺します。こうすれば、「このマスには爆弾があってもなくてもよい」ということを暫定的に表現できますね。
ただし、ZDDでは節点がアイテムの添え字に対してトポロジカル順序を満たす必要があるため、このマスの添え字は（これまでに付した添え字の最小値）- 1 とします。
そして、この操作で得られた暫定のZDDに対し、新たなヒント数字と爆弾総数による条件を改めて適用することで、正しいZDDを構築することができます。
ここからは、それらに対応したZDDの新たな演算を2つ導入します。
ヒント数字を適用する演算
に対して
\begin{equation} \mathcal{P}.\text{hint}(E, h) := \{P \in \mathcal{P} \mathrel{|} |P \cap E| = h\} \tag{3} \end{equation}
と定義します。
ここで、 をヒント数字、
をヒント数字が影響する隣接マスの集合とすれば、暫定のZDD
からヒント数字の条件を満たす組合せ集合を抜き出す演算になりますね。
実はこの演算、メモ化再帰で処理出来ちゃいます。びっくり。
引数の はまさに共有リストの出番ですね。
爆弾総数を適用する演算
に対して
\begin{equation} \label{4} \mathcal{P}.\text{limit}(b, m) := \{P \in \mathcal{P} \mathrel{|} 0 \le b-|P| \le m\} \tag{4} \end{equation}
と定義します。
ここで、 を爆弾総数、
を非隣接マスの個数とすれば、暫定のZDD
から爆弾総数の条件を満たす組合せ集合を抜き出す演算になりますね。
この演算もメモ化再帰で処理出来ちゃいます。やったぜ。
ここまでに見た2つの演算hint, limitを適用することで、暫定のZDDから正しいZDDを得ることができます。
爆弾総数のもう一つの使い方
次の盤面（盤面2）で、爆弾がないと確定するマスはどこでしょう？
（しばらくシンキングタイム用の空白）
…少し考えてもらえればわかると思いますが、右端の列の3マスには爆弾がないと確定します。
より一般的には、爆弾総数を 、非隣接マスの個数を
としたとき、非隣接マスに爆弾がないと確定することと以下は同値です：
\begin{equation} \forall P \in \mathcal{P}; b-|P| = 0 \end{equation}
この判定は式 \ref{4} のソースコードをちょちょいと弄ればできます*2。
危険度の計算
爆弾がないと確定するマスがない場合は、危険度（そのマスに爆弾があるような爆弾配置の総数）が最も低いマスを開くことにします。
暇な人は、次の盤面（盤面3）で実際に数えてみるとよいでしょう。シンプルな盤面なのでまだマシですが、それでも人力でやるにはうんざりする作業であると実感できるかと思います。
この計算を、ZDDを使ってうまいことやります。
隣接マスの危険度
:=
のうち、隣接マス
が含まれるサイズが
の組合せ集合の個数
と定義します。組合せ集合はZDDの根から1-葉までのパスに対応しているので、競プロerならお馴染みのDAG上のトップダウン、ボトムアップ2方向のDPで求められますね。
サイズが の組合せ集合（= 爆弾が
個あるような隣接マス内の爆弾配置）に対しては、非隣接マス内の爆弾配置の総数
（
）による重みがかかるので、非隣接マス
の危険度は次で求められます：
\begin{equation} \sum^{b}_{k=1} \text{dp}_{Total}[e][k] \times \binom{m}{b-k} \end{equation}
非隣接マスの危険度
:=
のうち、サイズが
の組合せ集合の個数*3
とします。どの非隣接マスについても、危険度の計算式は次の通りです：
\begin{equation} \sum^{b-1}_{k=0} \text{dp}[k] \times \binom{m - 1}{b - k - 1} \end{equation}
旗を立てる
爆弾があると確定したマスについては、盤面上に旗を立てて爆弾総数を1減らすことで対応します。また、ヒント数字は周囲の旗の個数分値を減らして処理するようにします。旗を立てたことで隣接マスの定義から外れるため台集合から取り除く必要がありますが、これはonset演算で処理できます。
この操作は行わなくても理論上は解くことができますが、持っているZDDの節点数を大きく減らせるため、解答速度がかなり速くなります。
不要節点の削除
ZDDや共有リストはハッシュテーブル上に永続的に節点を保存するため、マインスイーパーを解き進めていくと、爆弾の有無が確定したマスの節点やその祖先の節点がどんどん増えていきます。これらは今後共有されることのない不要な節点なので、削除してしまって問題ないはずです。
そこで、逆辺を追加し、ラベルごとに節点を管理することで、開くor旗を立てると同時に、節点の削除を行えるようにしました*4。
不要節点の削除は、盤面が大きければ大きいほど効果が発揮されます。
全体フローチャート
実験結果
盤面サイズと爆弾総数割合ごとに50戦し、勝数と解答時間を集計しました。
- 実装言語: Python 3.11.4 (tags/v3.11.4:d2340ef, Jun 7 2023, 05:45:37) [MSC v.1934 64 bit (AMD64)] on win32
- OS: Windows11
- CPU: Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz 2.30 GHz
- メモリ: 8GB
勝数
|
20×20 |
40×40 |
60×60 |
80×80 |
|
|
10% |
47 |
47 |
49 |
46 |
|
20% |
36 |
17 |
13 |
8 |
解答時間
「勝った試合のみ」と「全試合」それぞれで解答時間の最小値、中央値、最大値を記載。（単位: sec）
|
|
|
20×20 |
40×40 |
60×60 |
80×80 |
||||
|
|
|
勝 |
全 |
勝 |
全 |
勝 |
全 |
勝 |
全 |
|
10% |
最小 |
0.012 |
0.012 |
0.064 |
0.064 |
0.156 |
0.156 |
0.351 |
0.351 |
|
中央 |
0.016 |
0.016 |
0.076 |
0.076 |
0.191 |
0.191 |
0.424 |
0.424 |
|
|
最大 |
0.042 |
0.042 |
0.110 |
0.110 |
0.290 |
0.290 |
0.757 |
0.757 |
|
|
20% |
最小 |
0.020 |
0.002 |
0.139 |
0.004 |
0.858 |
0.005 |
3.357 |
0.006 |
|
中央 |
0.038 |
0.035 |
0.246 |
0.243 |
1.396 |
1.400 |
7.947 |
5.275 |
|
|
最大 |
0.128 |
0.128 |
0.707 |
1.121 |
17.471 |
23.505 |
38.111 |
74.303 |
|
ちなみに：『Microsoft Minesweeper』の「超上級」は 16×30, 爆弾総数99 なので、この表での 20×20, 20% に相当。
余談
恐らく私の大学最後のブログ執筆になるので、学部4年の思い出の記録として研究の背景をまったりと書きました。
研究テーマを決めたきっかけの話
夏休みに入る直前くらいのこと。友人とパズルゲームの話をしていて、自分もなんか買ってみるかーとSteamを漁ってみたらこんなの↓を見つけました。
マインスイーパーは昔から好きでよく遊んでいたので、面白そうだと思い即購入。
プレイしてみると、Windows標準搭載のマインスイーパーとは決定的に違う点がありました。
なんと、全ての問題が論理的に完全解答できるように作られており、開示された情報からは爆弾の有無が特定できないマスに対して操作（開く or 旗を立てる）をすると、自動的にそれを満たさない解を生成し、その時点でゲームを終了させる機能が実装されていたのです。
これにそこそこ感動し、おそらく内蔵されているのであろうマインスイーパーのソルバーを、自分でも作ってみたいと思いました。
ZDDについて勉強していると、パズルを解くのに使えるという情報をいくつか目にします。そこで、これマインスイーパーも解けるんじゃね…？と軽く考察を進めてみると、なんか解けちゃいました。
というわけで、夏休みの間ひたすら実装して、夏休み明けの初回ゼミで成果を発表したら、教授っちから学会で発表しようと提案されたという流れです。貴重な経験でした。
ちなみに 参考文献[1] はソルバーを作ってから見つけました。（アホ）
良い子のみんなは先に先行研究を調べてから卒研に着手しましょう。
参考文献
- 鈴木 浩史, 孫 浩, 湊 真一. BDD/ZDDを用いたマインスイーパーの爆弾配置パタンの列挙. The 30th Annual Conference of the Japanese Society for Artificial Intelligence, 1D5-OS-02b-3in2, 2016.
- 湊 真一. Zero-suppressed BDDs for Set Manipulation in Combinational Problems. 30th ACM/IEEE Design Automation Conference,1993.
- 3. 湊 真一. Zero-suppressed BDDs and their applications. Int. J. Softw. Tools Technol. Transf. (STTT), vol. 3, no. 2, pp. 156-170, Springer 2001
次回 >>（最終回のため、なし）
