Solving Problems with Uncertainty

• Item type: Symposium(1)
• 公開日: 1999-10-15
• タイトル: Solving Problems with Uncertainty
• タイトル / 言語: en
• タイトル: Solving Problems with Uncertainty
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Department of Computer Science, Shizuoka University
• 著者所属: Department of Computer Science, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Shizuoka University
• 著者名: Sakuta, Makoto; Iida, Hiroyuki
• 著者名(英): Sakuta, Makoto; Iida, Hiroyuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper explores the possibility of computing imperfect-information games with focus on its endgame, namely, mating problems with uncertainty. We have chosen the domain of Tsuitate-Shogi, which is a Kriegspiel-like Shogi variant. Our present goal is to make a program that can solve mating problems of Tsuitate-Shogi (Tsuitate-Tsume-Shogi). We have proposed an idea so-called metaposition, by which game-tree search for imperfect-information games turns out to be identical to generic AND/OR-tree search of metapositions. In order to solve Tsuitate-Tsume-Shogi, we introduce a search algorithm that we call double-nested iterative-deepening search. The algorithm has two iterations. The outer iteration is that of the search depth and the inner iteration is that of the allowed count of fouls in a problem. We implemented a solver of Tsuitate-Tsume-Shogi based on the proposed ideas, and experiments using a test set of mating problems were performed. All problems with roughly less than 17 steps in the test set were solved.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper explores the possibility of computing imperfect-information games with focus on its endgame, namely, mating problems with uncertainty. We have chosen the domain of Tsuitate-Shogi, which is a Kriegspiel-like Shogi variant. Our present goal is to make a program that can solve mating problems of Tsuitate-Shogi (Tsuitate-Tsume-Shogi). We have proposed an idea so-called metaposition, by which game-tree search for imperfect-information games turns out to be identical to generic AND/OR-tree search of metapositions. In order to solve Tsuitate-Tsume-Shogi, we introduce a search algorithm that we call double-nested iterative-deepening search. The algorithm has two iterations. The outer iteration is that of the search depth and the inner iteration is that of the allowed count of fouls in a problem. We implemented a solver of Tsuitate-Tsume-Shogi based on the proposed ideas, and experiments using a test set of mating problems were performed. All problems with roughly less than 17 steps in the test set were solved.
• 書誌情報: ゲームプログラミングワークショップ1999論文集; 巻 1999, 号 14, p. 145-152, 発行日 1999-10-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会