不確定性を持つ問題を解くためのAND/OR木探索 －衝立詰将棋を題材として

• Item type: Journal(1)
• 公開日: 2002-01-15
• タイトル: 不確定性を持つ問題を解くためのAND/OR木探索 －衝立詰将棋を題材として
• タイトル / 言語: en
• タイトル: AND/OR-tree Search for Solving Problems with Uncertainty - A Case Study Using Screen-shogi Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ゲームプログラム
• 著者所属: 静岡大学大学院理工学研究科
• 著者所属: 静岡大学情報学部
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Faculty of Information, Shizuoka University
• 著者名: 作田, 誠; 飯田, 弘之
• 著者名(英): Makoto, Sakuta; Hiroyuki, Iida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 不完全情報2人ゲームである衝立将棋の詰め問題を題材として，不確定性を持つ問題をAND/OR木探索として決定論的に解く手法を導入する．このAND/OR木は詰将棋など通常の完全情報2人ゲーム問題において生成されるものに比べてより一般化されており，節点はそれぞれ不確定性を持つ．探索アルゴリズムとして，局面表を活用した全幅深さ優先反復深化探索（ID），および証明数探索の深さ優先版の一種であるPDSを実装し動作を調べた．またPDSを不確定性のあるAND/OR木の探索に特化させたUPDSを開発しパラメータを変化させて動作を調べた．さらに，UPDSにおいて実行時にパラメータを順次変化させて解けるまで繰り返し探索を行うdpUPDS，および，UPDS，IDにおいて不確定性の探索閾値を小さな値から順次増加させて解けるまで繰り返し探索を行うuidUPDS，uidIDというバリエーションを考案・実装し動作を調べた．dpUPDS，uidUPDS，uidIDは解答能力が高く，特にuidUPDSはすべての問題を解いた．しかし，確実に最適解を得る効率の良い探索法は課題として残る．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper explores a deterministic approach to solving problems with uncertainty, using Screen-shogi problems, which are the mating problems of Kriegspiel-like Shogi variant.Our programs resolve a search space into an AND/OR tree and solve a problem by searching the tree.The AND/OR tree, each of which node has an uncertainty, is more generic than that in solving a problem of a two-person complete-information game such as Tsume-Shogi.The search algorithms are implemented using a full-width depth-first iterative deepening (ID), and using PDS, which is one of the depth-first variants of the proof-number search.In addition, UPDS, which is a specialized version of PDS for an AND/OR tree with uncertainty, is proposed and examined with changing the parameters.Moreover, some search variations are developed and examined.One variation is dpUPDS, which performs iteration with changing the parameters of UPDS.The others are uidUPDS based on UPDS and uidID based on ID.Both variations perform iteration with increasing the search threshold of uncertainty.The solving abilities of dpUPDS, uidUPDS and uidID are high.Especially, the uidUPDS program has solved all problems.However, an efficient algorithm that always finds an optimal solution even for a hard problem still needs to be investigated.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 43, 号 1, p. 1-10, 発行日 2002-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764