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

• Item type: Symposium(1)
• 公開日: 2010-11-12
• タイトル: 最善手の予測に基づくゲーム木探索の分散並列実行
• タイトル / 言語: en
• タイトル: Distributed Game-Tree Search Based on Prediction of Best Moves
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属: 東京大学情報基盤センター
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Information Technology Center, The University of Tokyo
• 著者名: 金子, 知適; 田中, 哲朗
• 著者名(英): TOMOYUKI, KANEKO; TETSURO, TANAKA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: メモリを共有しないクラスタ環境においてゲーム木探索を並列に行う手法は古くから研究されているが,従来の手法はいずれもプログラムの大幅な改変を必要とした.本研究では,元のプログラムの変更をほとんど要しないような単純さを保ちながらも,全体の強さを向上させる分散並列探索の枠組みを提案する.提案する枠組みでは,各節点における最善手を予想しながら再帰的にマスターのゲーム木を成長させ,各葉にスレーブが一つづつ割り当てられるまでゲーム木を成長させた後に残りの探索をスレーブに任せる.GPS将棋を用いた実験からは上位2手に集中的に資源を割り当てる単純な仕組みでも効果的に機能し,8スレーブの分散探索では4並列のメモリ共有探索に近い強さを実現した.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Parallel game-tree search techniques on distributed systems have been intensively researched. However, one has to drastically modify his program to adopt such techniques. This paper presents a simple but effective framework of parallel game-tree search on distributed systems, which requires few modifications on a sequential implementation. In this framework, the master tree grows based on the prediction of the best moves at each internal node until when each slave is assigned a unique leaf in the master tree. Then, each slave independently conducts a game-tree search. In the experiments with GPS-Shogi, the presented search worked effectively even when one simply assigned most computer resources to the top two moves at each node. The strength of the presented search with 8 slaves was almost comparable to that of a shared memory search with 4-threads.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12496601
• 書誌情報: ゲームプログラミングワークショップ2010論文集; 巻 2010, 号 12, p. 126-133, 発行日 2010-11-12
• 出版者 / 言語: ja
• 出版者: 情報処理学会