「モンテカルロ木探索」の版間の差分

削除された内容追加された内容

インライン

2019年4月13日 (土) 11:17時点における版

モンテカルロ木探索（モンテカルロきたんさく、英: Monte Carlo tree search）とは、モンテカルロ法を使った木の探索の事。決定過程に対する、ヒューリスティクス（＝途中で不要な探索をやめ、ある程度の高確率で良い手を導ける）な探索アルゴリズムである。

モンテカルロ木検索の主要な利用例は、コンピューター囲碁・チェス・将棋などのゲームプレイの手を決定する際に使用される。リアルタイムPCゲームや、大富豪、ポーカーなどの相手の手の内が全て分かるわけではないゲームへも使用される。

アルゴリズム

モンテカルロ木探索は、最も良い手を選択するために使われ、ランダムサンプリングの結果に基づいて探索木を構築する。ゲームでのモンテカルロ木検索は、最後までプレイしたシミュレーション結果に基づいて構築する。ゲームの勝敗の結果に基づいてノードの値を更新して、最終的に勝率が高いことが見込まれる手を選択する。

最も単純な方法は、それぞれの有効な選択肢に、同数ずつプレイアウトの回数を一様に割り振って、最も勝率が良かった手を選択する方法である^[1]。これは単純なモンテカルロ木探索（pure Monte Carlo tree search）と呼ばれる。過去のプレイアウト結果に基づき、よりプレイヤーの勝利に結びつく手にプレイアウトの回数をより多く割り振ると探索効率が向上する。

モンテカルロ木探索は4つのステップからなる^[2]。

選択：根Rから始めて、葉ノードLにたどり着くまで、子ノードを選択し続ける。根が現在のゲームの状態で、葉ノードはシミュレーションが行われていないノード。より有望な方向に木が展開していくように、子ノードの選択を片寄らせる方法は、モンテカルロ木探索で重要なことであるが、探索と知識利用の所で後述する。
展開：Lが勝負を決するノードでない限り、Lから有効手の子ノードの中からCを1つ選ぶ。
シミュレーション：Cから完全なランダムプレイアウトを行う。これはロールアウトとも呼ばれる。単純な方法としては、一様分布から手を選択してランダムプレイアウトを実行する。
バックプロパゲーション：CからRへのパスに沿って、プレイアウトの結果を伝搬する。

上記のグラフは各ステップの選択を表している。ノードの数字は、そのノードからのプレイアウトの"勝った回数/プレイアウトの回数"を表している^[3]。Selectionのグラフでは、今、黒の手番である。根ノードの数字は白が21回中11回勝利していることを表している。裏を返すと黒が21回中10回勝利していることを表していて、根ノードの下の3つのノードは手が3種類あることを表していて、数字を合計すると10/21になる。

シミュレーションで白が負けたとする。白の0/1ノードを追加して、そこから根ノードまでのパスの全てのノードの分母（プレイアウトの回数）に1加算して、分子（勝った回数）は黒ノードだけ加算する。引き分けの際は、0.5加算する。こうすることで、プレイヤーは最も有望な手を自分の手番で選択することが出来る。

計算の制限時間に到達するまで、これを反復し、最も勝率が高い手を選択する。

探索と知識利用

子ノードを選択する際の難しい点は、何回かのプレイアウトの結果により高い勝率であるという知識利用（英: exploitation）とプレイアウトの回数が不足してるので探索（英: exploration）することのバランスを取ることである。

UCT (Upper Confidence Tree)

探索と知識利用のバランスを取る1つの方法は、Levente Kocsis と Csaba Szepesvári が2006年に発表した UCT（木に適用したUpper Confidence Bound 1）である^[4]。UCT は Auer, Cesa-Bianchi, Fischer が2002年に発表した UCB1 (Upper Confidence Bound 1)^[5] に基づく方法である。Kocsis と Szepesvári は ${\frac {w}{n}}+c{\sqrt {\frac {\ln N}{n}}}$ が最大となる子ノードを選択することを提案している。各変数は以下の通り。

w は勝った回数
n はこのノードのシミュレーションの回数
N は全シミュレーション回数
c は定数。理論上は ${\sqrt {2}}$ であるが、実際は探索が上手く行くように調整する。

第1項の勝率は知識利用である。第2項は探索を表現していて、シミュレーション回数が少ないのを選択するようにする。

PUCT (Polynomial Upper Confidence Tree)

PUCT は David Auger, Adrien Couetoux, Olivier Teytaud が2013年に発表した手法^[6]。

木は根は決断ノードとし、決断ノードとランダムノードを交互に繰り返す形で構築する。決断ノードで行為 a を選択し、ランダムノードに遷移する。

