一学一做动漫视频网站,wordpress释放内存,湖南省郴州市天气预报,热门关键字搜索结果一. 什么是蒙特卡洛树搜索
蒙特卡洛树搜索(MCTS)是一种启发式搜索算法#xff0c;一般用在棋牌游戏中#xff0c;如围棋、西洋棋、象棋、黑白棋、德州扑克等。MCTS与人工神经网络结合#xff0c;可发挥巨大的作用#xff0c;典型的例子是2016年的AlphaGo#xff0c;以4:1…一. 什么是蒙特卡洛树搜索
蒙特卡洛树搜索(MCTS)是一种启发式搜索算法一般用在棋牌游戏中如围棋、西洋棋、象棋、黑白棋、德州扑克等。MCTS与人工神经网络结合可发挥巨大的作用典型的例子是2016年的AlphaGo以4:1的比分战胜了韩国的9段棋手李世石。
二. 蒙特卡洛树搜索与蒙特卡罗方法的区别
蒙特卡罗方法使用随机抽样来解决其他方法难以或不可能解决的确定性问题是一类计算方法的统称。它被广泛用在数学、物理的问题中基本上能解决具有概率解释的任何问题。蒙特卡罗方法的应用领域包括统计物理学、工程学、计算生物学、计算机图形学、AI游戏、金融和商业等。而蒙特卡洛树搜索(MCTS)就是其在AI游戏中的应用它用于搜索游戏中的最佳动作。
三. MCTS的工作原理
MCTS使用一个tree来记录搜索结果它更新tree的方法就是模拟游戏。就像人类在下棋时会在大脑中模拟对手的着法厉害的甚至计算10步、20步以后MCTS也是类似的原理。它先模拟几次游戏然后把游戏结果记录在tree中再根据最好的模拟结果选择最佳的动作。
MCTS一共包含4个步骤选择Selection、扩展Expansion、模拟Simulation、反向传播BackPropagation。
1选择Selection是从根节点开始连续选择子节点一直到达某个叶子节点然后在那个节点上进行更新。也就是说select时只会选leaf node叶子节点。
注意根节点是当前的游戏状态叶节点是尚未启动模拟的任何潜在子节点。
2扩展Expansion也叫expand是指一个节点往下产生新的子节点。
3模拟Simulation也叫rollout是随机模拟即以目前的状态开始模拟一场游戏直到结束。有时也叫播放或推出。
expand和rollout区别是如果目前节点是全新的就进行rollout如果节点已经被更新过就进行expand。这种说法可能不准确
4反向传播BackPropagation就是把leaf node的更新一直往上传直到根节点。有点类似神经网络的BP但更简单不涉及微积分。
MCTS整个执行过程如下
第一次模拟
我们有一个node记录wi和ni的值其中wi代表赢了几场ni代表总场数。对于围棋来说我们一般用wi代表黑棋赢的场数。
在一开始我们没进行任何游戏因此wi和ni都为0
第一步选择一个没有child的node目前只有root节点可选。 第二步因为是全新的节点需要进行rollout。由于root代表开局状态黑棋和白棋都没下过所以进行rollout没任何意义因此先进行expand。在19x19的棋盘上一共361个位置可以下。因此expand之后有361个child节点。 为了简单起见假设只有两个位置可以选。 在expand之后黑色root节点不再是leaf节点。
第三步选择一个leaf节点进行rollout。从root开始寻找此时有两个child选项。如何决定选哪个这时候要用到一个概念叫做UCB1(Upper Confidence Bound)也叫上置信度边界1。如下 其中wi表示当前node赢的次数ni表示当前node总共的模拟次数Ni表示当前node的父节点的模拟次数C是可以自己调整的参数最常用的是
对于左下角的leaf节点还没模拟过因此wi0ni0它的父节点即root也是0/0因此Ni0所以套用ucb1公式发现分母为0无法计算。所以当做ucb1的结果无限大。同样右下角的节点也是无限大。
由于两个都是无限大所以按顺序选节点即可比如选择左下角节点。
此节点是leaf node同时也是全新的节点现在对它rollout。因为root节点代表黑棋下所以现在轮到白棋下然后黑棋再下一直到游戏结束。 假设下到最后黑棋赢了那就更新这个node的值。因为黑棋赢了一场就将wi更新为1ni也更新为1. 接下来进行最后一步即反向传播。因此黑色root节点也变为了1/1如下
此时完成了一次MCTS模拟。一共需要几次模拟是你可以自行设置的。模拟越多次MCTS最后搜索的结果越准确提供的着法越强大。一般需要跑几万几十万次甚至更多。这个例子我们再进行几次更新说明。
第二次模拟
第一步选择一个没有child的node有两个选项需要计算两个node的ucb1
左边的ucb1是1代入公式可得右边的ucb1是无穷大右边更大选择它。 第二步因为是全新的节点需要进行rollout无需expand。假设这次黑棋输了如下
此时wi不会增加仍为0但是ni加1于是有 第三步反向传播。把黑色root节点的ni也加1即有 第三次模拟
第一步选择一个没有child的node有两个选项需要计算两个node的ucb1
左边是2.177右边是1.177因此选择左边。 第二步因为该leaf节点已经被更新过所以先expand。同样假设生成两个子节点。此时白色节点不再是leaf node需要继续往下select。和前面一样两个children节点都是新的ucb1都是无穷大因此按顺序选左边那个。 第三步对左下角leaf节点进行rollout。和前面一样随机下到游戏结束为止。这次假设黑棋输了。 此时把ni更新为1而wi保持不变。
第四步反向传播。依次更新白色、黑色节点为1/2、1/3. 第四次模拟
第一步选择一个没有child的node第二层白色节点有两个需要计算两个node的ucb1左边是1.548右边是1.482左边更大选它。 由于没到达leaf节点需要继续往下select此时轮到白的下在计算ucb1的时候要使用白棋的wi而目前节点上记录的都是黑棋的胜率需要进行换算假设不考虑和棋围棋的确没有和棋白棋赢的次数总场次-黑棋赢的次数即ni-wi就是白棋赢的次数所以左路径白棋的wi是1得出ucb1为2.177右路径白棋的wi是0得出ucb1为无穷大所以选择右边。 第二步因为该leaf node是全新的节点需要进行rollout无需expand。这次假设是黑棋赢我们把wi和ni都加1则0/0变为1/1 第三步反向传播。白色节点、root节点依次变为2/3、2/4 四次模拟结束你就可以决定该下哪步了。黑棋下左边的位置胜率为2/3而右边胜率为0。所以下左边。 UCB1公式的意义
ucb1的公式分为左右两部分左边是胜率如果一个node的胜率越高那么ucb1值也越高即胜率越高的一步棋越容易继续被选中。MCTS需要模拟足够多的次数来让胜率越准确。 右边这一项ni在分母Ni在分子因此模拟中一条路走过的次数越多ni相对Ni就越大就会导致ucb1相对变小。换言之已经走过很多次的路MCTS就不想再走了这是为了探索其他路径会不会有更好的着法。
ucb1公式体现了游戏中平衡开发(exploitation)和探索(exploration)的思想。开发(exploitation)为了选择已知最好策略探索(exploration)为了选择探索其他路线。如果只做exploitation而忽略exploration即永远选择胜率最高的路径可能就无法发现更好的着法。如果只做exploration而忽略exploitation意味着对围棋361个位置进行平均的探索会浪费很多时间探索胜率很低的路径效率太差MCTS的深度到不了太深着法也不会准确。
四. AlphaGo如何使用MCTS
AlphaGo如何将MCTS和deep learning相结合的呢
AlphaGo在搜索的时候使用了两个神经网络value network(值网络)和policy network(策略网络)如下 policy network作用和原理只要喂给policy network目前棋盘上的状态它就可以得出下一步的最佳落点policy network能给棋盘每个位置打分来选择下一步(即move)这样就能取代ucb1能减小search的广度(breadth)并提高准确性 value network作用和原理value network用来取代rollout意思是不需要真正模拟到分出胜负。用value network就能根据棋局状态(即board positions)得出双方输赢的概率能减小search的深度(depth)并提高准确性 说明AlphaGo的policy network有两种 supervised learning (SL) policy network和reinforcement learning (RL) policy network即基于监督学习的策略网络和基于强化学习的策略网络区别是训练数据来源的不同。SL的数据来自人类专家棋谱数据。RL的数据来自AI自我博弈(selfplay)。
policy network和value network的训练过程
policy network首先在人类专家数据上进行监督学习从而能预测人类专家的着法然后利用policy-gradient强化学习算法进行优化。value network利用两个训练好的policy network相互博弈来进行预测输赢。
扩展AlphaGo、AlphaGo Zero和AlphaGo Master三者区别
AlphaGo Zero是只基于自我博弈(selfplay)强化学习训练得到的没有任何人类数据的监督。AlphaGo Zero使用了单个neural network而不是分开的policy network和value network两个网络。如果说AlphaGo中MonteCarlo rollout和value network同时存在互相补充那么在AlphaGo Zero中rollout则被neural network完全取代了。AlphaGo Zero的MCTS更加简化。AlphaGo Master和AlphaGo Zero使用的算法和模型一样但使用了部分人类专家数据。
五. MCTS的优缺点
MCTS能够非常聪明的去探索胜率较高的路径和dfs这类暴力穷举算法比起来可以花费较少的运算资源就能达到不错的效果尤其对于围棋这类每步棋都有200种左右选择的游戏使用MCTS的效果非常显著。但与此同时也要指出MCTS并不能保证一定找到最佳路径和着法。AlphaGo和李世石比赛就输了一盘说明不一定能百分百找到最优解。不过论整体胜率AlphaGo和AlphaGo Zero已远远超过了人类。既然围棋的变化(10的360次方)比宇宙中的原子还多比起dfs或minimax等算法使用MCTS还是非常有优势和有必要的。
