蒙特卡洛树搜索(Monte Carlo Tree Search)揭秘

一. 什么是蒙特卡洛树搜索

蒙特卡洛树搜索(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是可以自己调整的参数,最常用的是\sqrt{2}

对于左下角的leaf节点,还没模拟过,因此wi=0,ni=0,它的父节点即root,也是0/0,因此Ni=0,所以套用ucb1公式发现,分母为0无法计算。所以当做ucb1的结果无限大。同样右下角的节点也是无限大。

由于两个都是无限大,所以按顺序选节点即可,比如选择左下角节点

此节点是leaf node,同时也是全新的节点,现在对它rollout。因为root节点代表黑棋下,所以现在轮到白棋下,然后黑棋再下,一直到游戏结束。

假设下到最后,黑棋赢了,那就更新这个node的值。因为黑棋赢了一场,就将wi更新为1,ni也更新为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相互博弈来进行预测输赢。

扩展:AlphaGoAlphaGo ZeroAlphaGo 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还是非常有优势和有必要的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/145503.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

压测工具主要功能是什么?该怎样选择?

压测工具是一类用于模拟并评估系统在不同负载条件下的性能的软件应用程序。通过模拟大量用户同时访问系统,压测工具能够帮助开发者识别系统的瓶颈、性能瓶颈以及潜在的故障点。这种实时、模拟的方式允许开发者在正式投入使用之前发现并解决问题,提高系统…

MySQL8 绿色版安装

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: MySQL学习 ✨特色专栏: My…

数据结构线性表——队列

前言:哈喽小伙伴们,这篇文章我们继续来学习线性表的第五章——队列。 世上无难事,只怕有心人。数据结构看似有很多种类型,但是它们之间都有着千丝万缕的联系。 只要我们能够耐心学习思考,就一定能够将知识串通起来&a…

一例plugx样本的分析(AcroRd32cWP)

这是一例plugx的样本,使用了一个合法签名的程序 ,使用侧加载的方式加载一个恶意的dll,解密一个dat文件来,在内存中执行一个反射型dll来完成恶意功能。 这个病毒会使用摆渡的方式的来窃取内网的文档数据,具有严重的失泄…

c语言11周(16~20)

利用函数求和 //只填写要求的函数 double fun(int n) {double s 0;int i;for (i 1; i < n; i) {s 1.0 / (i * i);}return s; } 编写char fun(char c)函数&#xff0c;将数字参数字符c按如下规则转换。 题干编写char fun(char c)函数&#xff0c;将数字参数字符c按如…

YOLO目标检测——苹果数据集下载分享【含对应voc、coco和yolo三种格式标签】

实际项目应用&#xff1a;监测果园中苹果的生长情况、水果品质监控、自动化分拣数据集说明&#xff1a;苹果检测数据集&#xff0c;真实场景的高质量图片数据&#xff0c;数据场景丰富标签说明&#xff1a;使用lableimg标注软件标注&#xff0c;标注框质量高&#xff0c;含voc(…

《视觉SLAM十四讲》-- 后端 1(上)

文章目录 08 后端 18.1 概述8.1.1 状态估计的概率解释8.1.2 线性系统和卡尔曼滤波&#xff08;KF&#xff09;8.1.3 非线性系统和扩展卡尔曼滤波&#xff08;EKF&#xff09;8.1.4 小结 08 后端 1 前端视觉里程计可以给出一个短时间内的轨迹和地图&#xff0c;但由于不可避免的…

项目经理为什么要考PMP?PMP考试条件有哪些?

考得PMP&#xff0c;项目经理可以有以下收获&#xff1a; 1、面试条件上&#xff1a;有PMP证书优先&#xff1b; 2、覆盖行业和职位范围广&#xff0c;医疗&#xff0c;互联网&#xff0c;机械&#xff0c;建筑金融&#xff0c;汽车&#xff0c;零售等各行各业&#xff0c;基…

【FastCAE源码阅读9】鼠标框选网格、节点的实现

一、VTK的框选支持类vtkInteractorStyleRubberBandPick FastCAE的鼠标事件交互类是PropPickerInteractionStyle&#xff0c;它扩展自vtkInteractorStyleRubberBandPick。vtkInteractorStyleRubberBandPick类可以实现鼠标框选物体&#xff0c;默认情况下按下键盘r键开启框选模式…

qt之扫码枪编码自动识别文本

一、前言 使用扫码枪输入扫码后&#xff0c;自动将编码转为文字或识别进入下一功能。 只是简单的实现了一种方式&#xff0c;并不适用于商业用途 二、环境 扫码枪免驱自动扫码编码打印到输入库的环境下 三、正文 本文介绍也是输入一种方式&#xff0c;不限于非得扫码识别…

YOLO-NAS:最高效的目标检测算法之一

YOLO-NAS目标检测 介绍 YOLO&#xff08;You Only Look Once&#xff09;是一种目标检测算法&#xff0c;它使用深度神经网络模型&#xff0c;特别是卷积神经网络&#xff0c;来实时检测和分类对象。该算法首次在2016年的论文《You Only Look Once&#xff1a;统一的实时目标检…

【Proteus仿真】【51单片机】拔河游戏设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真51单片机控制器&#xff0c;使用按键、LED、动态数码管模块等。 主要功能&#xff1a; 系统运行后&#xff0c;指示灯处于中间位置&#xff0c;数码管显示得分0&#xff0c;当按下…

c++范围for语句

语法格式 for(declaration:expression)statement 基本使用 遍历输出 vector<int> nums { 1,2,3,4,5}; for (int num : nums) {num;cout << num << " "; } cout << endl; 遍历时修改 vector<int> nums { 1,2,3,4,5}; for (int&…

Android 布局优化,看过来 ~

屏幕刷新机制 基本概念 刷新率&#xff1a;屏幕每秒刷新的次数&#xff0c;单位是 Hz&#xff0c;例如 60Hz&#xff0c;刷新率取决于硬件的固定参数。帧率&#xff1a;GPU 在一秒内绘制操作的帧数&#xff0c;单位是 fps。Android 采用的是 60fps&#xff0c;即每秒 GPU 最多…

[文件读取]cuberite 文件读取 (CVE-2019-15516)

1.1漏洞描述 漏洞编号CVE-2019-15516漏洞类型文件上传漏洞等级⭐⭐⭐漏洞环境VULFOCUS攻击方式 描述: Cuberite是一款使用C语言编写的、轻量级、可扩展的多人游戏服务器。 Cuberite 2019-06-11之前版本中存在路径遍历漏洞。该漏洞源于网络系统或产品未能正确地过滤资源或文件路…

苍穹外卖项目笔记(1)

前言 苍穹外卖项目笔记附代码&#xff0c;贴上 github 链接&#xff0c;持续更新中&#xff1a;GitHub - Echo0701/sky-take-out &#xff08;不知道为啥发不了项目压缩包&#xff0c;那就下次再试试吧........&#xff09; 1 软件开发整体介绍 1.1 软件开发流程 1.2 角色分…

U-boot(一):Uboot命令和tftp

本文主要基于S5PV210探讨uboot。 uboot 部署&#xff1a;uboot(180~400K的裸机程序)在Flash(可上电读取)、OS在FLash(nand) 启动过程&#xff1a;上电后先执行uboot、uboot初始化DDR和Flash,将OS从Flash中读到DDR中启动OS,uboot结束 特点&#xff1a;…

MES系统如何改进生产管理?

伴随机械制造业行业竞争逐渐加剧&#xff0c;越来越多企业意识到MES系统的重要性&#xff0c;慢慢积极主动把握和实施MES系统。可是纵观绝大部分企业或者MES生产商&#xff0c;对MES的掌握依然存在比较大的分歧。 有一些人说MES系统是企业信息化构建的中枢神经&#xff0c;也有…

Oracle(2-3) Basic Oracle Net Server Side Configuration

文章目录 一、基础知识1、The Listener Process监听器进程2、Connection Methods 连接方法3、Spawn and Bequeath Conn4、Direct Hand-Off Connections 直接切换连接5、Redirection Session 重定向会话6、Simple to Complex:N-Tier 简单到复杂&#xff1a;N层7、Service Config…

SQL-LABS

less8 and 11-- 12 发现存在注入点 接下来我们会接着用联合查询 和以往的题目不一样没显错位&#xff0c;也就是没有报错的内容&#xff0c;尝试用盲注 布尔型 length&#xff08;&#xff09;返回长度 substr&#xff08;&#xff09;截取字符串&#xff08;语法substr&a…