決断ノード z を選択した場合、
- $\lfloor n(z)^{\alpha }\rfloor >\lfloor (n(z)-1)^{\alpha }\rfloor$ ならば、そのノードでシミュレーションを行う
- さもなければ ${\hat {V}}(z,a)+{\sqrt {\frac {n(z)^{e(d)}}{n(z,a)}}}$ が最大となる子ノードを選択する
ランダムノード w を選択した場合、
- $\lfloor n(w)^{\alpha }\rfloor =\lfloor (n(w)-1)^{\alpha }\rfloor$ ならば、最も訪れていない子ノードを選択する
- さもなければ、新しい子ノードを作成する

関数は以下の通り。

$n(z)$ - 決断ノード z の訪問回数
$n(z,a)$ - 決断ノード z で行為 a を選択した際のランダムノードの訪問回数
${\hat {V}}(z,a)$ - 決断ノード z で行為 a を選択した際のランダムノードでの平均報酬（勝率など）
$\alpha (d)$ - 深さ d に対して定めた progressive widening 係数（定数）
$e(d)$ - 深さ d に対して定めた探索係数（定数）

参照

^ Brügmann, Bernd (1993). Monte Carlo Go. Technical report, Department of Physics, Syracuse University
^ G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). “Progressive Strategies for Monte-Carlo Tree Search”. New Mathematics and Natural Computation 4 (3): 343–359. doi:10.1142/s1793005708001094.
^ Bradberry, Jeff (2015年9月7日). “Introduction to Monte Carlo Tree Search”. 2019年4月12日閲覧。
^ Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4212. Springer. pp. 282–293. CiteSeerX 10.1.1.102.1296. doi:10.1007/11871842_29. ISBN 3-540-45375-X。
^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). “Finite-time Analysis of the Multiarmed Bandit Problem”. Machine Learning 47 (2/3): 235–256.
^ Auger, David; Couetoux, Adrien; Teytaud, Olivier (2013). “Continuous Upper Confidence Trees with Polynomial Exploration - Consistency”. Machine Learning and Knowledge Discovery in Databases (Springer Berlin Heidelberg) 8188: 194-209. doi:10.1007/978-3-642-40988-2_13.

この項目は、確率論に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

[Bruegmann-1] Brügmann, Bernd (1993). Monte Carlo Go. Technical report, Department of Physics, Syracuse University

[chaslot2008-2] G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). “Progressive Strategies for Monte-Carlo Tree Search”. New Mathematics and Natural Computation 4 (3): 343–359. doi:10.1142/s1793005708001094.

[3] Bradberry, Jeff (2015年9月7日). “Introduction to Monte Carlo Tree Search”. 2019年4月12日閲覧。

[Kocsis-Szepesvari-4] Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4212. Springer. pp. 282–293. CiteSeerX 10.1.1.102.1296. doi:10.1007/11871842_29. ISBN 3-540-45375-X。

[5] Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). “Finite-time Analysis of the Multiarmed Bandit Problem”. Machine Learning 47 (2/3): 235–256.

[6] Auger, David; Couetoux, Adrien; Teytaud, Olivier (2013). “Continuous Upper Confidence Trees with Polynomial Exploration - Consistency”. Machine Learning and Knowledge Discovery in Databases (Springer Berlin Heidelberg) 8188: 194-209. doi:10.1007/978-3-642-40988-2_13.

[1]

[2]

[3]

[4]

[5]

[6]

@@ 23行目: / 23行目: @@
 == 探索と知識利用 ==
-子ノードを選択する際の難しい点は、何回かのプレイアウトの結果により高い勝率であるという知識利用（{{lang-en-short|exploitation}}）とプレイアウトの回数が不足してるので探索（{{lang-en-short|exploration}}）することのバランスを取ることである。探索と知識利用のバランスを取る1つの方法は、Levente Kocsis と Csaba Szepesvári が発表した、UCT（木に適用したUpper Confidence Bound 1）である<ref name="Kocsis-Szepesvari">{{cite conference |last=Kocsis|first=Levente|last2=Szepesvári|first2=Csaba|title=Bandit based Monte-Carlo Planning|editor-first=Johannes|editor-last=Fürnkranz|editor2-first=Tobias|editor2-last=Scheffer|editor3-first=Myra|editor3-last=Spiliopoulou |booktitle=Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings|series=Lecture Notes in Computer Science |volume=4212|publisher=Springer|isbn=3-540-45375-X |pages=282–293|year=2006|doi=10.1007/11871842_29|citeseerx=10.1.1.102.1296}}</ref>。UCT は Auer, Cesa-Bianchi, Fischer が発表した UCB1 (Upper Confidence Bound 1)<ref>{{cite journal |last=Auer |first=Peter|last2=Cesa-Bianchi|first2=Nicolò|last3=Fischer|first3=Paul|title=Finite-time Analysis of the Multiarmed Bandit Problem|journal=Machine Learning|volume=47|issue=2/3|pages=235–256 |year=2002 |url=https://link.springer.com/content/pdf/10.1023/A:1013689704352.pdf}}</ref> に基づく方法である。Kocsis と Szepesvári は <math>\frac{w}{n} + c \sqrt{\frac{\ln N}{n}}</math> が最大となる子ノードを選択することを提案している。各変数は以下の通り。
+子ノードを選択する際の難しい点は、何回かのプレイアウトの結果により高い勝率であるという知識利用（{{lang-en-short|exploitation}}）とプレイアウトの回数が不足してるので探索（{{lang-en-short|exploration}}）することのバランスを取ることである。
+=== UCT (Upper Confidence Tree) ===
+探索と知識利用のバランスを取る1つの方法は、Levente Kocsis と Csaba Szepesvári が[[2006年]]に発表した UCT（木に適用したUpper Confidence Bound 1）である<ref name="Kocsis-Szepesvari">{{cite conference |last=Kocsis|first=Levente|last2=Szepesvári|first2=Csaba|title=Bandit based Monte-Carlo Planning|editor-first=Johannes|editor-last=Fürnkranz|editor2-first=Tobias|editor2-last=Scheffer|editor3-first=Myra|editor3-last=Spiliopoulou |booktitle=Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings|series=Lecture Notes in Computer Science |volume=4212|publisher=Springer|isbn=3-540-45375-X |pages=282–293|year=2006|doi=10.1007/11871842_29|citeseerx=10.1.1.102.1296|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296}}</ref>。UCT は Auer, Cesa-Bianchi, Fischer が[[2002年]]に発表した UCB1 (Upper Confidence Bound 1)<ref>{{cite journal |last=Auer |first=Peter|last2=Cesa-Bianchi|first2=Nicolò|last3=Fischer|first3=Paul|title=Finite-time Analysis of the Multiarmed Bandit Problem|journal=Machine Learning|volume=47|issue=2/3|pages=235–256 |year=2002 |url=https://link.springer.com/content/pdf/10.1023/A:1013689704352.pdf}}</ref> に基づく方法である。Kocsis と Szepesvári は <math>\frac{w}{n} + c \sqrt{\frac{\ln N}{n}}</math> が最大となる子ノードを選択することを提案している。各変数は以下の通り。
 * w は勝った回数
 * n はこのノードのシミュレーションの回数
@@ 30行目: / 33行目: @@
 第1項の勝率は知識利用である。第2項は探索を表現していて、シミュレーション回数が少ないのを選択するようにする。
+=== PUCT (Polynomial Upper Confidence Tree) ===
+PUCT は David Auger, Adrien Couetoux, Olivier Teytaud が[[2013年]]に発表した手法<ref>{{cite journal
+|last= Auger
+|first= David
+|last2= Couetoux
+|first2= Adrien
+|last3 = Teytaud
+|first3 = Olivier
+|date= 2013
+|title= Continuous Upper Confidence Trees with Polynomial Exploration - Consistency
+|url=
+|journal= Machine Learning and Knowledge Discovery in Databases
+|publisher= Springer Berlin Heidelberg
+|volume= 8188
+|issue=
+|pages= 194-209
+|doi= 10.1007/978-3-642-40988-2_13
+|accessdate=2019-04-13
+}}</ref>。
+木は根は決断ノードとし、決断ノードとランダムノードを交互に繰り返す形で構築する。決断ノードで行為 a を選択し、ランダムノードに遷移する。
+*決断ノード z を選択した場合、
+** <math>\lfloor n(z)^\alpha \rfloor > \lfloor (n(z) - 1)^\alpha \rfloor</math> ならば、そのノードでシミュレーションを行う
+** さもなければ <math>\hat{V}(z,a) + \sqrt{\frac{n(z)^{e(d)}}{n(z,a)}}</math> が最大となる子ノードを選択する
+*ランダムノード w を選択した場合、
+** <math>\lfloor n(w)^\alpha \rfloor = \lfloor (n(w) - 1)^\alpha \rfloor</math> ならば、最も訪れていない子ノードを選択する
+** さもなければ、新しい子ノードを作成する
+関数は以下の通り。
+* <math>n(z)</math> - 決断ノード z の訪問回数
+* <math>n(z, a)</math> - 決断ノード z で行為 a を選択した際のランダムノードの訪問回数
+* <math>\hat{V}(z,a)</math> - 決断ノード z で行為 a を選択した際のランダムノードでの平均報酬（勝率など）
+* <math>\alpha(d)</math> - 深さ d に対して定めた progressive  widening 係数（定数）
+* <math>e(d)</math> - 深さ d に対して定めた探索係数（定数）
 == 参照 ==