WEKO3
アイテム
反復深化探索に基く協力詰将棋の解法
https://ipsj.ixsq.nii.ac.jp/records/58622
https://ipsj.ixsq.nii.ac.jp/records/58622c9e305b7-afcf-4f8d-8d72-5f8601982f12
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-GI00005009.pdf (810.8 kB)
|
Copyright (c) 2001 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2001-03-16 | |||||||
| タイトル | ||||||||
| タイトル | 反復深化探索に基く協力詰将棋の解法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A New Algorithm for Solving the Cooperative Tsume - Shogi Based on Iterative - Deepening Search | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学科 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学科 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学科 | ||||||||
| 著者所属(英) | ||||||||
| 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
× Yoshio, Hoshi
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 協力詰将棋（協力詰）は詰将棋のルールを変形したパズルである．協力詰の問題はOR木の探索問題として定式化できる．本論文では探索問題として協力詰をとりあげ，これを解くための新しいアルゴリズムを提案する．探索法として，反復深化法と局面表（トランスポジション表）の技法を組み合わせた深さ優先探索を用いる．局面表に新しい技法を導入し，探索の高速化と記憶領域の節約を図る．本論文のアルゴリズムを用いて作成したプログラムは，協力詰の最長手数問題である49909手詰の「寿限無3」をはじめ，これまでコンピュータでは解けなかったいくつかの難しい問題を解くことができる．また実例によって，新しい技法は局面の数が多い問題で特に効果が大きいことを示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | The cooperative Tsume-shogi, or helpmate, is one of the most popular variants of Tsume-shogi. Solving a helpmate problem can be formulated as an OR-tree searching. We present a new algorithm for solving helpmate. The basic framework of our algorithm consists of depth-first searching, iterative-deepening and a transposition table. Several new techniques 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 | |||||||
| 収録物識別子 | AA11362144 | |||||||
| 書誌情報 |
情報処理学会研究報告ゲーム情報学（GI） 巻 2001, 号 28(2000-GI-005), p. 63-69, 発行日 2001-03-16 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
