Al Go: 蒙特卡洛树搜索(MCTS)简介
目录
1. 前言
1.1 Minimax
1.2 剪枝
1.3 蒙特卡洛树搜索
1.4 为什么随机走子会可行呢?
2. vanilla Monte Carlo tree search
3. UCT-based trade-off between exploitation and exploration
4. MCTS基本算法流程
5. Efficiency Through Expert Policies
6. Efficiency Through Value Approximation
1. 前言
众所周知,像围棋、国际象棋等这一类两人对抗性游戏(discrete, deterministic games with perfect information)项目的智能agent或者说bot的实现的最关键算法之一是蒙特卡洛树搜索(Monte Carlo Tree Search)。
1.1 Minimax
在双人对弈游戏中,某一方下子时,会考虑所有可能落子,针对每一落子考虑对手所有可能的应手,针对对手的每种可能应手进一步考虑自己的应手,这样一直考虑下去,这个过程实际上就是在构建一棵搜索树进行搜索。。。理论上如果可能计算到终局(即构建完整的搜索树),就可以每一步都采取理论上最优的落子策略(不一定能够战无不胜,取决于游戏类型)。这个过程其实就是Minimax search algorithm(极小化极大搜索算法)的执行过程。
像Tic-tac-toe这样的小规模游戏,现代计算机可以轻松地从一开始就构建出所有可能棋盘局面构成的搜索树,从而可以给出理论最优解。因此基于minimax搜索算法可以很容易地设计出unbeatable tic-tac-toe agent/bot。之所以说是unbeatable而不是战无不胜的,是因为Tic-tac-toe游戏是一个有先手优势的游戏,假定先手方能下出最优解,后手方就不可能战胜先手方,最多只能下成平局。理想棋手与非理想棋手之间的对弈结果关系如下所示:
但是,对于像象棋(中国象棋、国际象棋、日本将棋等)或者围棋,分支系数太大,搜索树的规模呈指数方式快速增长,而且深度可能上百层(一局围棋的手数可以轻松到达2~300以上)。构建完整的搜索树是完全无法想象的,无论从存储资源还是从计算时间来说。
关于minimax,有兴趣者可以参考TicTacToe:Minimax-Agent以及人机对弈python实现
1.2 剪枝
解决以上搜索树规模爆炸问题的关键技术是剪枝,即通过忽略搜索树的某些部分来缩减搜索空间。
搜索树是2维的,它具有宽度和深度。
宽度是指某个特定棋局(注意,棋局有时是指一局棋,有时是指一个盘面状态,当前棋盘上的局面的意思。根据上下文应该可以好无歧义地判断是指那种意思)下可能动作的数据(常称分支系数,branching factor)。
深度是指从某个棋局开始到可能的棋局终局状态的手数(或者说回合数。但是通常来说两个各下一手称为一个回合)。
当然,这两个数值对于每一个棋局来说都可能是不同的。
剪枝可以从深度和宽度两个方面来考虑,相应地有两种典型的剪枝技术:
- 一是基于棋局评估函数来减少搜索深度;
- 另一是用于减少搜索宽度的alpha-beta剪枝;
1.3 蒙特卡洛树搜索
剪枝(无论是深度还是宽度)技术的性能最终决定对棋局的评估,而对于围棋来说,棋局评估是一件非常困难的事情。蒙特卡洛树搜索(MCTS)为我们提供了一种有效的方法,不需要依赖于什么高深的游戏策略,也不需要利用游戏特定的启发式规则,通过模拟随机棋局的方式来进行棋局好坏的评估,并据此进行落子选择。
通常把模拟进行的每一个随机棋局称为一次推演(rollout)。
1.4 为什么随机走子会可行呢?
2. vanilla Monte Carlo tree search
以下以Tic-Tac-Toe游戏为例来说明基本的MCTS算法。
MCTS算法的处理从某个棋局(以下记为s0)开始,棋手在s0棋局下有若干种可能的落子点(可以理解为从一个actions set \mathscr{A}\中选择可能的动作)。每一种可能的落子导向下一个棋局,对应于搜索树中s0节点的子节点。尝试每一种可能的动作即对应蒙特卡洛树搜索树的扩展(expanding),这样一步步(交替尝试双方的可能的落子)深入下去直到终局的过程,就是构建蒙特卡洛搜索树的过程。
上图为从某个盘面状态s0出发进行搜索的示例。在该状态下下一手有5种可能,分别对应以上搜索树的5个子节点(每个子节点对应于某个下一手下完后所到达的状态)。为了选择最佳的一手,必需给每个这个每个子节点赋予一个分数(score,以下图中用W表示),然后就可以根据分数高低来选择(确定性地,选择分数最高的一手;或者概率性地进行选择,分数高的被选中的概率更高)下一手。这个可以通过从该子节点所代表的棋局出发,通过随机走子(random rollout)直到终局,并根据胜负结果来对该子节点进行打分(获胜即给+1分,负则给-1分,平局则得0分)。
本例中,考虑从出发经过随机走子到达终局,如果当前落子方获胜即给+1分,负则给-1分,平局则得0分。当然,由于是随机走子,一局、两局的结果可能并不足以代表真实的情况。实际上,需要从
出发经过随机走子若干局后得到的总分数(或者平均分数)作为
的分数(可以理解为在当前局面下当前落子方的胜率)。
都进行了随机走子后可以得到各节点对应的分数。然后,就可以根据这个分数进行落子选择。
每个节点存储的不仅仅有分数,还有从该节点出发所搜索过的棋局数N。
经过棋局推演(针对每个子节点各试走了一局)后,假设我们得到的数据{N,W},然后再通过回溯就可以相应得到
的数据(由于是基于
的分数进行落子选择,看似我们并不需要更新
的数据?其实不然,更新
的数据至少有两个用途:
(1) 总试走子对局数用于如下UCT-based算法需要的\N_p\;
(2) 可以根据{W,N}计算出当前状态下的胜率(可以是当前状态下的总体胜率,也可以是当前状态下棋手下出最佳下一手时的胜率)。在bot对弈或者bot-human对弈时的直播通常会显示这个信息。
在蒙特卡洛树搜索算法中,大量地重复以上处理(树的扩展,棋局推演。。。),当试推演的棋局数足够多而且对各种不同棋局的覆盖度足够高时,所产生的结果就有可能统计充分地(statistically sufficiently)给出足够好的棋局评估结果,并据此做出合理的落子决策。
一般来说,MCTS算法包含以下4个基本步骤:
- selection,选择合适的叶子节点进行进一步扩展
- expansion, 针对选定的叶子节点进行搜索树扩展
- evaluation, 评估所扩展出来的新的叶子节点所代表的棋局
- backup,基于将评估结果通过回溯更新整个蒙特卡洛搜索树
与minimax一样,MCTS算法也同样需要基于剪枝来缩减搜索空间。前面剪枝技术的最大难点在于对棋局的评估,那么MCTS是如何解决棋局评估问题的呢?
3. UCT-based trade-off between exploitation and exploration
在改进的MCTS算法中,采用基于UCT的选择算法来实现探索(exploration)和利用(exploitation)之间的折衷。针对每一个节点,计算其UCT(Upper confidence tree) score如下:
其中:
: the number of visit counts for the parent node
: trade-off factor. c越小表示越偏向优先选取既得平均分数高的子节点;c越高就表示优先选择访问次数少的子节点。这一策略是强化学习中经典的trade-off-between-exploitation-and-exploration策略。右边第一项代表exploitation,第二项则代表exploration。
针对以上例子计算各子节点的UCT后更新如下。
如上图所示,很显然,最左边的子节点为最优节点(当出现平局时可以随机选择一个或者确定性选择—比如说其中序号更小—某一个均可)。针对这个节点进一步进行展开,并同样将其结果进行回溯更新得到如下图所示:
这里需要注意的是,由于是对抗性游戏,双方轮流落子。胜负关系从对局双方来看是反的。在统计胜负结果计数时要注意始终站在当前搜索树根节点\s_0\的该当落子者的立场来进行统计。
不断重复以上MCTS迭代直到退出条件满足(比如说,设定每次MCTS处理的总的rollout局数N。由于以上基于UCT的选择机制,各子节点访问次数可能并不均等,有的子节点多一些,有的子节点少一些),蒙特卡洛搜索树会不断扩展生长,如果我们的选择机制足够好的话,就有可能以尽量小的代价对所有可能而且有效的“下一手”进行充分的探索和覆盖(同时,有效地忽略了那些价值较低的选项。通俗一点说,就是做到“好钢用在刀刃上”)。然后,就可以基于搜索结果选择最合理的下一手。比如说,如果我们通过从s0出发的MCTS搜索得到了以下结果,那很显然下一手应该选择s0,1:
4. MCTS基本算法流程
总结一下,面向对弈游戏的MCTS基本算法流程如下所示(示意):
- 以
为根节点初始化一个搜索树,并初始化
的数据:{N=0, W=0}
- 从
往下搜索,找到一个能够添加子节点的叶子节点
- 往下搜索过程中,子节点选择发生在同一层,同一层之间的比较选择可以是随机的,也可以是基于UCT的
- 对该叶子节点添加一个子节点,并从该子节点开始进行(随机或者非随机)棋局推演(rollout)
- 根据棋局推演结果回溯更新当前子节点以及其所有祖先节点的信息,N、W、UCT、etc
- 如果满足rollout退出条件,前进到(6);否则,返回(2)。rollout退出条件有以下可能的选择:
- Rollout退出条件可以是到达了预设的最大rollout数
- 搜索时间到达了预设时间(即发生了timeout)
- Others
- 根据
的各子节点的分数选择其中最优子节点进行实际落子
其中,影响效率的关键就在于第2步、第3步选择展开(以进行rollout)的叶子节点的处理。
5. Efficiency Through Expert Policies
国际象棋和围棋的分支系数非常大,在一个局面下,可以选择落子点非常多,这使得充分地对未来可能的对局状态进行探索非常困难。国际象棋的可能棋局数据估计为,而围棋(标准的19路棋盘)的可能棋局数高达
。与之相比,TicTacToe游戏只有5478种而已。所以,对于国际象棋或者围棋来说,完全随机的MCTS(vanilla MCTS)是不够的,还需要有更进一步的策略用于提高搜索效率。
假定我们有一个已知的专家策略(expert policy),能够给出专家(职业选手)在特定状态下采取某一落子的可能性
,如下图所示:
这样的话,问题就简单了。只要这个策略足够好,落子时只要查询一下所有可能的子节点所对应的概率取其最大值(或者以概率的方式进行采样)就可以了。但是,构造一个专家策略非常困难,验证一个专家策略是否最优同样非常困难。
幸运的是,我们可以对以上MCTS方案进行一定的微调,并用于进行策略提升。在这个变化版本中,每个节点仍然存储基于策略的概率信息\P_i\,而这个概率信息又被用于调节节点的用作选择基准的UCT score。Deepmind所使用的probabilistic upper confidence tree score如下所示:
与前述的基本的UCT score的区别在于(1)右边第2项多了一个概率乘性因子;(2)根号里面的分母加1。概率乘性因子Pi体现了“expert policy”对MCTS过程的节点选择的影响。\P_i\初始化为均一分布(uniform distribution)时则退化为原来的基本UCT-score。新的MCTS过程的节点选择将在以下三方面取得折中:
- 分数高者得到更多机会
- 访问次数少者得到更多机会
- “expert policy”认为更可能的子节点得到更多机会
如果专家策略足够好的话,MCTS就可以更加聚焦于比较有利的棋局状态的演化探索;反之,如果专家策略不好的话,就会导致MCTS聚焦与比较不利的棋局状态的演化探索。但是,不管怎样,只要搜索的量足够大的话,最终,都能够收敛于相同的结果,即UCT最终都是主要由来决定。
但是当搜索资源受限,即只能进行有限的搜索时,好的专家策略就能给出(概率意义上)更好的结果,自然也就能使得(采用该策略的)bot更强大。
6. Efficiency Through Value Approximation
另外一种提高效率的方法是直接基于价值近似的方法。假定有一个价值近似函数\ \hat{W}(x)\,(不需要进行rollout,也就是根本不进行MCTS)直接输入当前盘面状况价值评估(比如说代表当前局面的胜率)。如果该函数是一个很好的价值近似函数,而且其执行速度比rollout要更快的话,那么就可能用折中策略实现一个又快又强大的bot。
需要注意的是价值近似函数\ \hat{W}(x)\与前面提及的expert policy \Pi(a|s)\是不一样的。后者代表的是专家在当前局面下的落子概率,而\ \hat{W}(x)\直接代表当前局面的价值(比如说胜率)。虽然专家落子概率大的点通常意味着落子与该点能够获得更高的胜率,在理想条件下两者应该是代表相同的信息。但是,在有现实约束的条件下,两者不是完全一回事。
价值近似与expert-policy可以并行使用以加速MCTS。但是,根本的问题是,如何构建或者获得expert-policy和价值近似函数呢?
Deepmind给出的答案是,没有现成的expert-policy和价值近似函数,通过self-play(左右手互博)以及深度强化学习来自己琢磨出expert-policy和价值近似函数来。事实上,Deepmind通过AlphaGoZero证明了用拿来主义从人类棋手那里总结出来的expert-policy不好使,把bot宝宝带歪了。。。完全脱离人类经验自己从零开始学习使得AlphaGoZero的实力(相比之前的AlphaGo-Fan、Lee、Kejie以及后来的Master)获得了飞跃式的发展。
Coming soon:
AlphaGo Zero是如何训练的?
MCTS agent for Tic-Tac-Toe implementation (python, pytorch)
DIY Go agent implementation ...
Reference:
[1] AlphaGo Zero – How and Why it Works – Tim Wheeler (hibal.org)
[2] 《深度学习与围棋》,人民邮电出版社
相关文章:
Al Go: 蒙特卡洛树搜索(MCTS)简介
目录 1. 前言 1.1 Minimax 1.2 剪枝 1.3 蒙特卡洛树搜索 1.4 为什么随机走子会可行呢? 2. vanilla Monte Carlo tree search 3. UCT-based trade-off between exploitation and exploration 4. MCTS基本算法流程 5. Efficiency Through Expert Policies 6…...
Client-go操作Deployment
在工作中需要对kubernetes进行自定义资源的开发,操作K8s的资源肯定是必不可少的。K8s原生语言是用Go编写的,所以在CRD中使用client-go来操作资源。本次介绍一下使用client-go来操作Deployment。 1. 创建main函数 func main() {homePath : homedir.Home…...

设计模式——单例模式(懒汉和饿汉)
单例模式 一、概念 单例模式是一种对象创建型模式,使用单例模式,可以保证为一个类只生成唯一的实例对象。也就是说,在整个程序空间中,该类只存在一个实例对象。一个类只能有一个实例在生活中是很常见的,比如打印机程…...
详解——Vue3递归函数功能
在 Vue 3 中,递归函数是一种在组件中调用自身的技术。递归函数在解决树状数据结构、无限级分类、嵌套组件等情况下非常有用。以下是一个示例,展示如何在 Vue 3 中实现递归函数的功能、代码和原理: 1. 创建递归组件: 首先&#x…...

【VSCode】查看二进制文件
1.安装插件Hex Editor 2.打开二进制文件 3.执行Hex Editor命令...
C#设计模式之观察者模式
题目:假设你正在开发一个简单的新闻发布系统,该系统允许用户订阅不同的新闻频道,并在有新闻发布时向订阅者发送通知。使用观察者模式设计和实现该系统。观察者模式的相关概念和定义: 观察者模式是一种行为设计模式,它定…...

小红书攻略:爆款引流,如何在激烈竞争中脱颖而出?
小红书(RED)作为国内最具影响力的社交电商平台之一,是很多品牌运营者的首选之一。然而,在小红书的激烈竞争中,如何快速引流、吸引关注,成为了品牌运营者面临的挑战。本篇文章一秒推小编将为您介绍小红书运营…...
Ubuntu中的安装卸载及删除方法
说明:由于图形化界面方法(如Add/Remove... 和Synaptic Package Manageer)比较简单,所以这里主要总结在终端通过命令行方式进行的软件包安装、卸载和删除的方法。 一、Ubuntu中软件安装方法 1、APT方式 (1࿰…...
获取历史dokcer镜像项目,并上传gitlab,再打包镜像管理
今天遇到一个问题: 发现一个部署在Jenkins的脚本用的docker镜像是:test_project:v20191108,即这个项目是19年的一个版本,由于代码不断更新,用现在的最新代码运行该脚本,可能不能运行了,必须用19…...

【Go语言】Golang保姆级入门教程 Go初学者chapter3
Go语言 第三章 运算符 下划线“_”本身在Go中一个特殊的标识符,成为空标识符。可以代表任何其他的标识符,但是他对应的值就会被忽略 仅仅被作为站维度使用, 不能作为标识符使用 因为Go语言中没有private public 所以标记变量首字母大写代表其…...
网络防御(4)
一、结合以下问题对当天内容进行总结 1. 什么是IDS? 2. IDS和防火墙有什么不同? 3. IDS工作原理? 4. IDS的主要检测方法有哪些详细说明? 5. IDS的部署方式有哪些? 6. IDS的签名是什么意思?签名过滤器有什么…...
conda错误处理:ResolvePackageNotFound
当运行conda env create -f environment.yaml时出现"ResolvePackageNotFound"错误,这可能是由于环境配置文件中指定的依赖项无法找到或不可用。 错误消息中列出的依赖项包括pip20.3、python3.8.5和cudatoolkit11.3。 尝试以下解决方案: 更新…...
linux初学者小命令
linux初学者小命令 一.在正式学习linux命令之前需要先认识一下linux环境中命令是如何被执行的shell是一个属于linux内核的软件,在系统启动后加载进RAM(内存)内,每个用户通过终端登录系统后,就会运行。负责不间断的接收用户的输入,…...

宝尊电商短期前景堪忧,宝尊国际能否取得成功还有待验证
来源:猛兽财经 作者:猛兽财经 核心业务面临短期逆风 在2023年第一季度财报中,宝尊电商(BZUN)表示其电商业务(简称BEC)主要包括:品牌的门店运营、客户服务以及物流和供应链管理、IT和数字营销等增值服务”。…...

百川智能发布首个530亿参数闭源大模型,今年追上GPT-3.5
4月官宣创业,6月15日发布第一款7B开源模型,7月11日发布第二款13B、130亿参数开源模型。 平均保持2个月一个版本发布速度,8月8日,百川智能发布了创业以来的首个530亿参数闭源大模型——Baichuan-53B(以下简称“53B”&a…...
Redis的常用数据结构
StringListhashsetzset 1.字符串类型是Redis最基础的数据结构 使用场景: 缓存功能 Redis 作为缓存层,MySQL作为存储层,绝大部分请求的数据都是从Redis中获取。由于Redis具有支撑高并发的特性,所以缓存通常能起到加速读写和降低后端压力的作…...

深入JVM - JIT分层编译技术与日志详解
深入JVM - JIT分层编译技术与日志详解 文章目录 深入JVM - JIT分层编译技术与日志详解1. 背景简介2. JIT 编译器2.1. 客户端版本的编译器: C12.2. 服务端版本的编译器: C22.3. Graal JIT 编译器 3. 分层编译技术(Tiered Compilation)3.1. 汇聚两种编译器的优点3.2. 精准优化(Ac…...

临时文档2
java 中 IO 流分为几种? 按照流的流向分,可以分为输入流和输出流;按照操作单元划分,可以划分为字节流和字符流;按照流的角色划分为节点流和处理流。 Java Io流共涉及40多个类,这些类看上去很杂乱,但实际…...

[深度学习入门]PyTorch深度学习[数组变形、批量处理、通用函数、广播机制]
目录 一、前言二、数组变形2.1 更改数组的形状2.1.1 reshape2.1.2 resize2.1.3 T(转置)2.1.4 ravel2.1.5 flatten2.1.6 squeeze2.1.7 transpose 2.2 合并数组2.2.1 append2.1.2 concatenate2.1.3 stack 三、批量处理四、通用函数4.1 math 与 numpy 函数的性能比较4.2 循环与向量…...
男孩向妈妈发脾气爸爸言传身教
近日,广东的一个家庭中发生了一件引人深思的事情。 一个男孩因为游戏没有通关,向妈妈发脾气,结果被爸爸发现并带到一边教育。 爸爸对孩子说:“她凭什么要承受你给的负能量,凭什么你心情不好就可以对着她发脾气…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...

通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...