开发者社区> 云栖大讲堂> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

简介:
+关注继续查看
福利推荐:阿里云、腾讯云、华为云等大品牌云产品全线2折优惠活动来袭,4核8G云服务器899元/3年,新老用户共享优惠,点击这里立即抢购>>>

蒙特卡洛树搜索(MCTS)是所有现代围棋程序的核心组件。在此之上可以加入各种小技巧(如 UCT,RAVE/AMAF,Progressive Bias,Virtual win & lose,Progressive Widening,LGR,Criticality 等等)和大改进(如 AlphaGo 的策略网络和价值网络)。

网上很少见到关于 MCTS 的详细介绍,而且许多看似详细的介绍实际有错误,甚至许多人会混淆蒙特卡洛树搜索和蒙特卡洛方法。这两者有本质区别。用做过渲染器的朋友会理解的话来说:蒙特卡洛方法有偏差(Bias),而MCTS没有偏差(Bias)。我们在后文会解释。

一、极小极大(Minimax)搜索

先看传统的博弈游戏树搜索,著名的极小极大(Minimax)搜索,学过算法的朋友会清楚。看下图,假设现在轮到黑棋,黑棋有b1和b2两手可选,白棋对于b1有w1和w2两手可选,白棋对于b2有w3 w4 w5三手可选:

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

然后假设走完w1/w2/w3/w4/w5后,经过局面评估,黑棋的未来胜率分别是 50%/48%/62%/45%/58%(等一下,这些胜率是怎么评估出来的?我们后文会说这个问题)。

请问,黑棋此时最佳的着法是b1还是b2?如果是用蒙特卡洛方法,趋近的会是其下所有胜率的平均值。例如经过蒙特卡洛模拟,会发现b1后续的胜率是49% = (50+48)/2,而b2后续的胜率是55% = (62+45+58)/3。

于是蒙特卡洛方法说应该走b2,因为55%比49%的胜率高。但这是错误的。因为如果白棋够聪明,会在黑棋走b1的时候回应以w2(尽量降低黑棋的胜率),在黑棋走b2的时候回应以w4(尽量降低黑棋的胜率)。

所以走b1后黑棋的真实胜率是48%,走b2后黑棋的真实胜率是45%。黑棋的正解是b1。这就是 Minimax 搜索的核心思想:在搜索树中,每次轮到黑棋走时,走对黑棋最有利的;轮到白棋走时,走对黑棋最不利的。由于围棋是零和游戏,这就可以达到最优解。这是一个由底往上的过程:先把搜索树画到我们可以承受的深度,然后逐层往上取最大值或最小值回溯,就可以看到双方的正解(如果胜率评估是准确的)。而实际编程的时候,是往下不断生长节点,然后动态更新每个父节点的胜率值。

下图是一个更多层的例子:

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

值得注意的是,在实际对局中,胜率评估会有不准确的地方,这就会导致“地平线效应”,即由于电脑思考的深度不够,且胜率评估不够准确,因此没有看见正解。

Minimax 搜索还有许多后续发展,如课本会说的 Alpha-beta 剪枝,以及更进一步的 Null Window / NegaScout / MTD(f) 等等。可惜这些方法更适合象棋等棋类,对于围棋的意义不大(除非已经接近终局),请读者思考原因。

蒙特卡洛树搜索和蒙特卡洛方法的区别在于:

  • 如果用蒙特卡洛方法做上一百万次模拟,b1和b2的胜率仍然会固定在49%和55%,不会进步,永远错误。所以它的结果存在偏差(Bias),当然,也有方差(Variance)。

  • 而蒙特卡洛树搜索在一段时间模拟后,b1和b2的胜率就会向48%和45%收敛,从而给出正确的答案。所以它的结果不存在偏差(Bias),只存在方差(Variance)。但是,对于复杂的局面,它仍然有可能长期陷入陷阱,直到很久之后才开始收敛到正确答案。

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

二、蒙特卡洛树搜索

如果想把 Minimax 搜索运用到围棋上,立刻会遇到两个大问题:

  • 搜索树太广。棋盘太大了,每一方在每一步都有很多着法可选。

  • 很难评估胜率。除非把搜索树走到终局,这意味着要走够三百多步(因为对于电脑来说,甚至很难判断何时才是双方都同意的终局,所以只能傻傻地填子,一直到双方都真的没地方可以走为止)。简单地说,搜索树也需要特别深。

蒙特卡洛树搜索的意义在于部分解决了上述两个问题:

  • 它可以给出一个局面评估,虽然不准,但比没有强。这就部分解决了第二个问题。

  • 根据它的设计,搜索树会较好地自动集中到“更值得搜索的变化”(注意,也不一定准)。如果发现一个不错的着法,蒙特卡洛树搜索会较快地把它看到很深,可以说它结合了广度优先搜索和深度优先搜索,类似于启发式搜索。这就部分解决了第一个问题。

最后,随着搜索树的自动生长,蒙特卡洛树搜索可以保证在足够长的时间后收敛到完美解(但可能需要极长的时间)。下面看具体过程(需要指出,下图是网络上常见的一个图,但其实有错误):

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

上图中每个节点代表一个局面。而 A/B 代表这个节点被访问 B 次,黑棋胜利了 A 次。例如一开始的根节点是 12/21,代表总共模拟了 21 次,黑棋胜利了 12 次。

我们将不断重复一个过程(很多万次):

这个过程的第一步叫选择(Selection)。从根节点往下走,每次都选一个“最值得看的子节点”(具体规则稍后说),直到来到一个“存在未扩展的子节点”的节点,如图中的 3/3 节点。什么叫做“存在未扩展的子节点”,其实就是指这个局面存在未走过的后续着法。

