モンテカルロ木探索

モンテカルロ木探索

クラス	検索アルゴリズム

コンピュータサイエンスにおいて、モンテカルロ木探索( MCTS ) は、いくつかの種類の意思決定プロセス、特にボードゲームをプレイするソフトウェアで使用されるプロセスのためのヒューリスティック 探索アルゴリズムです。そのコンテキストでは、MCTS はゲームツリーを解くために使用されます。

MCTSは2016年にニューラルネットワークと組み合わせられ^[1]、チェス、将棋、^[2] チェッカー、バックギャモン、コントラクトブリッジ、囲碁、スクラブル、クロバー^[3]などの複数のボードゲームや、ターン制戦略ビデオゲーム（ Total War: Rome IIの高レベルキャンペーンAIの実装^[4]など）やゲ​​ーム以外のアプリケーションにも使用されています。^[5]

他のアプローチでは解決が困難または不可能な決定論的問題にランダムサンプリングを使用するモンテカルロ法は、 1940年代にまで遡ります。 ^[6]ブルース・エイブラムソンは、1987年の博士論文で、通常の静的評価関数の代わりに、最後までランダムにゲームが展開されることに基づく期待結果モデルとミニマックス探索を組み合わせました。エイブラムソンは、期待結果モデルは「正確で、正確で、簡単に推定でき、効率的に計算でき、ドメインに依存しないことが示されている」と述べています。^[7]彼は三目並べ で徹底的に実験し、次にオセロとチェスで機械生成の評価関数を試しました。

このような方法は、1989年にW. Ertel、J. Schumann、C. Suttnerによって自動定理証明の分野でヒューリスティック探索に研究され、うまく適用されました。^{[8] [9] [10]}これにより、幅優先探索、深さ優先探索、反復深化などの非情報探索アルゴリズムの指数関数的な探索時間が改善されました。

1992年、B. Brügmannが初めて囲碁プログラムにこれを採用しました。^[11] 2002年、Changら^[12]は、マルコフ決定過程のモデルに対する適応型多段サンプリング（AMS）アルゴリズムで、「適応型」サンプリング選択による「再帰的ローリングアウトとバックトラッキング」というアイデアを提案しました。AMSは、サンプリング/シミュレートされた（モンテカルロ）ツリーの構築におけるUCBベースの探索と活用というアイデアを探求した最初の研究であり、UCT（Upper Confidence Trees）の主な種となりました。^[13]

2006年、これらの先駆者たちに触発されて、^[15] Rémi Coulom はモンテカルロ法のゲームツリー探索への応用を説明し、モンテカルロツリー探索という名前を作り出した。^[16] L. Kocsis と Cs. Szepesvári は UCT (Upper Confidence bounds applied to Trees) アルゴリズムを開発し、^[17] S. Gelly らは UCT をプログラム MoGo に実装した。^[18] 2008年、MoGo は9×9 囲碁で段位(マスター) レベルを達成し、^[19] Fuego プログラムは 9×9 囲碁で強豪アマチュアプレイヤーに勝ち始めた。^[20]

2012年1月、Zenプログラムは19×19の碁盤上でアマチュア2段のプレイヤーと3対1で勝利した。^[21] Google DeepmindはプログラムAlphaGoを開発し、2015年10月にフルサイズの19×19の碁盤でハンディキャップなしでプロの人間の囲碁プレイヤーに勝利した最初のコンピュータ囲碁プログラムとなった。^{[1] [22] [23] 2016年3月、AlphaGoは}5ゲームの試合でイ・セドルを4対1で破ったことで、19×19囲碁の名誉九段（マスター）レベルを授与された。 ^[24] AlphaGoは、以前の囲碁プログラムから大幅に改善されただけでなく、機械学習のマイルストーンでもあります。ポリシー（移動選択）と価値に人工ニューラルネットワーク（ディープラーニング手法）を使用したモンテカルロ木探索を使用しており、以前のプログラムをはるかに上回る効率を実現しています。^[25]

MCTSアルゴリズムは、他のボードゲーム（例えばHex ^[26] 、Havannah ^[27] 、Game of the Amazons ^[28]、Arimaa ^[29]）、リアルタイムビデオゲーム（例えばMs. Pac-Man ^{[30] [31]}、Fable Legends ^[32]）、非決定性ゲーム（skat ^[33]、 ポーカー[ ^34] 、Magic: The Gathering ^[35]、またはSettlers of Catan ^[36]など）をプレイするプログラムでも使用されています。

MCTS の焦点は、最も有望な動きを分析すること、検索空間のランダム サンプリングに基づいて検索ツリーを拡張することにあります。ゲームでのモンテ カルロ ツリー検索の適用は、ロールアウトとも呼ばれる多数のプレイアウトに基づいています。各プレイアウトでは、動きをランダムに選択してゲームを最後までプレイします。各プレイアウトの最終的なゲーム結果を使用して、ゲーム ツリーのノードに重み付けが行われ、将来のプレイアウトでより良いノードが選択される可能性が高くなります。

