モンテカルロ⽊木探索索Monte-Carlo Tree Searchの理理論論と実践

美添  ⼀一樹  Kazuki Yoshizoe

JST ERATO 湊離離散構造処理理系プロジェクト / 東⼯工⼤大IBIS2014 企画セッション
離離散アルゴリズムの機械学習応⽤用

1

⾃自⼰己紹介と概要• 最近の研究テーマ（あるいは世を忍ぶ仮の姿）– 探索索アルゴリズムの⼤大規模並列列化• 本当のテーマ– コンピュータでプロ囲碁棋⼠士に勝つ• 今⽇日はモンテカルロ⽊木探索索の– 成⽴立立の経緯• 最初しばらく囲碁の話– 理理論論と実践• どちらも深くは⽴立立ち⼊入らない– モンテカルロ⽊木探索索を• 使いたい⼈人、理理論論を知りたい⼈人• 両⽅方に役⽴立立つと良良いと思っています2

IBM 1997
Kasparov
DeepBlue

2012~14電王戦

2013〜～14 電聖戦
4⼦子でプロと2勝2敗

モンテカルロ⽊木探索索の発明
FPGAで将棋プログラムを作ってみるブログ
http://blog.livedoor.jp/yss_fpga/archives/53897129.html

3

2013年年〜～14年年  電聖戦

4⼦子局は、将棋の⾓角落落ちより少し差があるハンデ

プロと4⼦子局で対戦

2年年連続で1勝1敗
参加プログラムは2年年連続でZen と  CrazyStone
電聖戦ウェブサイト
http://entcog.c.ooco.jp/entcog/densei/

従来の探索索アルゴリズム
A*探索索
minimax探索索(αβ探索索)モンテカルロ⽊木探索索(MCTS)

評価関数で評価各節点の数値の⽐比較

ランダムシミュレーションの結果で評価[Coulom 2006] CrazyStone

評価関数無しでも探索索できる画期的な発明
囲碁のために開発

各節点の持つ確率率率分布の⽐比較

4

囲碁の評価関数の難しさ
良良い評価関数は、正確で⾼高速でないといけない

駒の価値のような⼿手がかりがない
オセロの隅ほど特徴のある場所がない

囲碁の評価関数を作れた⼈人は居ない途中で終局図を予想するのも困難

56乱数を使って囲碁を打つ
乱数を使って、多数の終局図を作り、勝敗を記録

これをプレイアウトと呼ぶ
便便宜上この⽅方法を原始モンテカルロ囲碁と呼ぶことにする

⿊黒
2勝1敗
注：眼を残す7[Brügmann 1993]

原始モンテカルロ囲碁

凡例例

⿊黒の⼿手番
⽩白の⼿手番
⿊黒勝ちの          プレイアウト
⽩白勝ちの          プレイアウト

4勝1敗

3勝2敗

2勝3敗

⼀一番勝てそうな⼿手を選ぶ
注：この⽅方法は弱い
注：いくら時間を掛けても最善⼿手は分からない8

原始モンテカルロ囲碁を改良良原始モンテカルロ囲碁はそのままだと弱い
相⼿手のミスに期待した⼿手を打つ
⾶飛⾞車車の頭に歩を打つような⼿手

そこで、良良さそうな所を深く読むように改良良
これがモンテカルロ⽊木探索索プログラムCrazyStone [Coulom 2006]

プレイアウト数が閾値以上なら展開

MCTS の応⽤用

9

囲碁の研究が様々な応⽤用に貢献

single player game(real time game)[H. Nakhost and M. Müller 2009]“Monte-Carlo Exploration for
Deterministic Planning”, IJCAI’09

multi player gamePlanningbiometric security[Tanabe, Yoshizoe and Imai 2009]“A study on security evaluation methodology forimage-based biometrics authentication systems”

two playergame[Cazenave, Balbo, Pinson 2009]“Monte-Carlo bus regulation”

⾃自然⾔言語処理理

scheduling[Chevelu, Putois, Lepage 2010]“The true score of statistical paraphrase generation”

あらためて発表の概要
モンテカルロ⽊木探索索Monte-Carlo Tree Search (MCTS)
囲碁のために開発
評価関数不不要

汎⽤用性が⾼高く
様々な問題に応⽤用

MCTSの理理論論: Multi-Armed Bandit と⽊木探索索
MCTSの実践: 機械学習や職⼈人芸で強化
MCTSの得意、不不得意

MCTS の並列列化

1011[Robbins 1952][Lai and Robbins 1984]

Multi-Armed Bandit と囲碁[Auer, Cesa-Bianchi, Fischer 2002]

UCB1 アルゴリズム
cumulative regretを最⼩小化する

w
2 ln t+ss

mean項 + bias項
w : その腕の報酬
s : 投⼊入したコイン
t : s の合計

MAB と    原始モンテカルロ囲碁
腕

合法⼿手

コイン

プレイアウト

