反復深化探索に基づく協力詰将棋の解法

• Item type: Journal(1)
• 公開日: 2002-01-15
• タイトル: 反復深化探索に基づく協力詰将棋の解法
• タイトル / 言語: en
• タイトル: A New Algorithm for Solving the Cooperative Tsume-Shogi Based on Iterative-deepening Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ゲームプログラム
• 著者所属: 電気通信大学情報工学科
• 著者所属: 電気通信大学情報工学科
• 著者所属: 電気通信大学情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro-Communications
• 著者名: 星, 由雄; 野下浩平; 柳井, 啓司
• 著者名(英): Yoshio, Hoshi; Kohei, Noshita; Keiji, Yanai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 協力詰将棋（協力詰）は詰将棋のルールを変形したパズルである．協力詰の問題はOR木の探索問題として定式化できる．本論文では探索問題として協力詰をとりあげ，これを解くための新しいアルゴリズムを提案する．探索法として，反復深化法と局面表（トランスポジション表）の技法を組み合わせた深さ優先探索を用いる．局面表に新しい技法を導入し，探索の高速化と記憶領域の節約を図る．本論文のアルゴリズムを用いて作成したプログラムは，協力詰の最長手数問題である49909手詰の「寿限無3」をはじめ，これまでコンピュータでは解けなかったいくつかの難しい問題を解くことができる．また実例によって，新しい技法は局面の数が多い問題で特に効果が大きいことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The cooperative Tsume-shogi, or Shogi-helpmate, is one of the most popular variants of Tsume-shogi. Solving a Shogi-helpmate problem can be formulated as an OR-tree searching. We present a new algorithm for solving Shogi-helpmate. The basic framework of our algorithm consists of depth-first searching, iterative-deepening and a transposition table. Several new techiniques for handling information in the transposition table are introduced, by which we achieve considerable memory-savings as well as speed-ups. Our program has solved the longest-step problem named Jugemu 3 with 49909 steps, as well as several hard problems, all of which have been intractable by other previous programs. By experiments we show that our techniques are effective particularly for hard problems which need a large transposition table.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 43, 号 1, p. 11-19, 発行日 2002-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764