モンテカルロ木探索 並列化 囲碁 マリオ AI 美添一樹 ETATO 研究員 湊離散構造処理系プロジェクト 2013 年度秋のワークショップ 2013 年 11 月 26 日
並列モンテカルロ木探索の意義 コンピュータ囲碁で人間を超える 情報科学の有効性を示す 大規模並列探索ライブラリ 近い将来 全てのアルゴリズムは大規模並列化が必要 並列探索は実装が 非常に 大変なのでライブラリとして提供できると良い
AI の進歩 : チェス 将棋 囲碁 2013 IBM DeepBlue IBM Deep Blue 1997 第 2 回電王戦 GPS 将棋 Kasparov 将棋プログラム 並列化で進歩を加速する MCTS の発明 科研費代表者美添 1 万コア以上を用いる並列探索アルゴリズムで FPGAで将棋プログラムを作ってみるブログ http://blog.livedoor.jp/yss_fpga/archives/53897129.html 囲碁名人に勝つ 注 : これが課題名
従来の探索アルゴリズム モンテカルロ木探索 (MCTS) 評価関数を使う 評価関数 1 回 約 1μ 秒 ランダムシミュレーションを使うプレイアウトと呼ぶ プレイアウト 1 回 約 1 ミリ秒
[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. 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
並列化の難しさ 探索には枝刈りが必須 囲碁や将棋などでは実質的には 9 割以上の手が枝刈りされる 均等な負荷分散が困難 単純な方法は駄目 探索木を分割して各計算機が担当 注意 : うまく負荷が予測できれば これでもかなりうまく行く ( 参考 :GPS 将棋 )
0 1 2 3 分散ハッシュテーブルによる並列探索 グラフの各節点を 異なる計算ノードに割り当てる ノード番号 = 3 並列化手法 depth-first reformulation ( 深さ優先変形 ) アルゴリズムの深さ優先変形によって通信の集中を回避する r 011001 11 01001011 f g ノード番号 = 1 101100 01 10001110 a c d e b
ハッシュ表に基づく並列探索 (TDS) Transposition table Driven Scheduling [Romein et al. 1999] 他のノードに探索を依頼 3 ノード番号 = 3 011001 11 01001011 ノード 0 ハッシュ表 ノード 1 ハッシュ表 ハッシュキー 2 ノード番号 = 2 1 101100 10 11010001 ノード番号 = 1 101100 01 10001110 ノード 2 ハッシュ表 ノード 3 ハッシュ表 各節点はハッシュ値を持つ ハッシュ値の一部を計算ノードの番号とみなす 均等な負荷分散と引き替えに 細かい通信が増える
TDS UCT 動作全体像 2 3 4 5 1 6 1 2 3 1 ジョブおよびジョブ番号 注意 : 節点も計算機もどちらも ノード なので非常にややこしい 4 5 どの節点をどの計算ノードが担当するかはハッシュ関数に依存する 6 補足 : 根節点を担当する計算ノードもさらに深い節点を担当している データは計算ノードに固定されている ジョブ が移動する 当然 ジョブの総数は計算ノードより多くないといけない 実験では計算ノード数 x 3~10 個のジョブを使用した
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
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
TDS + depth first UCT = TDS-df-UCT TDS-df-UCT: 仮想ゲームの性能 3,000 2,500 2,000 1,500 1,000 500 - y=x Speedup 19 路囲碁に近い 1.0 ms playout 分岐 150 9 路囲碁に近い 0.1 ms playout 分岐 40 0 800 1600 2400 3200 4000 4800 Number of Cores P-Game を用いた 一般的な仮想ゲーム 大幅な速度向上を達成 プレイアウト速度で大きな差がある (Infiniband の能力による貢献も大きい ) ハードウェア : TSUBAME2 supercomputer 各計算ノード : Xeon 2.93GHz x 2 (12 cores) ネットワーク : Infiniband QDR x 2 MPI ライブラリ : MVAPICH2 library を使用
SGI UV1000 TSUBAME2 並列囲碁プログラム 仮想ゲームより遅い 通信遅延の増大 囲碁のデータ構造が大きいため プレイアウトが速いため 本実験では序盤で約 0.4ms 終盤ではより速くなる 並列化に伴うオーバーヘッド 単一コアで並列版を動かすと 0.6-0.7 倍の速度 囲碁の性能を仮想ゲームに近づけることが目標 プレイアウトを複数まとめる データ構造の圧縮 ( まだ途中 ) その他のパラメータを調整中 速度向上 400 350 300 250 200 150 100 50 - 囲碁プログラムの速度向上 SGI UV1000 Tsubame2 0 200 400 600 800 1000 1200 コア数
( 参考 ) 自動チューニング ハードウェアに合わせたチューニングのこと HPC 業界 (?) の取り組み cf. 自動チューニング研究会 ( 須田礼仁先生 ) ほとんどのメンバーは数値計算が専門 並列計算機はそれぞれ性質が異なるのでパラメータをチューニングする必要がある 並列囲碁との関連 十分なテストが難しい ( 自宅にスパコンが欲しい ) 自動チューニングの成果を利用して 念力に頼る部分を減らしたい 例 少コア数で実験 多いコア数のパラメータを推測 例 オンラインとオフラインの区別をつけない 今のところ それほど成功していない
run 1 playout at leaf (default) run N playouts at leaf プレイアウトを複数同時に (Leaf parallel) プレイアウトが遅ければ速度向上も大きい 複数のプレイアウトを一度に実行すれば見た目は長くなる Tsubame2 上では 1.0 ms あれば性能向上が得られるので 序盤では 2 回実行すれば十分 ( 序盤 終盤ではプレイアウト速度が変わる )
speedup Leaf Parallel の性能 ( 序盤 ) 350 300 250 200 150 100 50 Leaf 1~4 の速度向上 default leaf2 leaf3 leaf4 Leaf 2 以降はそれほど性能が伸びない 1.0 ms 以上は不要か? 現在は Leaf2 を使用中 逐次版の対戦実験で Leaf2 は強さに悪影響がないことを確認済み ( 理由は不明だが 婦考慮時間が長い場合はむしろ強くなる ) 0 0 200 400 600 800 1000 cores
その他のパラメータ調整 地味なので詳細は省略 Virtual Loss の調整 他のジョブが探索中の節点をどの程度忌避するか トレードオフ 局所性を高める <-> 有望なところに集中 Total job number starvation が起こらないギリギリの数に調整する 考慮時間に応じた調整 考慮時間 30 秒と 3 秒では最適な値が異なる
並列囲碁プログラムの途中経過 ネット対局サーバ KGS に並列版を投入 主に人間を相手に対局 SGI-UV1000 の 512 コアを主に使用 今後 Tsubame2 もテストする予定 まだデバッグ中 頻繁に時間切れ負けする 通信遅延の見積もりが甘い 終局時の死活不同意の対応など その他の不具合 直前の MPI プロセスが生き残っていて止まる 1 ノードでも止まると全体が止まる
耐故障性 ( 実装中 ) 青の計算ノードが止まると 青い計算ノードを通過するジョブが消滅していく すぐには分からないのでたちが悪い ある程度対応は可能なはず 故障ノードを検知 ハッシュ関数を変更して故障ノードの仕事を他のノードに均等に振り分け N 台以下の故障まで対応 と決める ルート節点を担当している計算機が故障した場合はあきらめる
人間らしいゲーム AI 強い AI 楽しい AI 将棋や囲碁は今は強い AI 人間らしい ( 自然に弱い )AI を作る大会 The 2K BotPrize FPS (Unreal Tournament 2004) の AI と対戦 ( 注 : チャットなどはしない プレイのみで判定 ) 2012 年に人間より人間らしい AI( 投票結果 ) Mario AI Turing Track 2013 年に人間より人間らしい AI( 投票結果 ) 対戦相手 協力相手として意義が大きい
Mario AI Mario AI とは Java ベースの某有名ゲームクローン 探索で与えられる情報は画面に映っている情報のみ ステージはランダム生成 行動は 1 フレームごとに 11 通りの行動がある AI は 42 ミリ秒以内 (1/24 秒 ) に探索, 出力を行う 画面内の敵の動作は決定的 クリアの早さを競う部門では A* 探索ベースの AI が有名 Turing Test Track 人間の投票によって人間ぽい方を選ぶ 人間 2 人と AI 3 つが参加 (2013 年 )
UCT + 進化計算によるマリオ AI 人間のプレイを模倣する プレイアウトの性質 報酬を調整する 人間はミスを前提としたプレイをする UCT の 勝率 の高い選択肢を選ぶ性質と似ている A* で普通に作ると非人間的にうまい プレイアウトを調整して人間の挙動に似せる 進化計算で調整 (GA と DE) 人間の操作履歴との一致率を60% 程度に DE: Differential Evolution ( 差分進化 ) 進化計算と UCT による Mario を人間らしくプレイする AI 中野雄基, 美添一樹, 脇田建. 第 18 回ゲームプログラミングワークショップ. 2013.
UCT を Mario AI へ適用 UCT 一般的な手法 提案手法 目的強い AI の作成人間らしくプレイする プレイアウト ( 方策 ) 強い人間 ( プロ ) から頻出パターンなどを学習 任意のプレイヤーから戦略を学習 報酬 負け 勝ち 0 または 1 似ていない <-> 似ている 0 ~ 1 探索時間 数秒から十数秒 42ミリ秒以内 ( 実験では300プレイアウト可能 )