マインスイーパーの熱力学

266日前原文(oscarcunningham.com)

概要

Minesweeperで 安全なセル を選ぶ確率計算の重要性
境界付近 の地雷配置パターンごとに発生確率が異なる事実
ボルツマン分布 との類似性と“マイン温度”の導出
近似式の精度と、実際の比率との比較
統計力学的な視点からMinesweeperを考察

Minesweeperにおける安全セルの確率計算

Minesweeperでは、 初手以降 に「どのセルが安全か」判断が難しい局面が発生
境界付近で考えられる 地雷配置パターン が複数存在
各パターンの地雷数が異なるため、 全てのパターンが等確率ではない
例：ある局面で地雷が5個、6個、7個のパターンが存在
- 各パターンの残りセルへの地雷配置通り数
  - 5個: $\binom{444}{89}$
  - 6個: $\binom{444}{88}$
  - 7個: $\binom{444}{87}$
したがって、 少ない地雷数のパターンが圧倒的に起こりやすい
各セルの安全確率は、 パターンごとの発生確率で重み付け して計算
これにより、 最適なクリック候補 を選定可能

ボルツマン分布との類似性と“マイン温度”

統計力学のボルツマン分布 では、系の状態（エネルギー$E$）の出現確率が$\exp(-E/kT)$に比例
Minesweeperでは、境界領域を「小さな系」、残りのセルを「マインバス」とみなす
境界付近の地雷数$m$が“エネルギー”に相当
パターンの発生確率は$\binom{C}{M-m}$（$C$は残りセル数、$M$は残り地雷数）
近似的に$\binom{C}{M-m}\propto \exp(-m/T)$の形にできる
- $T$は マイン温度 で、$T=1/\log(M/(C-M))$と定義
この近似により、 ボルツマン分布と同様の計算手法 が適用可能

近似式の精度と実際の比率

近似式による発生確率の比率は、実際の計算値と オーダーは一致 するが完全一致はしない
- 例：5個地雷パターンと7個地雷パターンの比率
  - 近似式：$1/(0.269)^2 \approx 13.86$
  - 実際：$16.2$
粒子数（地雷数）が非常に多い場合、近似の精度はさらに向上
Minesweeperのような有限サイズの問題では、 近似のズレ も考慮が必要

Minesweeper戦略への応用

安全なセルの選択 には、単純なパターン数の割合だけでなく、 重み付けした確率 を使うべき
統計力学的な考え方を応用することで、 より合理的な意思決定 が可能
Minesweeperの問題設定は、 統計物理の直感や技法 を学ぶ題材としても興味深い

議論と反響

本記事は Hacker News、 Reddit、 Mastodon、 Lemmy でも議論
Minesweeperと統計物理の接点に興味を持つコミュニティの存在

Hackerたちの意見

ちょっと関係ないけど、Dragonsweeperっていうマインスイーパーの面白い拡張版があるんだ。ヒットポイントがあって、「地雷」には攻撃力があるんだよ。これをプレイすることで、マインスイーパーのメカニクスをもっと理解できた。意外と深いゲームだよ。 https://danielben.itch.io/dragonsweeper

└

これ、実は結構面白いゲームだよ。初めて見たときに2時間くらいプレイしちゃった。

└

似たようなゲーム：マモノスイーパー https://duckduckgo.com/?q=mamono+sweeper （マモノは日本語でモンスターのこと）。これはマインスイーパーのRPGバリエーションで、ライフポイントがあってレベルアップして、モンスター（地雷）と戦うんだ。モンスターを倒すと経験値がもらえるし、レベルが高いモンスターと戦うとHPを失うよ。フラッシュゲームで、以前はAndroid版もあったけど、何かの理由でストアから消えちゃった。

「許容範囲」のマインスイーパーのバージョンを作ったんだ。安全だと証明できる選択肢がなかったら、安全な手を出してくれるの。証明できない爆弾じゃないマスを選べば、絶対に爆弾じゃない。普通は、爆弾の数と同じ数のマスを選ばなければ、最初の手は安全なんだ。それをゲーム全体に拡張した感じ。N-1個の爆弾を選べば、最初の手で必ず勝てるよ。

└

ハハ！これはNP完全だよね？実際にはあまり関係ないかもしれないけど、プレイヤーが「許される」かどうかを判断するのに指数時間かかる構成があると思うな。

└

先行技術: https://news.ycombinator.com/item?id=21883875

└

地雷をフラグしたときに、あいまいじゃないタイルを自動でクリアしたいな。隣接するタイルの一つをダブルタップすることでできるかも。

└

サイモン・タサムの Mines は、ゲーム中にあいまいな状態にならないように地雷の位置を生成する別の方法を取ってるよ。 https://www.chiark.greenend.org.uk/~sgtatham/puzzles/doc/min...

└

Windows 7のマインスイーパーは、最初のクリックでこんな感じになると思う。だいたい「いいスタート」って感じになるよね。

└

韓国のインディーゲームで、RPG Maker MVで作られた「どうやって私は異世界で勇者になれるのか、マインスイーパーの初心者レベルすらクリアできないのに?!」っていうゲームがあって、これがこのアイデアを極限まで押し進めてるんだ。残念ながら、韓国語だけでしか遊べないけど。

└

「許容的な」マインスイーパーのバージョン：これってゲームを薄めると思う。時には、確実に知るための情報が足りないこともあるからね。マインスイーパーのような低リスクな状況でこれを体験するのは、人生も時にはそういうもんだって思い出させてくれるし、ただ推測して結果を受け入れなきゃいけないんだよね。

└

