モンテカルロ木探索
探索と知識利用のバランスを取る1つの方法は、Levente Kocsis と Csaba Szepesvári が2006年に発表した UCT(木に適用したUpper Confidence Bound 1)である。UCT は Auer, Cesa-Bianchi, Fischer が2002年に発表した UCB1 (Upper Confidence Bound 1) に基づく方法である。Kocsis と Szepesvári は w n + c ln  N n {\displaystyle {\frac {w}{n}}+c{\sqrt {\frac {\ln N}{n}}}} が最大となる子ノードを選択することを提案している。各変数は以下の通り。
w は勝った回数
n はこのノードのシミュレーションの回数
N は全シミュレーション回数
c は定数。理論上は 2 {\displaystyle {\sqrt {2}}} であるが、実際は探索が上手く行くように調整する。
第1項の勝率は知識利用である。第2項は探索を表現していて、シミュレーション回数が少ないのを選択するようにする。