第二步叫扩展(Expansion),我们给这个节点加上一个 0/0 子节点,对应之前所说的“未扩展的子节点”,就是还没有试过的一个着法。

第三步是模拟(Simluation)。从上面这个没有试过的着法开始,用快速走子策略(Rollout policy)走到底,得到一个胜负结果。按照普遍的观点,快速走子策略适合选择一个棋力很弱但走子很快的策略。因为如果这个策略走得慢(比如用 AlphaGo 的策略网络走棋),虽然棋力会更强,结果会更准确,但由于耗时多了,在单位时间内的模拟次数就少了,所以不一定会棋力更强,有可能会更弱。这也是为什么我们一般只模拟一次,因为如果模拟多次,虽然更准确,但更慢。

第四步是回溯(Backpropagation)。把模拟的结果加到它的所有父节点上。例如第三步模拟的结果是 0/1(代表黑棋失败),那么就把这个节点的所有父节点加上 0/1。

三、重要细节

怎么选择节点?和从前一样:如果轮到黑棋走,就选对于黑棋有利的;如果轮到白棋走,就选对于黑棋最不利的。但不能太贪心,不能每次都只选择“最有利的/最不利的”,因为这会意味着搜索树的广度不够,容易忽略实际更好的选择。

因此,最简单有效的选择公式是这样的:

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

其中 x 是节点的当前胜率估计(注意,如前所述,要考虑当前是黑棋走还是白棋走!),N 是节点的访问次数。C 是一个常数。C 越大就越偏向于广度搜索,C 越小就越偏向于深度搜索。注意对于原始的 UCT 有一个理论最优的 C 值,但由于我们的目标并不是最小化“遗憾”,因此需要根据实际情况调参。

我们看例子说明这是什么意思,就看之前的图吧。假设根节点是轮到黑棋走。那么我们首先需要在 7/10、5/8、0/3 之间选择:

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

如果 C 比较小,我们将会选择 7/10,接着就要在 2/4 和 5/6 间选择。注意,由于现在是白棋走,需要把胜率估计倒过来:

28 天自制你的 AlphaGo(五):蒙特卡洛树搜索(MCTS)基础

那么我们下一步肯定应该选 2/4。所以说之前的图是错误的,因为制图的人并没有注意到要把胜率倒过来(有朋友会说是不是可以认为它的白圈代表白棋的胜率,但这样它的回溯过程就是错的)。

最后,AlphaGo 的策略网络,可以用于改进上述的分数公式,让我们更准确地选择需扩展的节点。而 AlphaGo 的价值网络,可以与快速走子策略的模拟结果相结合,得到更准确的局面评估结果。注意,如果想写出高效的程序,这里还有很多细节,因为策略网络和价值网络的运行毕竟需要时间,我们不希望等到网络给出结果再进行下一步,在等的时候可以先做其它事情,例如 AlphaGo 还有一个所谓 Tree policy,是在策略网络给出结果之前先用着。

相信大家现在就可以写出正确的 MCTS 程序了(注意:最终应该选择访问量最大的节点,而不是胜率最高的节点,简单地说是因为访问量最大的节点的结果更可靠)。如果要写一个高效的程序,你会发现必须自己写一个内存池。关于 MCTS 还有很多话题可以说,这篇就到这里吧。

本系列已更新多篇,其它几篇的传送门:

28 天自制你的 AlphaGo(一)

28 天自制你的 AlphaGo(二):训练策略网络,真正与之对弈

28天自制你的AlphaGo(三):对策略网络的深入分析以及它的弱点所在

28天自制你的AlphaGo(四):结合强化学习与深度学习的Policy Gradient(左右互搏自我进化的基础)

本文作者:彭博

本文转自雷锋网禁止二次转载,原文链接


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
蒙特卡洛方法与蒙特卡洛搜索树(一)
最近在做 AIOps 相关的项目时,用到了蒙特卡洛搜索树(MCTS)算法,对蒙特卡洛相关的内容有些兴趣,在此整理些相关的资料。
23 0
?LeetCode刷题实战98:验证二叉搜索树
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
27 0
如何用代码的方式取出SAP C4C销售订单创建后所有业务伙伴的数据
如何用代码的方式取出SAP C4C销售订单创建后所有业务伙伴的数据
18 0
YYC松鼠短视频系统【bug】短信验证码功能bug,新注册短信用户任意填写验证码都能通过注册的严重bug修复
YYC松鼠短视频系统【bug】短信验证码功能bug,新注册短信用户任意填写验证码都能通过注册的严重bug修复
190 0
2.cocos2d-x坐标体系(UI坐标系,GL坐标系,本地坐标,世界坐标,节点坐标)
?? openGL & UI坐标体系 OpenGL坐标系:该坐标原点在屏幕左下角,x轴向右,y轴向上。这也就是cocos2dx中用到的坐标系。 ??? 屏幕坐标系:该坐标系的原点在屏幕左上角,x轴向右,y轴向下,其实和OpenGL坐标系的差别也就是y轴的方向。假设游戏场景的分辨率为(500,500),其中一个点坐标为(200,200),那么它在Open
1485 0
Howto: Deploy VC2008 apps without installing vcredist_x86.exe
There are several reasons for xcopy deployment of an application (also known as application local). One main reason is that you are independent of what the target computer has installed.
803 0
bboss mvc框架中使用注解指定控制器方法日期类型参数日期格式的例子
bboss mvc框架中使用注解指定控制器方法日期类型参数日期格式的例子 直入正题: 1.控制器方法定义-DateConvertController /* * Copyright 2008 biaoping.
761 0
+关注
云栖大讲堂
擅长前端领域,欢迎各位热爱前端的朋友加入我们( 钉钉群号:23351485)关注【前端那些事儿】云栖号,更多好文持续更新中!
3913
文章
1754
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载


http://www.vxiaotou.com