WEKO3
-
RootNode
アイテム
可能パターン完全探索によるminesweeperのsolver生成
https://ipsj.ixsq.nii.ac.jp/records/82814
https://ipsj.ixsq.nii.ac.jp/records/8281404dce652-9207-4f7c-9007-199817c54d9a
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-GI12028005.pdf (659.6 kB)
|
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-07-06 | |||||||
| タイトル | ||||||||
| タイトル | 可能パターン完全探索によるminesweeperのsolver生成 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Minesweeper Solver with Complete Enumeration of All Possible Patterns | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 早稲田大学大学院先進理工学研究科電気・情報生命専攻 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学大学院先進理工学研究科電気・情報生命専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Dept. of Electrical Engineering and Bioscience, Graduate School of Advanced Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Dept. of Electrical Engineering and Bioscience, Graduate School of Advanced Science and Engineering, Waseda University | ||||||||
| 著者名 |
大森, 瑛智
井上, 真郷
× 大森, 瑛智 井上, 真郷
|
|||||||
| 著者名(英) |
Eichi, Omori
Masato, Inoue
× Eichi, Omori Masato, Inoue
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Minesweeper は一人用のパズルゲームであり，プレイヤーが全ての情報を得られる訳ではないという，不完全情報ゲームである．つまり，地雷が設置されていないと分かる安全なマスが常に存在する訳ではなく，勝利できるか否かは運によるところが大きい．ルールが単純であり，多くの人に親しまれている一方，最適戦略，および達成可能な勝率の上限は未だに分かっていない．これは，地雷の有無を判断するのに，難しい場面では，地雷が設置されていたとして矛盾しない全パターンを列挙する必要がある，つまり NP 完全問題となっていることに由来する．我々は本研究で， 1) 二体探索法により，問題が簡単な場合に高速に安全なマスを発見する方法， 2) 地雷設置可能な全パターンを効率よく列挙し，地雷設置確率を算出する方法， および3) 安全なマスがなく，地雷設置確率が最小のマスが複数ある場合の選択方法，の三つを組み合わせた手法を開発したので提案する．本手法は，16×30 マス，地雷 99 個の標準ゲームで勝率 49.4% を達成できた． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11362144 | |||||||
| 書誌情報 |
研究報告ゲーム情報学（GI） 巻 2012-GI-28, 号 5, p. 1-6, 発行日 2012-07-06 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
