モンテカルロ木探索
David Silver らが AlphaZero にて2017年に採用した方法は PUCT を更に改変していて、以下の評価値で子ノードを選択する。
Q ( s , a ) + C ( s ) P ( a ∣ s ) N ( s ) 1 + N ( s , a ) {\displaystyle Q(s,a)+C(s)P(a\mid s){\frac {\sqrt {N(s)}}{1+N(s,a)}}}
C ( s ) = log  1 + N ( s ) + c base c base + c init {\displaystyle C(s)=\log {\frac {1+N(s)+c_{\mbox{base}}}{c_{\mbox{base}}}}+c_{\mbox{init}}}
関数は以下の通り。
Q ( s , a ) {\displaystyle Q(s,a)} - 状態 s で行為 a を行った際の平均報酬
P ( a ∣ s ) {\displaystyle P(a\mid s)} - 状態 s で行為 a を選択する確率。ニューラルネットワークの出力
N ( s ) {\displaystyle N(s)} と N ( s , a ) {\displaystyle N(s,a)} - 訪問回数
他のアプローチでは解決不可能または困難な決定問題を、ランダム性を使用するモンテカルロ法で解決する試みは、1940年代に始まった。ブルース・アブラムソンは、1987年の博士論文で、通常の静的評価関数ではなく、ミニマックス法をランダムなゲームプレイアウトに基づく期待結果モデルと組み合わせた。アブラムソンは、期待結果モデルは「正確・高精度で簡単に推定でき、効率的に計算でき、ドメインに依存しないことが示された」と述べた。アブラムソンは、三目並べ、リバーシ、チェスの機械生成の評価関数を詳細に実験した。
この方法は、1989年に、W・エルテル・シューマンとC・ズットナーによって、定理の自動証明の分野に適用され、幅優先探索、深さ優先探索、反復深化などの探索アルゴリズムにおいて、指数関数的な探索時間を改善することが発見された。
1992年、B・ブルークマンは、コンピュータ囲碁のプログラムに初めてそれを採用した。チャンらは、マルコフ決定プロセスモデルのアダプティブマルチステージサンプリング(AMS)アルゴリズムで「適応型」サンプリングを選択して、「再帰的ロールアウトとバックトラック」のアイデアを提案した。AMSは、サンプリング/シミュレーション(モンテカルロ)ツリーの構築におけるUCBベースの探査と開発のアイデアを探求した最初の試みであり、UCT(上位信頼性ツリー)のメインシードだった。