著者

大森 瑛智 井上 真郷

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2012-GI-28, no.5, pp.1-6, 2012-07-06

---

Minesweeper は一人用のパズルゲームであり,プレイヤーが全ての情報を得られる訳ではないという,不完全情報ゲームである.つまり,地雷が設置されていないと分かる安全なマスが常に存在する訳ではなく,勝利できるか否かは運によるところが大きい.ルールが単純であり,多くの人に親しまれている一方,最適戦略,および達成可能な勝率の上限は未だに分かっていない.これは,地雷の有無を判断するのに,難しい場面では,地雷が設置されていたとして矛盾しない全パターンを列挙する必要がある,つまり NP 完全問題となっていることに由来する.我々は本研究で, 1) 二体探索法により,問題が簡単な場合に高速に安全なマスを発見する方法, 2) 地雷設置可能な全パターンを効率よく列挙し,地雷設置確率を算出する方法, および3) 安全なマスがなく,地雷設置確率が最小のマスが複数ある場合の選択方法,の三つを組み合わせた手法を開発したので提案する.本手法は,16×30 マス,地雷 99 個の標準ゲームで勝率 49.4% を達成できた.