プレイアウトを使用する最も基本的な方法は、現在のプレイヤーの合法的な動きの後に同じ数のプレイアウトを適用し、最も多くの勝利につながった動きを選択することです。^{[11]この方法（}純粋なモンテカルロゲーム検索と呼ばれます）の効率は、以前のプレイアウトに従って現在のプレイヤーの勝利につながる動きに多くのプレイアウトが割り当てられるため、時間の経過とともに増加することがよくあります。モンテカルロツリー検索の各ラウンドは、4つのステップで構成されます。^[37]

• 選択: ルートRから開始し、リーフ ノードLに到達するまで連続する子ノードを選択します。ルートは現在のゲーム状態であり、リーフは、シミュレーション (プレイアウト) がまだ開始されていない潜在的な子を持つノードです。以下のセクションでは、モンテ カルロ ツリー検索の本質である、ゲーム ツリーを最も有望な動きに向けて拡張できるようにする子ノードの選択をバイアスする方法について詳しく説明します。
• 拡張: L がどちらかのプレイヤーにとって決定的にゲームを終了しない限り(例: 勝ち/負け/引き分け)、 1 つ (または複数) の子ノードを作成し、そのうちの 1 つからノードC を選択します。子ノードは、 Lによって定義されたゲーム位置からの有効な移動です。
• シミュレーション: ノードCから 1 つのランダム プレイアウトを完了します。このステップは、プレイアウトまたはロールアウトと呼ばれることもあります。プレイアウトは、ゲームが決まる (たとえば、チェスでは、ゲームは勝ち、負け、または引き分けになります) まで、均一なランダムな動きを選択するのと同じくらい単純な場合があります。
• バックプロパゲーション: プレイアウトの結果を使用して、 CからRへのパス上のノードの情報を更新します。

このグラフは、1 つの決定に含まれる手順を示しており、各ノードは、そのノードが表すプレイヤーのゲーム ツリーのその時点からの合計プレイアウトに対する勝利の比率を示しています。^[38]選択図では、黒が今にも動かようとしています。ルート ノードは、この位置からこれまでに 21 回のプレイアウトのうち白が 11 回勝利していることを示しています。これは、その下の 3 つの黒ノードに沿って示されている合計 10/21 の黒の勝利を補完するものであり、各黒ノードは黒の可能な動きを表しています。このグラフは、以下で説明する UCT アルゴリズムに従っていないことに注意してください。

白がシミュレーションに負けた場合、選択中のすべてのノードのシミュレーション回数 (分母) が増加しますが、その中で黒のノードのみが勝利 (分子) としてカウントされます。白が勝った場合、選択中のすべてのノードのシミュレーション回数が増加しますが、その中で白のノードのみが勝利としてカウントされます。引き分けが可能なゲームでは、引き分けにより黒と白の両方の分子が 0.5 増加し、分母が 1 増加します。これにより、選択中に各プレーヤーの選択肢がそのプレーヤーにとって最も有望な動きに向かって拡大し、各プレーヤーの動きの価値を最大化するという目標を反映します。

割り当てられた時間が残っている限り、探索ラウンドが繰り返されます。そして、最も多くのシミュレーションが行われた手 (つまり、最も高い分母) が最終的な答えとして選択されます。

この基本的な手順は、局面が必然的に有限の手数と有限の長さを持つあらゆるゲームに適用できます。各局面について、実行可能なすべての手が決定されます。k回のランダムなゲームが最後までプレイされ、スコアが記録されます。最高スコアにつながる手が選択されます。同点の場合は、公平なコイントスで決着がつきます。純粋なモンテカルロ ゲーム サーチは、ゲームEinStein würfelt nicht!のように、ランダム要素を持ついくつかのゲームで強いプレイをもたらします。ランダムなターン順のボード フィリング ゲームでは、 k が無限大に近づくにつれて最適なプレイに収束します。たとえば、ランダムなターン順のゲームHexなどです。 ^[39] DeepMind の AlphaZero は、シミュレーション ステップをニューラル ネットワークに基づく評価に置き換えます。^[2]

子ノードを選択する際の主な難しさは、平均勝率の高い手の後の深いバリアントの利用と、シミュレーションの少ない手の探索との間でバランスを保つことです。ゲームでの利用と探索のバランスをとるための最初の式は、UCT（ツリーに適用される上部信頼境界1 ）と呼ばれ、Levente KocsisとCsaba Szepesváriによって導入されました。^{[17] UCTは、Auer、Cesa-Bianchi、Fischer [40]}によって導出されたUCB1式と、Chang、Fu、Hu、Marcusによって多段階意思決定モデル（具体的には、マルコフ決定過程）に初めて適用されたおそらく収束するAMS（適応型多段階サンプリング）アルゴリズムに基づいています。 ^[12] KocsisとSzepesváriは、ゲームツリーの各ノードで、式が最高値を持つ手を選択することを推奨しています。この式では、 ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}}$

