局面の実現確率に基づくゲーム木探索アルゴリズム

• Item type: Symposium(1)
• 公開日: 2001-10-26
• タイトル: 局面の実現確率に基づくゲーム木探索アルゴリズム
• タイトル / 言語: en
• タイトル: Game-Tree Search Algorithm Based on Realization Probability
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京大学工学系研究科
• 著者所属: 東京大学工学系研究科
• 著者所属: 東京大学工学系研究科
• 著者所属: 東京大学新領域創成科学研究科
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): School of Frontier Sciences, The University of Tokyo
• 著者名: 鶴岡, 慶雅; 横山, 大作; 丸山, 孝志; 近山, 隆
• 著者名(英): Tsuruoka, Yoshimasa; Yokoyama, Daisaku; Maruyama, Takashi; Chikayama, Takashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 現在のトップレベルのコンピュータ将棋プログラムの多くは深さ打ち切りのミニマックス法を基本としている．深さ打ち切りによる探索は，以前から多くの欠点が指摘されながらも，依然としてコンピュータ将棋における最も実用的な探索手法とされている．それに対して本論文では，局面の実現確率を打ち切り条件とする探索アルゴリズムを提案する．局面の実現確率とは，その局面にいたるまでの手順が実際に指されて，その局面が実現する確率を表す．したがって，探索打ち切り条件を局面の実現確率とすることで，「ありそうな展開」を中心に読むことができ，効率的な探索が可能になることが期待される．本論文では，提案アルゴリズムを実装した将棋プログラムを作成し，深さ打ち切りアルゴリズムとの比較による評価を行なった．実験の結果，実現確率打ち切りプログラムは，深さ打ち切りプログラムよりも有意に強く，その効果は，深さ打ち切りプログラムを5倍に高速化する効果に相当することを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Most of the state-of the art computer shogi programs adopt variants of fixed-depth minimax search algorithm. Although many drawbacks of the fix-depth search have been pointed out, the algorithm is still considered to be the most practical one for computer shogi programs. In this paper we propose a new game tree search algorithm based on realization probability instead of depth. Realization probability of a certain node represents the probability that the moves leading to the node will actually to be played. Thus, this algorithm spends little computational resource on unrealistic moves, resulting in more effective search. We provide experimental results showing that this new algorithm performs significantly better than the fixed-depth search algorithm and its performance gain is equivalent to speedup of more than 5 times.
• 書誌情報: ゲームプログラミングワークショップ2001論文集; 巻 2001, 号 14, p. 17-24, 発行日 2001-10-26
• 出版者 / 言語: ja
• 出版者: 情報処理学会