多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例）コンピュータ将棋における次手の計算

Presentation on theme: "多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例）コンピュータ将棋における次手の計算"— Presentation transcript:

1 多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例）コンピュータ将棋における次手の計算
6八金 2六歩 3六香 ゲーム木探索 例）コンピュータ将棋における次手の計算 非常に多くの計算リソースを消費する ⇒遊休PCを利用して高速化 低コストで高性能 3六香 6八金

2 将棋ソフト激指（開発：近山研有志）を改造
実装 特徴 動的にPCが増減する中でも動作可能 中央集権的な管理を行わない システムの構成 コンピュータ将棋 将棋ソフト激指（開発：近山研有志）を改造 将棋の思考ルーチンなど 岸本らの手法 [ICCP’02]に基づく 同じ盤面を探索するPCは常に同じ 同じ盤面の2回目以降の探索を省略 分散ゲーム木探索 タスクの生成 実行結果の取得 タスク管理機構 盤面のハッシュ値に基づいて探索を各PCにばらまく タスク投入先PCとの通信 通信機構 Phoenixを利用 物理PCに依存しない名前空間を提供 盤面のハッシュ値とPCとを対応付け 並列計算ライブラリ 実行の様子 以前に現れた盤面なので探索を省略 6 17 20 13 名前空間の割り当ては動的に変更可能 ⇒PCの追加・削除にあわせて調節 3 34 62 42 53 23 １ 60 6 名前空間 16 32 48 64

3 多数の遊休PC上での 分散ゲーム木探索 性能評価 実験環境 実験内容 東芝TECRA x 720台 各PCは100Base-Tで結合
金田憲二 東京大学 / PRESTO, JST 性能評価 実験環境 東芝TECRA x 720台 CPU: PentiumM 1.3GHz Memory: 512MB 各PCは100Base-Tで結合 実験内容 将棋の中盤の盤面からの探索時間 探索の深さは12と14

4 実験結果 考察：性能低下の原因 1台時と比較して7~8倍の性能向上 元の激指と比較すると4~15倍遅い 分散化によるオーバヘッド
探索盤面数の増加 深さ12で約2倍，深さ14で約7倍 小さい並列度 同時に探索可能な盤面数が，　　　　　　　　　　　　　　　　　　深さ10の探索では，最大で162 深さ12における探索時間 深さ14における探索時間 2分木の探索木 将棋の探索木 参考文献 　Kenjiro Taura, Kenji Kaneda, and Toshio Endo　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 “Phoenix: a Parallel Programming Model for Accommodating Dynamically Joining/Leaving Resources” (PPoPP’03) Kenji Kaneda, Kenjiro Taura, and Akinori Yonezawa 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　“Routing and Resource Discovery in Phoenix Grid-Enabled Message Passing Library” (CCGrid’04)

5 27 侵入検知システムのデータベース 22 侵入検知システムのデータベース 24 侵入検知システムのデータベース
侵入検知システムのデータベース 14 侵入検知システムのデータベース 16 侵入検知システムのデータベース 18 侵入検知システムのデータベース 20 侵入検知システムのデータベース 22　侵入検知システムのデータベース 24　侵入検知システムのデータベース 27 侵入検知システムのデータベース

6 36 侵入検知 侵入検知 44 侵入検知 48 侵入検知 56 侵入検知 80 侵入検知システムのデータベース