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

• Item type: Symposium(1)
• 公開日: 2009-11-06
• タイトル: 探索結果を利用した実現確率探索
• タイトル / 言語: en
• タイトル: The Realization Probability Search Based on Search Results
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者名: 佐藤佳州; 高橋, 大介
• 著者名(英): Sato, Yoshikuni; Takahashi, Daisuke
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，探索結果に基づく実現確率探索を提案する．実現確率による探索打ち切りアルゴリズム（実現確率探索）は，コンピュータ将棋において注目を集めている探索法の一つであり，多くのトップレベルのプログラムがこのアルゴリズムをベースとした探索法を用いている．実現確率探索は探索深さの決定にプロの棋譜から求めた指し手の確率を用いることで，あり得そうな展開を深く探索するという特徴を持つアルゴリズムである．この手法は，よい結果を収めているものの，探索の残り深さや評価関数の性質などによらず確率が常に一定であるという点に改善の余地があると考えられる．また，ある程度探索を行いよさそうな手が分かってきた場合にも，プロの棋譜から求めた確率に基づき確率を決定してしまう点も問題点と考えられる．本論文ではこれらの問題点について，プログラムの探索結果を用い，深さに応じた確率を利用する，探索中に得られる情報を特徴として利用する，といった改良を行うことにより改善を試みた．実験の結果，プロの棋譜を基にした従来の実現確率探索と比較し，6 割程度の勝率を得ることに成功し，提案手法の有効性を示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose the 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 many top-level programs use this algorithm. This method decides 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.
• 書誌情報: ゲームプログラミングワークショップ2009論文集; 巻 2009, 号 12, p. 148-155, 発行日 2009-11-06
• 出版者 / 言語: ja
• 出版者: 情報処理学会