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

情報処理学会 被引用文献1件

書誌事項

タイトル別名
  • Enhancement of Df-pn with Fixed-depth Search at Frontier Nodes

この論文をさがす

説明

本稿ではdf-pn探索の拡張として，末端節点での浅い探索木の活用を提案し，実際に効率的に詰を発見できることを示す．AND/OR木の探索において，df-pnは探索節点数の観点で効率が良く，固定深さの探索は節点展開速度に優れている．そこで末端で固定深さの探索を行い，詰む場合はその情報を，詰まない場合は固定深さの探索が展開した探索木の証明数と反証数を計算して，df-pnで活用する．実験の結果，棋譜に表れる実戦の詰み局面に対して，平均探索時間が標準的なdf-pnの約1/3，使用した局面表の節点の数は平均約1/5という大きな効率の向上を実現した．さらに，大規模な詰将棋問題において各種の拡張を組み込んだdf-pn+との比較においても，所要時間で約2/3，使用した局面表の節点数で半分強という効率の向上を実現した．

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.

収録刊行物

被引用文献 (1)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