コインの枚数考慮時間

regret 最⼩小化が⽬目的? 最善⼿手が⽬目的

[Kocsis, Szepesvári 2006]

UCT algorithm

Upper Confidence bound applied to Trees
節点の⽐比較にUCB1を⽤用いる

⽊木探索索アルゴリズムw
2 ln t+ss
証明あり
プレイアウト数  n に対し、w⎛ log n ⎞+ O⎜⎟s⎝ n ⎠

また、1⼿手⽬目が間違える確率率率は  0 に収束．
つまり(いずれは)最善⼿手が分かる

値が最⼤大の枝をたどる（末端の節点を展開）
末端でプレイアウト
経路路上の節点を更更新

繰り返し

12

13

UCB1, UCT: 証明関連の補⾜足報酬が  [0, 1] なら  c=1 で証明成⽴立立[Auer, Cesa-Bianchi and fischer 2002]

UCB1の証明

Chernoff bound を⽤用いる[Kocsis, Szepesvári 2006]

UCTの証明各部分⽊木を確率率率過程とみなす
Hoeffding-Azuma 不不等式を⽤用いる
値域が [0, 1] より広がると(c=1のままでは) 証明は不不成⽴立立
1回プレイアウトするごとに更更新しないと証明は不不成⽴立立

exploration constantw
2 ln t+css

実践的には問題に合わせて  c を調整する
囲碁なら、強くすると⼤大抵  c の値は⼩小さくなる
実際には、収束するかどうか気にする開発者は少ない（というかいない？）

14

MCTS の実践（囲碁）
9路路盤ならそこまで弱くないが19路路盤だと壊滅的に弱い

プレイアウトがpure random では弱いw
2 ln t+css

信頼がおけない腕をbias項が優遇

この効果があればある程度度うまく⾏行行く
機械学習や職⼈人芸で強化

UCB1 は別に最善じゃない

強いプログラムは使わない
19路路盤
(正式)

囲碁の知識識や謎のヒューリスティックでbias項をおきかえる。実は  c は 09路路盤
証明？何それおいしいの？

15

⽊木探索索
ほぼ共通

プレイアウト
問題ごとに取り替える

single player

枠組みは汎⽤用性が⾼高い

multiplayerscheduling

two player

planning
biometric security

MCTS の汎⽤用性評価関数を・作れない・作るのがめんどくさい等の時にも効率率率よく探索索
もちろん、何でもできる
万能のツールではない

MCTS の得意、不不得意は？
例例えば、

囲碁は得意
将棋は苦⼿手16

MCTSの得意、不不得意（その1）

プレイアウトの作りやすさ
囲碁

候補⼿手が減っていくので⾃自然と終局する（簡単な制約は必要）

将棋

ランダムなプレイで⾃自然な終局図を迎えることは困難

プレイアウトで「⾃自然な」報酬が得られるかどうかが問題
何が「⾃自然」か考えると難しいが…

注意：MCTS 将棋は初段よりは強い初段あるのに苦⼿手とは⽣生意気な…

MCTSの得意、不不得意（その2）

苦⼿手な形の⽊木

MCTSの弱点

17(trap, だまし構造)

確率率率的な探索索なので細い⼀一本道は苦⼿手
理理論論的解析の例例  [Coquelin, Munos 2007]    ⼈人⼯工的に苦⼿手な⽊木を作れば    ほとんどいくらでも収束を遅くできる

実践的解析の例例  [Ramanujan, Selman 2011]    同じゲームでも序盤は得意    中盤は苦⼿手という例例

囲碁は五段

将棋は初段

負

負負負勝
囲碁でも⼀一本道はある囲碁ではどう対処？

負18

シチョウ

「シチョウ」
負

分かりやすい⼀一本道
⽊木探索索は⼀一般には深い⼿手順が苦⼿手（選択肢の多い局⾯面は得意）プレイアウトは深い⼿手順もOK（選択肢の多い局⾯面は苦⼿手）

負負負

負
勝

プレイアウトが⽊木探索索の弱点を補うのが理理想19[Coulom 2007]

⼈人間の棋譜から学習

数千〜～数⼗十万の  feature の重みを調整
盤端からの距離離2

直前の⼿手とのマンハッタン距離離1

周囲の  3x3 のパターンアタリをかけられたか
この特徴がシチョウ対策

いいえ

候補⼿手の重みは特徴の重みの積

⼀一番重みの⾼高い⼿手がプロの⼿手と⼀一致する回数を最⼤大化

参考: 将棋の  bonanza メソッドも⼈人間の棋譜との⼀一致率率率を上げるように学習

プレイアウト強化
探索索の枝刈り20

プレイアウト

⽊木探索索

プレイアウトの難しさ
⽊木探索索と組合わせるため挙動の予測が困難（強さ以外の）評価も難しい
プレイアウト単体では「弱い」が⽊木探索索と組合わせると強いという例例あり
cf. Simulation Balancing

