PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

ふさこすえたけ
7 years ago
Views:

1 モンテカルロ木探索並列化囲碁マリオ AI 美添一樹 ETATO 研究員湊離散構造処理系プロジェクト 2013 年度秋のワークショップ 2013 年 11 月 26 日

2 並列モンテカルロ木探索の意義コンピュータ囲碁で人間を超える情報科学の有効性を示す大規模並列探索ライブラリ近い将来全てのアルゴリズムは大規模並列化が必要並列探索は実装が非常に大変なのでライブラリとして提供できると良い

3 AI の進歩 : チェス将棋囲碁 2013 IBM DeepBlue IBM Deep Blue 1997 第 2 回電王戦 GPS 将棋 Kasparov 将棋プログラム並列化で進歩を加速する MCTS の発明科研費代表者美添 1 万コア以上を用いる並列探索アルゴリズムで FPGAで将棋プログラムを作ってみるブログ囲碁名人に勝つ注 : これが課題名

4 従来の探索アルゴリズムモンテカルロ木探索 (MCTS) 評価関数を使う評価関数 1 回約 1μ 秒ランダムシミュレーションを使うプレイアウトと呼ぶプレイアウト 1 回約 1 ミリ秒

5 [Kocsis & Szepesvari 2006] UCT algorithm Upper Confidence bound applied to Trees [Auer, Cesa-Bianchi and fischer 2002] w 2ln t s s mean + bias Upper Confidence Bound によって確率分布を比較する正確にはこれは UCB1 節点の比較に UCB を用いる探索アルゴリズムが UCT Multi-Armed Bandit Problem UCT は幅広く応用されている