• w _{i は}i番目の移動後に考慮されるノードの勝利数を表す。
• n _{i は、} i番目の移動後に考慮されるノードのシミュレーションの数を表します。
• N _{i は}、対象ノードの親ノードによって実行されたi番目の移動後のシミュレーションの総数を表します
• cは探索パラメータであり、理論的には√2に等しいが、実際には経験的に選択されることが多い。

上記の式の最初の要素は、活用に対応しており、平均勝率の高い動きでは高くなります。2 番目の要素は探索に対応しており、シミュレーションが少ない動きでは高くなります。

モンテカルロ木探索の最近の実装のほとんどは、UCTの変種に基づいています。そのルーツは、Changら^[12] (2005)がOperations Researchで導入した、有限期間マルコフ決定過程(MDP)の価値関数を推定するAMSシミュレーション最適化アルゴリズムに遡ります。(AMSは、サンプリング/シミュレートされた(モンテカルロ)木の構築におけるUCBベースの探索と活用のアイデアを探求した最初の研究であり、UCTの主な種でした。^[13] )

モンテカルロ木探索における動きの評価はUCTを使用するとミニマックスに収束することが証明されているが、 ^{[17] [41]}モンテカルロ木探索の基本バージョンは、いわゆる「モンテカルロパーフェクト」ゲームでのみ収束する。^{[42]しかし、モンテカルロ木探索は、}アルファベータプルーニングや探索空間を最小化する同様のアルゴリズムに比べて大きな利点がある。

特に、純粋なモンテカルロ木探索では、明示的な評価関数は必要ありません。ゲームの仕組みを実装するだけで、探索空間を探索するのに十分です (つまり、特定の位置で許可される動きの生成とゲーム終了条件)。そのため、モンテカルロ木探索は、理論が発達していないゲームや一般的なゲームプレイで使用できます。

モンテカルロ木探索のゲーム木は、この方法がより有望なサブツリーに集中するため、非対称に成長します。したがって^{[疑わしい–議論する] 、}分岐係数の高いゲームでは、従来のアルゴリズムよりも優れた結果が得られます。

欠点は、特定の局面では、表面的には強いように見えても、実は微妙なプレイの流れによって負けにつながる動きがあるかもしれないということだ。このような「罠状態」は、特に熟練したプレイヤーと対戦する場合、正しく処理するために徹底的な分析を必要とする。しかし、MCTSは選択的ノード拡張のポリシーにより、このような流れを「見る」ことができない。^{[43] [44]これが、}イ・セドルとの4回目の対局でAlphaGoが負けた理由の一部であったと考えられている。本質的には、探索は関連性の低いシーケンスを刈り込もうとする。場合によっては、プレイが非常に特定のプレイの流れにつながる可能性があり、それは重要であるが、ツリーが刈り込まれるときに見落とされ、その結果は「探索レーダーから外れている」。^[45]

検索時間を短縮するために、基本的なモンテカルロ ツリー検索法のさまざまな修正が提案されています。ドメイン固有の専門知識を活用するものもあれば、そうでないものもあります。

モンテカルロ木探索では、軽いプレイアウトと重いプレイアウトのどちらも使用できます。軽いプレイアウトはランダムな動きで構成されますが、重いプレイアウトはさまざまなヒューリスティックを適用して動きの選択に影響を与えます。 ^[46]これらのヒューリスティックでは、以前のプレイアウトの結果（たとえば、Last Good Replyヒューリスティック^[47]）や特定のゲームに関する専門知識が使用される場合があります。たとえば、多くの囲碁プログラムでは、盤面の一部にある特定の石のパターンが、その領域に移動する確率に影響を与えます。^[18]逆説的ですが、シミュレーションで最適ではないプレイをすると、モンテカルロ木探索プログラムが全体的に強くなることがあります。^[48]

ゲームツリーを構築する際には、いくつかのバリアントの活用を助けるために、ドメイン固有の知識が使用されることがある。そのような方法の1つは、各子ノードを作成するときに、勝ったシミュレーションとプレイしたシミュレーションの数に非ゼロの事前確率を割り当て、平均勝率を人為的に上げたり下げたりすることで、選択ステップでノードがそれぞれより頻繁に、またはより頻繁に選択されるようにする。^[49]関連する方法は、プログレッシブバイアスと呼ばれるもので、UCB1式に要素を追加するもので、b _{i は}i番目の動きのヒューリスティックスコアである 。^[37]${\displaystyle {\frac {b_{i}}{n_{i}}}}$

