文献

J-GLOBAL ID：201202244398402425   整理番号：12A1712231

最善手の予測に基づくゲーム木探索の分散並列実行

Distributed Game-tree Search Based on Prediction of Best Moves

著者 (2件)： 金子知適 (東大 大学院総合文化研究科) ,  田中哲朗 (東大 情報基盤セ)
資料名： 情報処理学会論文誌ジャーナル(CD-ROM)  (情報処理学会論文誌 論文誌ジャーナル(CD-ROM))
巻： 53  号： 11  ページ： 2517-2524  発行年： 2012年11月15日 
JST資料番号： Z0778B  ISSN： 1882-7837  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,主記憶を共有しない多数の計算機を用いて,ゲーム木探索を並列に行う新たな手法を提案する。提案する枠組みでは,各節点における最善手や次善手を予想しながらマスタのゲーム木を成長させ,最終的に葉にスレーブが1台ずつ割り当てられる。各スレーブは,割り当てられた葉を独立に探索する。この手法ではマスタやスレーブ間の通信はほぼ最小限に抑えられており,通信遅延の大きな環境でも頑健に動くこと,また元のプログラムの変更をほとんど必要としないことが利点である。多数の計算機を用いることによる強さの向上の度合いについて,オープンソースプログラムのGPS将棋を用いた実験を行い,8スレーブの分散探索では4並列のメモリ共有探索に近い強さを確認した。(著者抄録)

シソーラス用語： *木探索 ,  *並列処理 ,  木【グラフ】 ,  *ゲーム ,  マスタスレーブシステム ,  通信 ,  遅れ ,  ロバスト性 ,  マルチコンピュータシステム ,  分散処理 ,  性能評価 ,  ゲーム木
準シソーラス用語： 通信遅延

分類 (3件)： 人工知能  (JE08000Z) ,  ディジタル計算機方式一般  (JC02010O) ,  ゲーム理論  (KA03060T)

引用文献 (11件)：

• [1] Brockington, M.G.: Asynchronous Parallel Game-Tree Search, Ph.D. Thesis, Department of Computing Science, University of Alberta (1997).
• [2] Feldmann, R.: Game Tree Search on Massively Parallel Systems (1993).
• [3] Kishimoto, A.: Transposition Table Driven Scheduling for Two-Player Games, M.Sc. Thesis, University of Alberta (2002).
• [4] Marsland, T.A. and Popowich, F.: Parallel Game-Tree Search, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.7, pp.442-452 (1985).
• [5] Obata, T., Sugiyama, T., Hoki, K. and Ito, T.: Consultation Algorithm in Computer Shogi - A Move Decision by Majority, Computers and Games - 7th International Conference (CG2010), LNCS, No.6515, pp.156- 165, Springer-Verlag (2011).

タイトルに関連する用語 (3件)： 予測 ,  ゲーム ,  木探索