MCTS の応用 two player Planning [H. Nakhost and M.

biometric security multi player single player (real time) [Tanabe, Yoshizoe and

biometrics authentication systems, [Browne et al.

6 MCTS の応用 two player Planning [H. Nakhost and M. Müller 2009] Monte-Carlo Exploration for Deterministic Planning, IJCAI 09 biometric security multi player single player (real time) [Tanabe, Yoshizoe and Imai 2009] A study on security evaluation methodology for image-based biometrics authentication systems, [Browne et al. 2012] A Survey of Monte Carlo Tree Search Methods サーベイ論文 CACM [Gelly et al. 2012] The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions

7 並列化の難しさ探索には枝刈りが必須囲碁や将棋などでは実質的には 9 割以上の手が枝刈りされる均等な負荷分散が困難単純な方法は駄目探索木を分割して各計算機が担当注意 : うまく負荷が予測できればこれでもかなりうまく行く ( 参考 :GPS 将棋 )

8 分散ハッシュテーブルによる並列探索グラフの各節点を異なる計算ノードに割り当てるノード番号 = 3 並列化手法 depth-first reformulation ( 深さ優先変形 ) アルゴリズムの深さ優先変形によって通信の集中を回避する r f g ノード番号 = a c d e b

9 ハッシュ表に基づく並列探索 (TDS) Transposition table Driven Scheduling [Romein et al. 1999] 他のノードに探索を依頼 3 ノード番号 = ノード 0 ハッシュ表ノード 1 ハッシュ表ハッシュキー 2 ノード番号 = ノード番号 = ノード 2 ハッシュ表ノード 3 ハッシュ表各節点はハッシュ値を持つハッシュ値の一部を計算ノードの番号とみなす均等な負荷分散と引き替えに細かい通信が増える

TDS UCT 動作全体像 2 3 4 5 1 6 1 2 3 1 ジョブおよびジョブ番号注意 : 節点も計算機もどちらもノードなので非常にややこしい 4 5 どの節点をどの計算ノードが担当するかはハッシュ関数に依存する 6

10 TDS UCT 動作全体像ジョブおよびジョブ番号注意 : 節点も計算機もどちらもノードなので非常にややこしい 4 5 どの節点をどの計算ノードが担当するかはハッシュ関数に依存する 6 補足 : 根節点を担当する計算ノードもさらに深い節点を担当しているデータは計算ノードに固定されているジョブが移動する当然ジョブの総数は計算ノードより多くないといけない実験では計算ノード数 x 3~10 個のジョブを使用した

11 depth-first reformulation による通信の集中の解消 r r f g f g c d e c d e a b a b Normal UCT 不必要に root まで返っている Depth First UCT 不必要なリターンを削除 [ 吉本, 岸本, 金子, 美添 2007] 局所性を高めるのは並列化の基本 11

12 virtual loss によるジョブの分散 f r g 並列化と Virtual Loss 何もしないと全てのプロセスが同じ所を探索する a c d e b そこで探索中の節点には Virtual Loss というペナルティーを加える d は節点を探索中のプロセス数 D は兄弟節点の d の合計 [Coulom 2007?] w s 2ln t s s w d 2ln( t D) s d

13 TDS + depth first UCT = TDS-df-UCT TDS-df-UCT: 仮想ゲームの性能 3,000 2,500 2,000 1,500 1, y=x Speedup 19 路囲碁に近い 1.0 ms playout 分岐路囲碁に近い 0.1 ms playout 分岐 Number of Cores P-Game を用いた一般的な仮想ゲーム大幅な速度向上を達成プレイアウト速度で大きな差がある (Infiniband の能力による貢献も大きい ) ハードウェア : TSUBAME2 supercomputer 各計算ノード : Xeon 2.93GHz x 2 (12 cores) ネットワーク : Infiniband QDR x 2 MPI ライブラリ : MVAPICH2 library を使用

7 倍の速度囲碁の性能を仮想ゲームに近づけることが目標プレイアウトを複数まとめるデータ構造の圧縮 ( まだ途中 ) その他のパラメータを調整中

14 SGI UV1000 TSUBAME2 並列囲碁プログラム仮想ゲームより遅い通信遅延の増大囲碁のデータ構造が大きいためプレイアウトが速いため本実験では序盤で約 0.4ms 終盤ではより速くなる並列化に伴うオーバーヘッド単一コアで並列版を動かすと倍の速度囲碁の性能を仮想ゲームに近づけることが目標プレイアウトを複数まとめるデータ構造の圧縮 ( まだ途中 ) その他のパラメータを調整中速度向上囲碁プログラムの速度向上 SGI UV1000 Tsubame コア数

15 ( 参考 ) 自動チューニングハードウェアに合わせたチューニングのこと HPC 業界 (?) の取り組み cf. 自動チューニング研究会 ( 須田礼仁先生 ) ほとんどのメンバーは数値計算が専門並列計算機はそれぞれ性質が異なるのでパラメータをチューニングする必要がある並列囲碁との関連十分なテストが難しい ( 自宅にスパコンが欲しい ) 自動チューニングの成果を利用して念力に頼る部分を減らしたい例少コア数で実験多いコア数のパラメータを推測例オンラインとオフラインの区別をつけない今のところそれほど成功していない

16 run 1 playout at leaf (default) run N playouts at leaf プレイアウトを複数同時に (Leaf parallel) プレイアウトが遅ければ速度向上も大きい複数のプレイアウトを一度に実行すれば見た目は長くなる Tsubame2 上では 1.0 ms あれば性能向上が得られるので序盤では 2 回実行すれば十分 ( 序盤終盤ではプレイアウト速度が変わる )

17 speedup Leaf Parallel の性能 ( 序盤 ) Leaf 1~4 の速度向上 default leaf2 leaf3 leaf4 Leaf 2 以降はそれほど性能が伸びない 1.0 ms 以上は不要か? 現在は Leaf2 を使用中逐次版の対戦実験で Leaf2 は強さに悪影響がないことを確認済み ( 理由は不明だが婦考慮時間が長い場合はむしろ強くなる ) cores

18 その他のパラメータ調整地味なので詳細は省略 Virtual Loss の調整他のジョブが探索中の節点をどの程度忌避するかトレードオフ局所性を高める <-> 有望なところに集中 Total job number starvation が起こらないギリギリの数に調整する考慮時間に応じた調整考慮時間 30 秒と 3 秒では最適な値が異なる

19 並列囲碁プログラムの途中経過ネット対局サーバ KGS に並列版を投入主に人間を相手に対局 SGI-UV1000 の 512 コアを主に使用今後 Tsubame2 もテストする予定まだデバッグ中頻繁に時間切れ負けする通信遅延の見積もりが甘い終局時の死活不同意の対応などその他の不具合直前の MPI プロセスが生き残っていて止まる 1 ノードでも止まると全体が止まる

20 耐故障性 ( 実装中 ) 青の計算ノードが止まると青い計算ノードを通過するジョブが消滅していくすぐには分からないのでたちが悪いある程度対応は可能なはず故障ノードを検知ハッシュ関数を変更して故障ノードの仕事を他のノードに均等に振り分け N 台以下の故障まで対応と決めるルート節点を担当している計算機が故障した場合はあきらめる

21 人間らしいゲーム AI 強い AI 楽しい AI 将棋や囲碁は今は強い AI 人間らしい ( 自然に弱い )AI を作る大会 The 2K BotPrize FPS (Unreal Tournament 2004) の AI と対戦 ( 注 : チャットなどはしないプレイのみで判定 ) 2012 年に人間より人間らしい AI( 投票結果 ) Mario AI Turing Track 2013 年に人間より人間らしい AI( 投票結果 ) 対戦相手協力相手として意義が大きい

22 Mario AI Mario AI とは Java ベースの某有名ゲームクローン探索で与えられる情報は画面に映っている情報のみステージはランダム生成行動は 1 フレームごとに 11 通りの行動がある AI は 42 ミリ秒以内 (1/24 秒 ) に探索, 出力を行う画面内の敵の動作は決定的クリアの早さを競う部門では A* 探索ベースの AI が有名 Turing Test Track 人間の投票によって人間ぽい方を選ぶ人間 2 人と AI 3 つが参加 (2013 年 )

23 UCT + 進化計算によるマリオ AI 人間のプレイを模倣するプレイアウトの性質報酬を調整する人間はミスを前提としたプレイをする UCT の勝率の高い選択肢を選ぶ性質と似ている A* で普通に作ると非人間的にうまいプレイアウトを調整して人間の挙動に似せる進化計算で調整 (GA と DE) 人間の操作履歴との一致率を60% 程度に DE: Differential Evolution ( 差分進化 ) 進化計算と UCT による Mario を人間らしくプレイする AI 中野雄基, 美添一樹, 脇田建. 第 18 回ゲームプログラミングワークショップ

24 UCT を Mario AI へ適用 UCT 一般的な手法提案手法目的強い AI の作成人間らしくプレイするプレイアウト ( 方策 ) 強い人間 ( プロ ) から頻出パターンなどを学習任意のプレイヤーから戦略を学習報酬負け勝ち 0 または 1 似ていない <-> 似ている 0 ~ 1 探索時間数秒から十数秒 42ミリ秒以内 ( 実験では300プレイアウト可能 )

dlshogiアピール文章

dlshogiアピール文章第 28 回世界コンピュータ将棋選手権 dlshogi アピール文章山岡忠夫 2018 年 5 月 1 日更新下線部分は第 5 回将棋電王トーナメントからの差分を示す 1 特徴ディープラーニングを使用指し手を予測する Policy Network 局面の勝率を予測する Value Network 入力特徴にドメイン知識を活用モンテカルロ木探索並列化自己対局による強化学習既存将棋プログラムの自己対局データを使った事前学習