基本的なモンテカルロ木探索では、多くのラウンドを経て初めて最も有望な手を見つけるのに十分な情報が収集されます。それまでは、手は本質的にランダムです。この探索段階は、RAVE ( Rapid Action Value Estimation ) を使用する特定の種類のゲームでは大幅に短縮される可能性があります。^[49]これらのゲームでは、一連の手の組み合わせは同じ位置につながります。通常、これらはボードゲームであり、手にはボード上の駒または石の配置が含まれます。このようなゲームでは、各手の価値は他の手によってわずかに影響を受けるだけです。

RAVE では、特定のゲーム ツリー ノードNについて、その子ノードC _iには、ノードNで開始されたプレイアウトでの勝利の統計だけでなく、ノードNおよびその下位で開始されたすべてのプレイアウトでの勝利の統計も格納されます (プレイアウトにi手が含まれている場合) (また、その手がツリー内でノードNとプレイアウトの間でプレイされた場合)。このように、ツリー ノードの内容は、特定の位置ですぐにプレイされた手だけでなく、後でプレイされた同じ手によっても影響を受けます。

RAVE を使用する場合、選択ステップでは、修正された UCB1 式が最高値を持つノードを選択します。この式では、およびは、移動i を含むプレイアウトの勝利数と移動i を含むすべてのプレイアウト数を表し、関数は、比較的小さいn _iと比較的大きい に対してそれぞれ 1 と 0 に近くなります。D . Silver によって提案された の多くの式のうちの 1 つ^{[50] は}、バランスの取れたポジションでは を取ることができると述べています。ここで、bは経験的に選択された定数です。 ${\displaystyle (1-\beta (n_{i},{\tilde {n}}_{i})){\frac {w_{i}}{n_{i}}}+\beta (n_{i},{\tilde {n}}_{i}){\frac {{\tilde {w}}_{i}}{{\tilde {n}}_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}}$${\displaystyle {\チルダ {w}}_{i}}$${\displaystyle {\チルダ {n}}_{i}}$${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$${\displaystyle {\チルダ {n}}_{i}}$${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$${\displaystyle \beta (n_{i},{\tilde {n}}_{i})={\frac {{\tilde {n}}_{i}}{n_{i}+{\tilde {n}}_{i}+4b^{2}n_{i}{\tilde {n}}_{i}}}}$

モンテカルロ木探索で使用されるヒューリスティックは、多くの場合、多くのパラメータを必要とします。勝率を最大化するためにパラメータを調整する自動化された方法があります。^[51]

モンテカルロ木探索は、多くのスレッドやプロセスで同時に実行することができます。並列実行には、根本的に異なるいくつかの方法があります。^[52]

• リーフ並列化、つまりゲームツリーの 1 つのリーフからの多数のプレイアウトの並列実行。
• ルート並列化、つまり独立したゲームツリーを並列に構築し、これらすべてのツリーのルートレベルのブランチに基づいて移動を実行します。
• ツリー並列化、すなわち同じゲームツリーを並列に構築し、1つのグローバルミューテックス、複数のミューテックス、または非ブロッキング同期を使用して同時書き込みからデータを保護します。^[53]

• AlphaGo は、モンテカルロ木探索、強化学習、深層学習を使用した囲碁プログラムです。
• AlphaGo Zero は、モンテカルロ木探索、強化学習、ディープラーニングを使用した更新された囲碁プログラムです。
• AlphaZero は、モンテカルロ木探索、強化学習、ディープラーニングを使用した AlphaGo Zero の一般化バージョンです。
• Leela Chess Zero は、現在主要なチェス プレイ プログラムの 1 つである AlphaZero のチェス メソッドを実装したフリー ソフトウェアです。

• Cameron Browne、Edward Powley、Daniel Whitehouse、Simon Lucas、Peter I. Cowling、Philipp Rohlfshagen、Stephen Tavener、Diego Perez、Spyridon Samothrakis、Simon Colton (2012 年 3 月)。「モンテ カルロ ツリー検索手法の調査」。IEEE Transactions on Computational Intelligence and AI in Games。4 (1): 1–43。CiteSeerX 10.1.1.297.3086。doi : 10.1109 /tciaig.2012.2186810。S2CID 9316331  。 
• マチェイ・シフィチョフスキ。コンラッド・ゴドルフスキー。バルトシュ・サヴィツキ;ヤツェク・マンジウク（2022年7月）。 「モンテカルロ ツリー検索: 最近の変更とアプリケーションのレビュー」。Springer Nature 人工知能のレビュー。56 (3): 497–2562 (66 ページ)。arXiv : 2103.04931。土井：10.1007/s10462-022-10228-y。S2CID  232147848。

• モンテカルロ木探索の初心者向けガイド