今までプレイしたマインスイーパーのどのバージョンも、最初の一手は安全だよ。あなたのバージョンほどではないけど、これが真実じゃないって主張する熱心なプレイヤーと議論したことがあるよ（彼らはただ運が良かっただけなんだと思うけど）。

記事ではボルツマンの公式 exp(-E/kT) について話してる。最近、半導体の文脈で同じ公式を見てて、ボルツマン定数 k は温度が変な単位を使うから必要なんだなって気づいた。温度を度ではなくエネルギーで測ったら、ボルツマン定数は消えちゃう。例えば、室温を25 meV（ミリ電子ボルト）や2444ジュール/モルで表現できるし、そうすると定数は消える。理想気体の法則でも、温度をエネルギーで測れば定数は消えるんだ。つまり、ケルビン度は捨てるべき作り話の単位だよ。（これが本当かどうかは分からないけど、欠陥は見当たらない。）

└

そうだね！単位は自由だよ（いくつかの制約はあるけど）！物理学者は実際にこれをよくやってるよ。 https://en.wikipedia.org/wiki/Natural_units

└

これはどんな単位にも当てはまるよね。多くの物理学者が「c=1に設定する」って言うけど、つまりメートルやフィートは悪い単位で、代わりに身長をcの分数で測るべきってこと？それは不便に感じるな。

└

温度はエネルギーとして測るんじゃなくて、むしろ情報あたりのエネルギー、つまりビットあたりのジュールとして測るべきだと思う。ボルツマン定数は、マクロスケールで便利な数字を得るために、1ジュールを非常に大きなビット数で定義してるんだよね。

└

温度をジュールあたりのビットとして見る: https://arxiv.org/abs/2401.12119

└

中学校でよく出てくる別の例は、角度の測り方だね。ギリシャ人やバビロニア人のように、普通は度で測るけど、18世紀頃からはラジアンが使われ始めた。特に冪級数展開でね。インドでは、歴史的に角度は長さの単位で測られてた（標準化された円のために）。それで、sinのような関数は長さから長さへの関数になってたんだ。

これをBombeみたいな負の爆弾スペースにどう拡張できるかな？ (https://store.steampowered.com/app/2262930/Bombe/)

これらの計算をするボットの勝率は、しないボットと比べてどうなるんだろう？

└

https://mrgris.com/projects/minesweepr/ のボットはこれらの計算をしてて、エキスパートでの勝率は37.8%だよ。もっと単純なボットだとどれくらいの結果が出るのかは分からないけど。

マインスイーパーは確率ゲームだから、解くためには確率的なツールを使うべきだよ。例えば、パーティクルフィルターを使って地雷の分布を近似することができる。新しい情報を得るたびにフィルターを更新して、制約に合った分布だけが残るようにするんだ。地雷の分布の近似ができたら、各スポットが地雷である確率を計算できるし、各アクションの情報利得みたいな統計指標も計算できる。だから、低い地雷確率で最高の情報利得を得るのがいい戦略だね。でも、地雷確率がゼロじゃないときはトレードオフがあるから、先を見越す必要がある。幸い、地雷の分布の近似のおかげで、どんなアクションとその結果もシミュレートできる。クリックしたときにどの数字が表示されるかを予測できるからね。だから、さらに良い戦略は、いくつかのヒューリスティックに基づいて最良の候補ムーブのゲームツリーを展開して、数手後のコスト利得確率を計算することだよ。

└

マインスイーパーはほとんどの場合、決定論的で、考えれば空いてる場所がわかるんだ。でも時々運が悪くて、推測しなきゃいけないこともある。数年前、Racketの「Games」コレクションのマインスイーパーのバージョンを改造して、ボードごとにもっと多くの地雷を配置して、難しいケースを増やしたんだ。（周りに十分なフラグがある場合に自動でマスを開けるトリックを追加したから、簡単なケースは全部解決できて、もっと楽しくなったよ。変更を上流に送ったことはないけど…）ドラゴンスイーパーが好きなんだ（別のコメントで話してるやつ）理由は、確率と情報のトレードオフがもっと明確だから。

面白いことに、マインスイーパーの主な問題は運のゲームだってことだね（だから、記事で話されているアプローチはすごく適切）。論理だけに基づいたマインスイーパーのバリエーションとして、タメッツィを強くおすすめするよ。160の手作りレベルがあって、いくつかはすごく面白い幾何学的配置になってる。私はこのゲームに100時間以上費やしてる。

└

タメツィはすごいよね。描画モードも好きで、Steamオーバーレイに追加して、どのゲームでも使えるようにすべきだと思う。純粋な論理マインスイーパーに興味がある人には、HexCellsシリーズもチェックする価値があるよ。

記事の最初に深刻な数学的誤りがあるよ。著者の数学は、地雷がそのボード状態に達した後に空いているマスに分配される場合を考慮しているけど、これは間違い。これはクラシックなモンティ・ホール問題だね。著者は「残りのドアが2つあるから、賞品がどちらかのドアの後ろにある確率は50/50だ」と言っているのと同じことをしている。これ以降の数字はすべて無効になるよ。

└

同意できないな（俺が作者なんだけど）。違いは、モンティがどのドアの後ろに車があるかを知っていて、わざとそれを避けることで、車の場所に関する情報を与えていることなんだ。一方、マインスイーパーでは、ただ盲目的に状況に遭遇して、推測しなきゃいけないんだよ。毎回モンティがランダムなドアを開けるようなもんだよね。時には車を開けて、ゲームがすぐに終わっちゃうこともあるし。車を開けなかった場合は、残りの2つのドアの間で本当に50/50になるんだ。

最初は「等確率の仮定」ってそんなに悪い近似じゃないと思ってたけど、平均ブライヤースコアが0.217なんだ。思ってたよりずっと悪かった。

ハクソク