蒙特卡洛树搜索:

UCB(Upper Confidence Bound/上限置信区间):探索-利用(Exploration-Exploitation),基于过去产生的平均回报和对未来期望回报的累加,UCB1值最高的被认为是最有潜力的节点,即那些过去产生过很大价值,或是那些过去没有探索过但可能会产生更大价值的节点。

n代表number of visits,指访问次数

左半式为了找到最大的价值,右半式为了广泛探索可能

Value和迭代次数n均累加

根节点是当前状态
选取根节点的直接子节点中最大的一个行为
蒙特卡洛算法

Minimax算法:

Alpha-Beta剪枝算法: