著者

大森 瑛智 井上 真郷

雑誌

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

巻号頁・発行日

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

---

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

著者

大森 瑛智 井上 真郷

雑誌

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

巻号頁・発行日

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

---

Minesweeper は一人用のパズルゲームであり,プレイヤーが全ての情報を得られる訳ではないという,不完全情報ゲームである.つまり,地雷が設置されていないと分かる安全なマスが常に存在する訳ではなく,勝利できるか否かは運によるところが大きい.ルールが単純であり,多くの人に親しまれている一方,最適戦略,および達成可能な勝率の上限は未だに分かっていない.これは,地雷の有無を判断するのに,難しい場面では,地雷が設置されていたとして矛盾しない全パターンを列挙する必要がある,つまり NP 完全問題となっていることに由来する.我々は本研究で, 1) 二体探索法により,問題が簡単な場合に高速に安全なマスを発見する方法, 2) 地雷設置可能な全パターンを効率よく列挙し,地雷設置確率を算出する方法, および3) 安全なマスがなく,地雷設置確率が最小のマスが複数ある場合の選択方法,の三つを組み合わせた手法を開発したので提案する.本手法は,16×30 マス,地雷 99 個の標準ゲームで勝率 49.4% を達成できた.Minesweeper is a puzzle game of incomplete information for one person. In this game, mine-free squares are sometimes unknowable from open information, thus, winning is not always guaranteed. The rule of the game is quite simple and many people are familiar with this game. On the other hand, the optimal strategy and the upper limit of the winning rate are not known so far. This is because this game needs the complete enumeration of all possible mine-filled square patterns in some difficult situations, which implies this game is NP-complete and so, indeed, it is. In this research, we developed a novel solver combining following three methods; 1) two-body search method which can find mine-free square quickly in easy situations, 2) the method which can calculate the mine-filled probability efficiently by the complete enumeration, and 3) the selecting method among two or more mine-filled squares having the same smallest mine-filled probability. This solver achieved the winning rate of 49.4% for the standard minefield of 16×30 squares containing 99 mines.