問題解決における不確定性パラダイムの提案と適用

• Item type: SIG Technical Reports(1)
• 公開日: 2000-05-31
• タイトル: 問題解決における不確定性パラダイムの提案と適用
• タイトル / 言語: en
• タイトル: Introducing and Applying Uncertainty Paradigm for Problem Solving
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 静岡大学情報学部
• 著者所属: 静岡大学情報学部
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Shizuoka University
• 著者名: 作田, 誠; 飯田, 弘之
• 著者名(英): Makoto, Sakuta; Hiroyuki, Iida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 不確定性のある問題を解決するための新しいパラダイム「不確定性パラダイム」を提案する。この下では任意の不確定性のある問題を決定論的に解決することが純粋なAND/ORグラフ（または木）の探索に帰着される。この探索を不確定性パラダイム探索(UPS)と名づける。通常のゲーム木は節点として局面、枝として指手を持つが、このパラダイム下では節点は可能な局面の重ね合せであるメタ局面、枝は可能な指手の重ね合せであるメタ指手になる。理論的にはUPSはあらゆる不完全情報のパズル・ゲームの終盤を決定論的に解決することに適用可能である。しかし、多くの問題領域において実際に適用するためには厳しい限界がある。また、二人ゲームを題材としたパズルへの適用例として「ついたて詰将棋」を選び、このパラダイム下で問題を探索し解決するプログラムを作成した。さらに、ついたて詰将棋についてメタ局面のコード化を行い、transposition tableを利用した全幅反復深化探索および長井のPDSを不確定性パラダイム探索に特化させたUPDS (Uncertainty Paradigm PDS)を実装し良い結果を得た。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We introduced a novel paradigm for the problems with uncertainty, Uncertainty Paradigm. Under this paradigm, deterministic solving of such a problem is resolved into a plain AND/OR tree search for multi-person games as well as for single-agent puzzles. The search under this paradigm is generally denoted as the Uncertainty Paradigm Search (UPS). Instead using a position as a node of game tree, a metaposition, which is a hybrid of possible positions, is used as the node of game tree under this paradigm. Similarly, a metamove, which is a hybrid of possible moves, is used as an arc between the parent metaposition and the child metaposition. Theoretically, UPS is applicable for solving any puzzles or endgames with imperfect information, though there is a severe restriction of practical application for many domains. As an example of application of this paradigm to the adversary-agent puzzles, we selected the domain of Tsuitate-Tsume-Shogi (mating problems of Kriegspiel-like variant of Shogi). We implemented a solver of Tsuitate-Tsume-Shogi under paradigm, and experiments using a test set of mating problems were performed. We have implemented the encoding methods of a metaposition and exploited the transposition table with UPS. A program using the full-width depth-first iterative deepening as a search algorithm, and another program using UPDS (Uncertainty Paradigm PDS), which is a specialized version of PDS for UPS, have been tested. Most problems have been solved by one program or by both programs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 情報処理学会研究報告ゲーム情報学（GI）; 巻 2000, 号 52(2000-GI-003), p. 49-56, 発行日 2000-05-31
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会