プレイアウトの質が強さに直結
⼀一番重要な部分

完全なランダムだと弱い[Silver, Tesauro 2009][Huang, Coulom, Lin 2011]

しかし⼀一番良良く分からない部分

しかしランダム性は必要21

プレイアウトの作り⽅方？
囲碁でも⼆二つの派閥がある

⼈人間の棋譜に学習で似せる派

職⼈人芸で⼿手作りする派

CrazyStone 等  Zen 等

それなりのランダム性
今のところ…

それなりの速さ（1ミリ秒なら⼗十分）
プラス職⼈人芸

要するに、それなりにうまくいけば良良いのでは（投げやりですみませんが本当に分かりません）

22

UCT 以外のMAB[Li, Chu, Langford, Schapire 2010][万代, ⾦金金⼦子 2014]

LinUCB

LinUCT[Garivier, Cappé 2010][??? 2012ごろ]

KL-UCB

KL-UCT[Karnin, Koren, Somekh 2013]

Seq. Halving

⽊木探索索アルゴリズムになってかつ収束の証明がある物はUCTのみ

いろいろあるが、[Cazenave 2014]

SHOT

⽊木探索索

simple regret 最⼩小化

強いプログラムは強くならない

弱いプログラムならUCT より強くなる例例あり[Kocsis, Szepesvári 2007]

Discounted UCB[Hashimoto, Kishimoto, Yoshizoe, Ikeda 2012]

Accelerated-UCT
⼆二⼈人ゲームに特化モンテカルロ⽊木探索索の性質

最近の囲碁プログラム
形勢判断が正確絶対に数え間違えない「地」ではなく勝率率率を最⼤大化するように打つ。よってリードしていると安全に不不利利だと攻撃的に打つ
負けると⾮非常につまらない（勝つと⾯面⽩白い）

局所的な読みが不不正確

詰碁は解けない

重要プレイアウトの報酬をスコアでは無く勝ち=1, 負け=0 とする
他のアルゴリズム  (αβ探索索)
だとこれが⾮非常に難しい

23

考慮時間が短い
探索索には厳しい24

モンテカルロ⽊木探索索の性質

リアルタイムゲームの例例

Ms. Pac-Man AI Competition○○○AI Competition

MCTS を⽤用いたプログラムが世界記録を更更新  [Ikehata, Itoh 2011]

某有名アクションゲームのクローンを使ったAI⼤大会挟み撃ちをさけるように作られたプレイアウトを使って  MCTS

「⼈人間のプレイに似せる部⾨門」(Turing Track)
A*探索索と  MCTS を⽐比較  （動画）Ms. Pac-Man 1/15秒ごとに⾏行行動[Baumgarten 2009?] [中野, 美添, 脇⽥田 2013]○○○

http://cswww.essex.ac.uk/staff/sml/pacman/PacManContest.html

プライバシに配慮しています

1/24秒ごとに⾏行行動

http://www.platformersai.com/

25

MCTS の並列列化: Root 並列列化
異異なる乱数シードで複数の探索索を⾏行行う
深さ 1〜～3 程度度の部分を共有する
少し⼯工夫すると16ノードくらいまでは有効
探索索の並列列化は難しいのでこれでもそれなりに良良い

参考: SAT solver の portfolio 並列列化

26

0 1 2 3

我々の並列列化⼿手法

均等な負荷分散が可能[Romein et al. 1999]

TDS

分散ハッシュテーブル
による並列列探索索⼿手法

グラフの各節点を、異異なる計算ノードに割り当てる
ノード番号= 3[吉本, 岸本, ⾦金金⼦子, 美添, ⽥田浦 2007]

df-UCT

depth-first reformulation（深さ優先変形）

アルゴリズムの深さ優先変形によって通信の集中を回避する
r011001 11 01001011

fc

ノード番号= 1101100 01 10001110

adbge

27

補⾜足1: 評価関数＋プレイアウト
プレイアウトは終局する必要はない
数⼿手進めて評価関数を呼ぶ⽅方法もありうる評価関数が不不正確な場合に強化することが可能
ここで評価関数（かもしれない）

Amazons（という検索索しにくいゲーム）などで成功例例あり

28

補⾜足2：合流流への対処 10?

231368?

?

?

?

20

711142302

合流流があるとmean項の定義が難しい

2558134514252
302

節点ではなく枝が報酬を持つ

簡単だし、収束もする[Childs, Brodeur, Kocsis 2008] ただし無駄はある
もっと良良い⽅方法、求むモンテカルロ⽊木探索索Monte-Carlo Tree Search (MCTS)
囲碁のために開発
評価関数不不要

汎⽤用性が⾼高く
様々な問題に応⽤用

理理論論: MAB と⽊木探索索

実践: 機械学習と職⼈人芸

得意、不不得意がある

並列列化は有望囲碁を強くしたい

さらに多くの研究者の参⼊入求む

29