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

• Item type: Journal(1)
• 公開日: 2012-11-15
• タイトル: 最善手の予測に基づくゲーム木探索の分散並列実行
• タイトル / 言語: en
• タイトル: Distributed Game-tree Search Based on Prediction of Best Moves
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：ゲームプログラミング] ゲーム木探索，分散処理，将棋
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属: 東京大学情報基盤センター
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Information Technology Center, The University of Tokyo
• 著者名: 金子, 知適; 田中, 哲朗
• 著者名(英): Tomoyuki, Kaneko; Tetsuro, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，主記憶を共有しない多数の計算機を用いて，ゲーム木探索を並列に行う新たな手法を提案する．提案する枠組みでは，各節点における最善手や次善手を予想しながらマスタのゲーム木を成長させ，最終的に葉にスレーブが1台ずつ割り当てられる．各スレーブは，割り当てられた葉を独立に探索する．この手法ではマスタやスレーブ間の通信はほぼ最小限に抑えられており，通信遅延の大きな環境でも頑健に動くこと，また元のプログラムの変更をほとんど必要としないことが利点である．多数の計算機を用いることによる強さの向上の度合いについて，オープンソースプログラムのGPS将棋を用いた実験を行い，8スレーブの分散探索では4並列のメモリ共有探索に近い強さを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a new game-tree search method on distributed systems. In this method, a master tree grows based on the prediction of the best moves at each internal node until when each slave is assigned a leaf to search. Then, all slaves independently conduct a game-tree search. This framework has two major advantages; (1) it can work under an environment with relatively high latency, as it requires little communication between a master and slaves. (2) it works without significant modification of a base search program. In the experiments with an open source shogi program, the presented method worked effectively. 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 / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 53, 号 11, p. 2517-2524, 発行日 2012-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764