新規節点で固定深さの探索を行うdf-pnの拡張

• Item type: Journal(1)
• 公開日: 2010-11-15
• タイトル: 新規節点で固定深さの探索を行うdf-pnの拡張
• タイトル / 言語: en
• タイトル: Enhancement of Df-pn with Fixed-depth Search at Frontier Nodes
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：ゲームプログラミング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属: 東京大学情報基盤センター
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属: 放送大学
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Information Technology Center, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of the Air
• 著者名: 金子, 知適; 田中, 哲朗; 山口, 和紀; 川合, 慧
• 著者名(英): Tomoyuki, Kaneko; Tetsuro, Tanaka; Kazunori, Yamaguchi; Satoru, Kawai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿ではdf-pn探索の拡張として，末端節点での浅い探索木の活用を提案し，実際に効率的に詰を発見できることを示す．AND/OR木の探索において，df-pnは探索節点数の観点で効率が良く，固定深さの探索は節点展開速度に優れている．そこで末端で固定深さの探索を行い，詰む場合はその情報を，詰まない場合は固定深さの探索が展開した探索木の証明数と反証数を計算して，df-pnで活用する．実験の結果，棋譜に表れる実戦の詰み局面に対して，平均探索時間が標準的なdf-pnの約1/3，使用した局面表の節点の数は平均約1/5という大きな効率の向上を実現した．さらに，大規模な詰将棋問題において各種の拡張を組み込んだdf-pn+との比較においても，所要時間で約2/3，使用した局面表の節点数で半分強という効率の向上を実現した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents an enhancement on df-pn for AND/OR tree search, by utilization of fixed-depth look ahead. In this enhancement, a shallow fixed-depth search is performed to find out a short proof at each new frontier node visited in the df-pn search. This combination utilizes both the efficiency of df-pn regarding to the number of nodes needed to find a proof and the efficiency of fixed-depth searches in execution time for node expansion. Moreover, even when checkmate is not found, the result of fixed-depth search yields a good estimation of future proof and disproof numbers at the node. Our experiments on checkmate search in shogi showed that the presented combination solved problems with about 1/3 in execution time and about 1/5 in memory usage, compared to the df-pn. Also for large problems, it achieved efficiency of about 2/3 in execution time and about 1/2 in memory usage, compared to df-pn+ with state-of-the-art techniques.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 51, 号 11, p. 2040-2047, 発行日 2010-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764