非同期並列ゲーム木探索での効果的な計算ノード割り当て

• Item type: Symposium(1)
• 公開日: 2014-10-31
• タイトル: 非同期並列ゲーム木探索での効果的な計算ノード割り当て
• タイトル / 言語: en
• タイトル: Efficient Assignment of Computation Nodes in Asynchronous Parallel Game-Tree Search
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京大学教養学部
• 著者所属: 東京大学総合文化研究科
• 著者所属(英): en
• 著者所属(英): College of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者名: 横山, 秀; 金子, 知適
• 著者名(英): Shu, Yokoyama; Tomoyuki, Kaneko
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 性能が低い安価なネットワークで接続された計算機環境を前提として研究されているゲーム木の局面分担方式での並列探索では，局面の分担を決定するためのマスタゲーム木を適切に構築することで，無駄な探索を行う計算機ノードを減らすことができる．本稿ではゲーム固有の知識によらず，探索時間を犠牲にすることのないマスタゲーム木の構築手法を提案する．また，この手法によるチェス探索を実装し，対局実験を行ったところ，計算ノード数によっては逐次探索よりも高性能で，並列化の効果が得られたことを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Asynchronous parallel game-tree search methods are effective ways to improve the playing strength by utilizing many computing nodes connected in low-cost network systems. This paper presents a method of making an improved plan for the assignment of computing nodes. In our framework, the master node manages the game-tree and makes an assignment based on the game-tree. Then, each computing node asynchronously searches the best move and evaluation for a position assigned to the node. To reduce the search overheads, the master's game-tree should be grown appropriately so that a better move has more computing nodes assigned in the corresponding sub game-tree for the move. We present two improvements over existing assignment; one is independence from game-specific knowledge and the other is the efficiency that makes the asynchronous parallel search framework suitable even for short time matches. We applied the proposed method to a top-level chess program, and evaluated the playing strength via self-plays. We confirmed that a program incorporated the presented method plays better than the original one when the number of the computing node are greater than or equak to eight.
• 書誌情報: ゲームプログラミングワークショップ2014論文集; 巻 2014, p. 82-88, 発行日 2014-10-31
• 出版者 / 言語: ja
• 出版者: 情報処理学会