モンテカルロ木探索
PUCT は David Auger, Adrien Couetoux, Olivier Teytaud が2013年に発表した手法。
木は根は決断ノードとし、決断ノードとランダムノードを交互に繰り返す形で構築する。決断ノードで行為 a を選択し、ランダムノードに遷移する。
決断ノード z を選択した場合、 ⌊ n ( z ) α ⌋ > ⌊ ( n ( z ) − 1 ) α ⌋ {\displaystyle \lfloor n(z)^{\alpha }\rfloor >\lfloor (n(z)-1)^{\alpha }\rfloor } ならば、そのノードでシミュレーションを行う さもなければ V ^ ( z , a ) + n ( z ) e ( d ) n ( z , a ) {\displaystyle {\hat {V}}(z,a)+{\sqrt {\frac {n(z)^{e(d)}}{n(z,a)}}}} が最大となる子ノードを選択する