ゲーム木探索の並列化について

臼井 啓素  山下 雅史  今井 正治  茨木 俊秀  

誌名
電子情報通信学会論文誌 D   Vol.J69-D   No.10   pp.1382-1393
発行日: 1986/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(963.1KB)>>
論文を購入




あらまし: 
完全情報2人ゲームはminimaxゲーム木で表現され,ゲーム木を解くことで両者が最適な手を選んだ場合の結果を知ることができる.この目的に種々の探索法が提案されているが,本論文では,それらをm台のプロセッサをもつ並列コンピュータ上で実行することを考え,計算時間がmとともにどのように変化するかを調べた.理論的結果としては,1台のプロセッサの場合に対する速度向上比がmより大(加速異常)あるいは1より小(減速異常)になり得ることを指摘し,更に本論文で考察した5種の探索法では減速異常は生じないことを証明した.つぎに探索法の全般的な挙動をシミュレーション実験で評価し.速度向上比はmよりかなり小さくなることを示し,その理由を検討した.試みに探索法の中では有資格探索が比較的良好な結果を与えている.