Comments
Description
Transcript
モンテカルロ 木探索索 コンピュータ囲碁の進歩について
モンテカルロ⽊木探索索 および コンピュータ囲碁の進歩について 湊離離散構造処理理系プロジェクト 研究員 美添 ⼀一樹 1 1 ゲームAI研究の特徴 良いところ 悪いところ ✴ 目的が明確 ✴ 評価基準が明確 ✴ 実用性が磨かれる ✴ 研究のための研究は ✴ 問題の性質が偏る ✴ 評価基準が一つだけ ✴ 実装が大変 ✴ 研究のための研究が 速やかに淘汰される 速やかに淘汰される 2 2 ゲームAIの現状 チェッカー 1994年年に世界チャンピオンに勝利利 （2007年年に引き分け証明） オセロ 1997年年に世界チャンピオンに完勝 チェス 1997年年に世界チャンピオンに勝利利 (IBM DeepBlue vs Kasparov) 将棋 (削除) 囲碁 アマ6段くらい Scrabble ⼈人間より強い バック ギャモン ⼈人間より強い ポーカー 2008年年に⼈人間に勝利利 (1対1 Texas holdʼ’em) クイズ 2011年年 IBM Watson 3 3 ⼆二⼈人ゼロ和完全情報ゲームと minimax探索索 末端のスコアが分かれば、 探索索により最善⼿手が分かる 50 50 47 50 50 70 47 24 70 25 47 67 15 67 Max node 65 Min node 4 4 minimax探索索の前提 末端のスコアが分からないとminimax探索索はできない その1、本当に末端まで探索索 その2、評価関数を使う f(局⾯面) = スコア 詰将棋 評価関数は、何とかして作る (昔は⼿手作り) 最近は機械学習で作るのが主流流 ? ? ? ? 五目並べ 5 5 囲碁の難しさ 探索索空間が巨⼤大＝読み切切れない＝その1はダメ チェッカー 1020 オセロ チェス 将棋 囲碁(9路路) 10 28 10 50 良良い評価関数が作れる ⼿手⽣生成、機械学習などによる ⾼高速（μ秒オーダー）、 正確な評価関数が存在する 1071 10 囲碁では、良良い 評価関数が作れない ＝その2もダメ 38 囲碁(19路路) 10171 6 6 第3の⽅方法、モンテカルロ法 • 囲碁は終盤に近づくにつれ て合法⼿手が減少する • 合法⼿手の中からランダムに 選んで打つだけのプレイ ヤーでも終局可能 • ただし、少し制約が必要 「眼に打 たない」 • 終局まで simulation するこ とを playout と呼ぶ (造語) 7 7 原始モンテカルロ囲碁 playout による局⾯面評価 [Brügmann 1993] [Bouzy, Cazenave など 2000ごろ] ⿊黒の⼿手番 ⽩白の⼿手番 playout ⿊黒勝ち ⽩白勝ち 8 8 もちろん、 原始モンテカルロ囲碁は弱い • playout の回数が多ければ強くなるという期待 • しかし、深さが2段以上の⽊木に対しては、最善⼿手を 返す保証がない (無限の計算時間があっても) • 相⼿手のミスに期待した⼿手を打つ特徴がある • 正しい応⼿手の数が少ない場合は特にその傾向が 強い • どのくらいが強さの限界か調べた論論⽂文あり • GNU Go 相⼿手の勝率率率は1割くらいだったようです H.Yoshimoto, K.Yoshizoe, T. Kaneko, A. Kishimoto, and K. Taura Monte Carlo Go Has a Way to Go, AAAI06, 9 9 モンテカルロ⽊木探索索 Monte Carlo Tree Search [R. Coulom 2006, cf. CrazyStone] 「有望な」⼿手で多く の playout を実⾏行行 playout の回数が 閾値を超えた 節点を展開 10 10 「有望」とは？の答え：UCB [P. Auer, N. Cesa-Bianchi and P. Fischer 2002] w : 報酬の合計=勝ち数 s : コインの数=playout数 t : コインの総数=総playout数 w + s mean 2 ln t s bias Multi-Armed Bandit Problem Upper Confidence Bound 値が⾼高い節点を 「有望な」節点とする 11 11 UCTアルゴリズム [L. Kocsis and C. Szepezvári 2006] 1 3 1, UCB値の⾼高い枝をたどって 2 末端まで⾏行行く 2, 末端で1回プレイアウト 3, たどった経路路上の勝率率率を更更新 (最適解に収束する証明あり) 12 12 2006年年5⽉月, Coulom MCTSの進歩 囲碁プログラムCrazyStoneが登場 Monte Carlo Tree Search の成⽴立立。9路路盤で成功 2006年年9⽉月, Kocsis and Szepesvári [ECML2006] UCT アルゴリズムが発表される Monte Carlo Tree Search の理理論論化 2006年年11⽉月, Gelly,Wang, Munos, Teytaud 囲碁プログラム MoGo の登場 19路路盤でも成功。playout の強化 13 13 ⼿手持ちの道具 スーパー コンピュータ 分散並列探索 + アルゴリズム 分散ハッシュ 深さ優先型 テーブル モンテカルロ木探索 TDS-‐‑‒df-‐‑‒UCT アルゴリズム K.Yoshizoe, A. Kishimoto, T. Kaneko, H.Yoshimoto and Y. Ishikawa. Scalable Distributed Monte-Carlo Tree Search. SoCS 2011. 14 14 1000 速度向上 1200 TDS-‐‑‒df-‐‑‒UCTの性能 仮想ゲーム木が対象 600〜～750倍の速度度向上 800 既存⼿手法だと数⼗十倍 の速度度向上が限界 分岐8 600 分岐40 分岐150 400 (囲碁相当) 200 0 12 core / node (Xeon 2.93GHz x 2) QDR Infiniband x 2 (80 Gbps) Image provided by Tokyo Institute of Technology Photographer: Takahiro Uozumi 0 200 400 600 800 コア数 TSUBAME2 supercomputer 1000 1200 4,800コアまでは実験済み 囲碁版はデバッグ中 15 15 現状の進捗 • • 選択肢1 (今はこちら） • • 既存の囲碁プログラム (fuego) を並列列化 (デバッグ中) • • fuego の開発者は共同研究者 Prof. Martin Mueller @ Alberta University さらに機械学習などによって強化予定 選択肢2 • • 全て⾃自分で書く 詳細は未定 16 16 この研究の (囲碁以外の) • • • 意義 近い未来の計算機における並列列化 • PCI Express ボード上に数⼗十〜～数百のコア • • GPU, Xeon Phi (Intel MIC) ⼤大量量のコアと、遠いメモリ 分散メモリスパコンで動くアルゴリズムなら、上記の環 境でも動く期待が持てる その他の分野にも貢献 • グラフ探索索, SAT solver, 制約充⾜足問題など 17 17