N人ゲームにおける最良優先探索(<特集>ゲームプログラミング)

概要

論文の詳細を見る
我々は,N人ゲームにおける,選択的深化を用いた探索アルゴリズムを2つ提案し,その有効性についての検証を行った.1つ目は,最良優先マックスN探索と呼ばれ,マックスN値という評価値を用いた最良優先探索であり,LuckHardtらによるマックスNとKorfらによる最良優先ミニマックス探索の自然な拡張である.2つ目は,手番を考慮した最良優先マックスN探索と呼ばれ,先のアルゴリズムにさらに変更を加えたものである.このアルゴリズムでは,異なる手番の局面の比較を避け,評価値の更新を同一手番の子孫の局面の評価値のみによって行う.インクリメンタルランダムゲームによる実験では,マックスNは深く読んでも性能が上がらず,逆により悪くなるという結果が得られた.Sturtevantらの提案したパラノイド探索は,マックスNよりも優れた性能を示したが,我々の提案した,2つの最良優先探索アルゴリズムは,より安定した強さを示し,特に,最良優先マックスN探索は十分な数の節点を展開できるときに,また,手番を考慮した最良優先マックスN探索はわずかな数の節点を展開するだけで手を決定しなければならないようなときに,より良い成績を収めた.ダイアモンドゲームを例題にした実験でも,2つの最良優先探索について同様の結果を得ることができた.マックスN値(ミニマックス値)を基準とした最良優先探索は,2人ゲームのみならず,一般のN人ゲームにおいても有効であることが示された.
2002-10-15

N人ゲームにおける最良優先探索(<特集>ゲームプログラミング)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク