モンテカルロ木探索

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

モンテカルロ木検索は、主に囲碁・チェス・将棋などのゲームの次の着手の決定などに使用される。また、リアルタイムPCゲームや、大富豪、ポーカーなどの相手の手の内が全て分かるわけではないゲームへも使用される。

歴史

モンテカルロ法

他のアプローチでは解決不可能または困難な決定問題を、ランダム性を使用するモンテカルロ法で解決する試みは、1940年代に始まった。ブルース・アブラムソンは、1987年の博士論文で、通常の静的評価関数ではなく、ミニマックス法をランダムなゲームプレイアウトに基づく期待結果モデルと組み合わせた^[1]。アブラムソンは、期待結果モデルは「正確・高精度で簡単に推定でき、効率的に計算でき、ドメインに依存しないことが示された」と述べた^[1]。アブラムソンは、三目並べ、リバーシ、チェスの機械生成の評価関数を詳細に実験した^[1]。

この方法は、1989年に、W・エルテル・シューマンとC・ズットナーによって、定理の自動証明の分野に適用され、幅優先探索、深さ優先探索、反復深化などの探索アルゴリズムにおいて、指数関数的な探索時間を改善することが発見された^[2][3][4]。

1992年、B・ブルークマンは、コンピュータ囲碁のプログラムに初めてそれを採用した^[5]。チャンら^[6]は、マルコフ決定プロセスモデルのアダプティブマルチステージサンプリング（AMS）アルゴリズムで「適応型」サンプリングを選択して、「再帰的ロールアウトとバックトラック」のアイデアを提案した。AMSは、サンプリング/シミュレーション（モンテカルロ）ツリーの構築におけるUCBベースの探査と開発のアイデアを探求した最初の試みであり、UCT（上位信頼性ツリー）のメインシードだった^[7]。

モンテカルロ木検索

→「コンピュータ囲碁」も参照

2006年、これらの研究に触発されて^[8]、レミ・クーロンは、ゲームツリー検索へモンテカルロ法を適用させ、「Monte Carlo tree search（モンテカルロ木検索）」と命名した^[9]。L・コチシュとCs・セーペスヴァーリはUCT（ツリーに適用される上限信頼限界）アルゴリズム^[10]を開発した。S・ゲーリーらは、彼らのプログラムMoGoにUCTを実装した^[11]。2008年にMoGoは9路盤の囲碁でアマチュア有段者の域に到達し、Fuegoは9路盤でアマチュアの強豪プレーヤーに勝ち始めた^[12]。

2012年1月、モンテカルロ木探索を導入したZenは、19路盤のアマチュア二段のプレーヤーとの番勝負に3対1で勝利した^[13] 。また、クーロンが開発に携わっているCrazy Stoneも2014年の第2回電聖戦で依田紀基九段に19路盤の4子局の置き碁（ハンデ戦）で勝利するなど、着実に進歩していった^[14]。それでもなおトップ棋士に勝てるようになるには10年以上かかると考えられていたが^[15]、2016年1月、Google DeepMind社は開発を進めていたAlphaGoについて公表した。AlphaGoは2015年10月に樊麾二段に19路盤でハンディキャップなしに勝利しており、初めてプロ棋士に互先で勝利したコンピュータ碁プログラムになっていた^[16][17][18]。2016年3月、AlphaGoは国際棋戦優勝多数の李世乭九段を相手に5番勝負を行い、4勝1敗で勝利した（詳細はAlphaGo対李世乭を参照）^[19]。AlphaGoは、以前の囲碁プログラムを大幅に改善しただけでなく、機械学習は、ポリシー（移動選択）と値に人工ニューラルネットワーク（ディープラーニング手法）を使用したモンテカルロ木検索を使用したため、以前のプログラムをはるかに上回る効率が得られた^[20]。

MCTSアルゴリズムは、他のボードゲーム（例えば、ヘックス^[21] 、ハバナ（英語版）^[22]、アマゾンズ（英語版）^[23]、アリマア^[24]）、リアルタイムビデオゲーム（例えばパックマン^[25][26]、Fable Legends（英語版）^[27]）、不完全情報ゲーム（スカート^[28]、 ポーカー^[29]、マジック・ザ・ギャザリング^[30]、カタンの開拓者たち^[31]）などに応用された。

AlphaGo登場以降はディープラーニングを利用したプログラムが主流となったが、モンテカルロ木探索を利用したプログラムの開発も一部で行われている^[32]。

アルゴリズム

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

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

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

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

モンテカルロ木探索の4つのステップ

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

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

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

探索と知識利用

子ノードを選択する際の難しい点は、何回かのプレイアウトの結果により高い勝率であるという知識利用（英: exploitation）とプレイアウトの回数が不足してるので探索（英: exploration）することのバランスを取ることである。手法は無数にあり Cameron B. Browne らが2012年2月までに発表された物を論文にまとめている^[35]。

UCT (Upper Confidence Tree)

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

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

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

PUCT (Polynomial Upper Confidence Tree)

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

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

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

関数は以下の通り。

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

AlphaZero

David Silver らが AlphaZero にて2017年に採用した方法は PUCT を更に改変していて、以下の評価値で子ノードを選択する^[38]。

${\displaystyle Q(s,a)+C(s)P(a\mid s){\frac {\sqrt {N(s)}}{1+N(s,a)}}}$

${\displaystyle C(s)=\log {\frac {1+N(s)+c_{\mbox{base}}}{c_{\mbox{base}}}}+c_{\mbox{init}}}$

関数は以下の通り。

• ${\displaystyle Q(s,a)}$ - 状態 s で行為 a を行った際の平均報酬
• ${\displaystyle P(a\mid s)}$ - 状態 s で行為 a を選択する確率。ニューラルネットワークの出力
• ${\displaystyle N(s)}$ と ${\displaystyle N(s,a)}$ - 訪問回数