動的候補手拡大を用いたDf-pnアルゴリズム

• Item type: Symposium(1)
• 公開日: 2007-11-09
• タイトル: 動的候補手拡大を用いたDf-pnアルゴリズム
• タイトル / 言語: en
• タイトル: Df-pn Algorithm with Dynamic Widening
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 中央大学研究開発機構
• 著者所属(英): en
• 著者所属(英): Research and Development Center, Chuo University
• 著者名: 美添一樹
• 著者名(英): Yoshizoe, Kazuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 証明数探索は証明数/反証数の大小を基準として探索順序を決定する．証明数が小さいことは，探索すべき節点が少ないことを意味し，多くの問題では実際に良い手であることが多い．見込みの高い手から探索することは探索アルゴリズムの性能を考慮するうえで非常に重要な要素である．しかし，見込みの無い候補手が多数存在する場合，証明数/反証数の大小が基準として相応しくないことがある．そのような場合に，証明数/反証数の計算に一部の候補手の証明数/反証数のみを合計する手法を適用することを提案する．囲碁の19路盤における捕獲問題を対象に実験を行った結果，候補手をヒューリスティックに限定した場合にはこの手法は効果が無かったが，全合法手を対象に探索を行った場合には本手法は大きな効果を発揮することを示した．結果として，全合法手を対象に探索を行うことにより結果の正しさを保証しながら，探索速度は候補手をヒューリスティックに限定した場合の平均して3倍程度に抑えることができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Proof number search expands nodes with smaller (dis-) proof numbers. Nodes having (dis-) proof numbers are expected to need less number of nodes to be (dis-) proved, and in many for move ordering. However, when there are many number of unpromising child nodes, (dis-) proof numbers are not always a suitable measure for move ordering, because unpromising nodes temporarily increases (dis-) proof numbers. In such cases, we propose to use only part of the child nodes (in stead of all child nodes) upon calculating (dis-) proof numbers. Experiment was done for capturing problems of Go on 19x19 boards. The result shows that this method was not effective if combined with heuristically limited candidate move generator, but was highly effective if all legal moves were generated. As a result, we could guarantee the correctness by generating all legal moves, while maintaining the speed performance approximately 3 times slower compared to searching based on heuristic move generation.
• 書誌情報: ゲームプログラミングワークショップ2007論文集; 巻 2007, 号 12, p. 60-65, 発行日 2007-11-09
• 出版者 / 言語: ja
• 出版者: 情報処理学会