証明数と反証数を用いたλ 探索 λ Search Based on Proof and Disproof Numbers

この論文にアクセスする

この論文をさがす

著者

抄録

本論文では脅威度と証明数・反証数の双方を利用するdf-pn λ 探索を提案する.脅威度と証明数・反証数は,両者ともAND/OR 木探索を効率的に行うための指標であり,脅威度を利用するλ 探索と,証明数・反証数を利用するdf-pn 探索は,どちらも優れた探索アルゴリズムである.脅威度と証明数・反証数の双方を用いることで,探索をさらに効率的に行うことは自然なアイデアである.脅威度と証明数・反証数の関係を結び付けるために,本論文では各節点ごとに,各脅威度に対応する疑似節点をモデル化する.そのうえで,疑似節点上の証明数・反証数を用いて,元の節点の証明数・反証数を定義することを提案し,それにより探索が制御されることを示す.さらに,性質の異なる複数のゲームを対象に,df-pn λ 探索とdf-pn 探索の性能を比較する実験を行った.その結果,将棋や囲碁においてdf-pn λ 探索はdf-pn 探索よりも性能が良いことを確認した.We present the df-pn λ search algorithm that combines threats with proof and disproof numbers. λ search is a promising method based on threats. Df-pn is an efficient algorithm that employs the notion of proof and disproof numbers. However, λ search uses neither proof nor disproof numbers, whereas df-pn incorporates no information on threat levels. Integrating threats with proof and disproof numbers is a natural extension to further enhance the search performance. We introduce pseudo-nodes for various threat levels at each node, to represent a node searched with a specific threat level. Then the proof and disproof numbers of the original node are defined using pseudo-nodes, which provides a model that can be searched with df-pn. We compared df-pn λ with df-pn on games with different properties. The results showed that df-pn λ is better than df-pn in Shogi and Go.

We present the df-pn λ search algorithm that combines threats with proof and disproof numbers. λ search is a promising method based on threats. Df-pn is an efficient algorithm that employs the notion of proof and disproof numbers. However, λ search uses neither proof nor disproof numbers, whereas df-pn incorporates no information on threat levels. Integrating threats with proof and disproof numbers is a natural extension to further enhance the search performance. We introduce pseudo-nodes for various threat levels at each node, to represent a node searched with a specific threat level. Then the proof and disproof numbers of the original node are defined using pseudo-nodes, which provides a model that can be searched with df-pn. We compared df-pn λ with df-pn on games with different properties. The results showed that df-pn λ is better than df-pn in Shogi and Go.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 48(11), 3455-3462, 2007-11-15

    一般社団法人情報処理学会

参考文献:  19件中 1-19件 を表示

各種コード

  • NII論文ID(NAID)
    110006530807
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    JPN
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • NDL 記事登録ID
    9272519
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-741
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