探索結果を利用した実現確率探索

• Item type: Journal(1)
• 公開日: 2010-11-15
• タイトル: 探索結果を利用した実現確率探索
• タイトル / 言語: en
• タイトル: The Realization Probability Search Based on Search Results
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：ゲームプログラミング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者名: 佐藤佳州; 高橋, 大介
• 著者名(英): Yoshikuni, Sato; Daisuke, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，探索結果に基づく実現確率探索を提案する．実現確率による探索打ち切りアルゴリズム（実現確率探索）は，コンピュータ将棋において注目を集めている探索法の1つであり，多くのトップレベルのプログラムがこのアルゴリズムをベースとした探索法を用いている．実現確率探索は探索深さの決定にプロの棋譜から求めた指し手の確率を用いることで，ありえそうな展開を深く探索するという特長を持つアルゴリズムである．この手法は，多くの場面において優れた結果を収めているものの，プロの棋譜から求めた確率を利用するため，プログラムの探索手法や評価関数の性質によらず確率がつねに固定である点に改善の余地があると考えられる．また，実現確率探索では「王手」「駒を取る手」といった表面的な特徴から確率を算出するが，これらの特徴に加え，探索中の履歴を考慮することでさらに性能を改善することができる可能性があると考えられる．本論文ではこれらの点について，プログラムの探索結果を利用し，評価関数や探索の深さに応じた確率を利用する，探索中に得られる情報を特徴として利用する，といった改良を行うことにより改善を試みた．実験の結果，提案手法は全幅探索や従来の実現確率探索に勝ち越すことに成功し，その有効性を示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a realization probability search algorithm based on search results. The realization probability search is one of the search algorithms attracting much attention in the Computer-Shogi area, and it is used by many top-level programs. This method determines search depths according to probabilities of moves obtained from game records by professional players, and searches deeper for more probable moves. The realization probability search is an efficient algorithm, but it is considered that it still has room for improvement because probabilities of moves are fixed at any time. We improved the realization probability search by using the search results. In our method, probabilities change according to the rest of search depths and heuristics obtained while searching. In the result of our experiments, our program based on the proposed method is superior to existing methods.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 51, 号 11, p. 2021-2030, 発行日 2010-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764