証明数と反証数を用いたλ 探索

• Item type: Journal(1)
• 公開日: 2007-11-15
• タイトル: 証明数と反証数を用いたλ 探索
• タイトル / 言語: en
• タイトル: λ Search Based on Proof and Disproof Numbers
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：ゲームプログラミング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 探索
• 著者所属: 公立はこだて未来大学
• 著者所属: 中央大学研究開発機構
• 著者所属: 公立はこだて未来大学
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属: 東京大学情報基盤センター
• 著者所属: アルバータ大学コンピューティング・サイエンス学科
• 著者所属(英): en
• 著者所属(英): Future University-Hakodate
• 著者所属(英): en
• 著者所属(英): Center of Research and Development Initiative, Chuo University
• 著者所属(英): en
• 著者所属(英): Future University-Hakodate
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Information Technology Center, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Computing Science, University of Alberta
• 著者名: 副田, 俊介; 美添一樹; 岸本, 章宏; 金子, 知適; 田中, 哲朗; マーティンミュラー
• 著者名(英): Shunsuke, Soeda; Kazuki, Yoshizoe; Akihiro, Kishimoto; Tomoyuki, Kaneko; Tetsuro, Tanaka; Martin, M¨uller
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では脅威度と証明数・反証数の双方を利用するdf-pn λ 探索を提案する．脅威度と証明数・反証数は，両者ともAND/OR 木探索を効率的に行うための指標であり，脅威度を利用するλ 探索と，証明数・反証数を利用するdf-pn 探索は，どちらも優れた探索アルゴリズムである．脅威度と証明数・反証数の双方を用いることで，探索をさらに効率的に行うことは自然なアイデアである．脅威度と証明数・反証数の関係を結び付けるために，本論文では各節点ごとに，各脅威度に対応する疑似節点をモデル化する．そのうえで，疑似節点上の証明数・反証数を用いて，元の節点の証明数・反証数を定義することを提案し，それにより探索が制御されることを示す．さらに，性質の異なる複数のゲームを対象に，df-pn λ 探索とdf-pn 探索の性能を比較する実験を行った．その結果，将棋や囲碁においてdf-pn λ 探索はdf-pn 探索よりも性能が良いことを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 48, 号 11, p. 3455-3462, 発行日 2007-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764