蒙特卡洛树搜索(MTCS)
一、目标
一种启发式的搜索算法,在搜索空间巨大的场景下比较有效
算法完成后得到一棵树,这棵树可以实现:给定一个游戏状态,直接选择最佳的下一步
二、算法四阶段
1、选择(Selection)
父节点选择UCB值最大的子节点作为当前节点
UCB=Vi‾+c2lnNniUCB=\overline{V_{i}} +c\sqrt{\frac{2lnN}{n_{i}}} UCB=Vi+cni2lnN
其中,c通常取2。
nin_{i}ni代表 iii 节点被选择的次数,NNN代表其父节点被选择的次数。
Vi‾\overline{V_{i}}Vi 代表 iii 节点的平均价值大小(例如 iii 节点 Vi=v,ni=3V_{i}=v,n_{i}=3Vi=v,ni=3,则Vi‾=v/3\overline{V_{i}}=v/3Vi=v/3)。
2、扩展(Expansion)
为当前节点创建一个或多个子节点(子节点代表当前节点下可采取的动作)
3、仿真(Simulation/Rollout)
在某一节点用随机策略进行模拟(rollout)
def Rollout(S_i): # S_i = 当前状态While True: # S_i达到终止条件/状态(下棋中某方获胜或平局)if S_i a terimal state: # 返回结果valuereturn value(S_i) # 还未终止,则# 随机选择一个当前状态下的可用动作A_i = random(available_action(S_i)) # 在当前状态下采取动作,得到新的状态S_i = simulate(A_i, S_i)
4、反向传播(Backpropagation)
得到模拟结果后不断反向更新父节点

三、运行过程

n代表当前节点被探索的次数。
则运行过程如下:
1、选择节点
- 当前节点是叶节点,则选择该节点
- 当前节点有孩子,孩子中UCB值最大的作为选择的节点
2、节点扩展 + 模拟
- 若选择的节点未模拟过(n=0),则进行模拟,得到结果后更新该节点 n=1 , value=结果数值。
- 若选择的节点模拟过(n≠0),则扩展节点。添加在该节点下所有可采取的动作,作为孩子
- 选择第一个孩子作为当前节点,进行模拟
def Rollout(S_i): # S_i = 当前状态While True: # S_i达到终止条件/状态(下棋中某方获胜或平局)if S_i a terimal state: # 返回结果valuereturn value(S_i) # 还未终止,则# 随机选择一个当前状态下的可用动作A_i = random(available_action(S_i)) # 在当前状态下采取动作,得到新的状态S_i = simulate(A_i, S_i)
3、反向传播
- 当孩子得到 Vc=v,nc+=1V_{c}=v,n_{c}+=1Vc=v,nc+=1,反向传播到父节点,父节点 Vp+=v,np+=1V_{p}+=v,n_{p}+=1Vp+=v,np+=1,直至传播到根节点。
三、实例
具体样例可参考博客蒙特卡洛树搜索(MCTS)详解、蒙特卡洛树搜索 MCTS 入门或b站视频AI如何下棋?直观了解蒙特卡洛树搜索MCTS!!!
相关文章:
蒙特卡洛树搜索(MTCS)
一、目标 一种启发式的搜索算法,在搜索空间巨大的场景下比较有效 算法完成后得到一棵树,这棵树可以实现:给定一个游戏状态,直接选择最佳的下一步 二、算法四阶段 1、选择(Selection) 父节点选择UCB值最…...
【Verilog】——Verilog简介
目录 1.简介 2.什么是HDL以及HDL的功能 3.Verilog和C语言的比较 4.Verilog的用途 5.数字系统的抽象层次 1.系统级 2.算法级 3.RTL级(寄存器变换级) 6.数字系统抽象层级 7.自顶向下的结构化设计方法 8.Verilog建模 9.Verilog概述 10.Verilog模块的基本…...
【Python从入门到进阶】10、流程控制语句-循环语句(for-while)
接上篇《9、流程控制语句-条件语句(if-else)》 上一篇我们学习了Python的控制流语句的概念,以及其中的条件语句(if/else),本篇我们来学习控制流语句中的循环语句(for/while)。 一、Python中的循环 Python的循环结构就是让程序“杀个回马枪”࿰…...
超全的命令(代码)执行漏洞无回显的姿势总结(附带详细代码和测试分析过程)
目录 漏洞代码 突破方式 重定向 dnslog外部通信 burpsuite burpcollaborator外部通信 日志监听 netcat监听 反弹shell的各种姿势 漏洞代码 <?php shell_exec($_GET[a]); ?>这里使用了无回显的shell执行函数shell_exec,给html目录的权限是777 突破方…...
STM32MP157-Linux音频应用编程-简易语音助手
文章目录前言STM32MP157简易语音助手alsa-lib简介:移植alsa-lib库:libcurl库简介:移植libcurl库:API调用修改asrmain.c文件修改token.c文件录音文件IO打开音频文件硬件控制sysfs文件系统数据解析和控制多线程主循环实现效果及注意…...
Python-OpenCV图像处理:学习图像算术运算,如加减法、图像混合、按位运算,以及如何实现它们
目录 目标 图像添加 图像混合算法 按位运算 目标 学习对图像的几种算术运算,如加法、减法、位运算等。了解这些功能:cv.add()、...
并发编程——ReentrantLock
如果有兴趣了解更多相关内容,欢迎来我的个人网站看看:耶瞳空间 一:基本介绍 从Java 5开始,引入了一个高级的处理并发的java.util.concurrent包,它提供了大量更高级的并发功能,能大大简化多线程程序的编写…...
English Learning - L2 第 3 次小组纠音 [ʌ] [ɒ] [ʊ] [ɪ] [ə] [e] 2023.3.4 周六
English Learning - L2 第 3 次小组纠音 [ʌ] [ɒ] [ʊ] [ɪ] [ə] [e] 2023.3.4 周六共性问题小元音 [ʌ]小元音 [ɒ]小元音 [ʊ]小元音 [ɪ]小元音 [ə]小元音 [e]我的发音问题纠音过程共性问题 小元音 [ʌ] 口型容易偏大 解决办法:因为嘴角没有放松,…...
STM32之关门狗
看门狗介绍在由单片机构成的微型计算机系统中,由于单片机的工作常常会受到来自外界电磁场的干扰,造成程序的跑飞,而陷入死循环,程序的正常运行被打断,由单片机控制的系统无法继续工作,会造成整个系统的陷入…...
Apollo控制部分1-- ControlComponent组件介绍
Apollo控制部分1-- ControlComponent组件介绍摘要一、ControlComponent1、启动文件解析2、ControlComponent()组件函数解析1)ControlComponent::ControlComponent() 构造函数2)ControlComponent::Init() 初始化函数(执行一次)3&am…...
0626-0631韩顺平Java Buffered字节处理流 学习笔记
如何去构建字节流package com.hspedu.outputstream_;import java.io.*;/*** author abner* version 1.0*/ public class BufferedCopy02 {public static void main(String[] args) {String srcFilePath "D:\\Users\\Pictures\\Camera Roll\\Pierre-Auguste_Renoir,_Le_Mo…...
【网络】序列化和反序列化
🥁作者: 华丞臧. 📕专栏:【网络】 各位读者老爷如果觉得博主写的不错,请诸位多多支持(点赞收藏关注)。如果有错误的地方,欢迎在评论区指出。 推荐一款刷题网站 👉 LeetCode刷题网站 文章…...
【代码随想录训练营】【Day32】第八章|贪心算法|122.买卖股票的最佳时机II |55. 跳跃游戏|45.跳跃游戏II
买卖股票的最佳时机II 题目详细:LeetCode.122 买卖股票的最佳时机,怎么都能够想出来个思路,假如我们每天都能预知明天的股票是涨是降,那么贪心策略就是在涨之前买股票,在降的前一天卖掉,这就是买卖股票的…...
constexpr 和 常量表达式
👀👀常量表达式 常量表达式是指值不会改变并且在编译过程就能得到计算结果的表达式。 字面值属于常量表达式,用常量表达式初始化的const对象也是常量表达式。 那么是什么来就决定是不是常量表达式呢?一个对象是不是常量表达式主要…...
Vue响应式原理————Object.defineProperty()和proxy的用法分享
Vue框架一个比较核心的功能就是我们的数据是响应式的,这样我们在修改数据的时候,页面会自动帮我们更新,那么想要实现这个功能就要实现对一个数据的劫持,即在取值和设置值的同时我们能够检测到即数据劫持。vue2响应式的实现原理所依…...
CSDN 编程竞赛三十四期题解
竞赛总览 CSDN 编程竞赛三十四期:比赛详情 (csdn.net) 本期的题目和第三十一期竞赛的题目竟然高度重合,真不知道该写点什么了。 不过,上次那道测试数据有bug的题已经修复了,答题过程挺顺利的,没有遇到新的问题。 竞…...
C#教程06 运算符
文章目录 一、算术运算符加法运算符(+)减法运算符(-)乘法运算符(*)除法运算符(/)二、逻辑运算符与运算符(&&)或运算符(||)非运算符(!)三、比较运算符等于运算符(==)大于运算符(>)小于运算符(<)大于等于运算符(>=)小于等于运算符(<=…...
软测入门(六)pytest单元测试
pytest pytest是python的一种单元测试框架,同自带的unit test测试框架类似,但pytest更简洁高效。 单元测试: 测试 函数、类、方法能不能正常运行测试的结果是否符合我们的预期结果 安装 pip install -U pytest基本使用 通过pytest包使用…...
经典分类模型回顾5—DenseNet实现图像分类(matlab)
DenseNet,全称为Densely Connected Convolutional Networks,中文名为密集连接卷积网络,是由李沐等人在2017年提出的一种深度神经网络架构。 DenseNet旨在解决深度神经网络中的梯度消失问题和参数数量过多的问题,通过构建密集连接…...
基于flask+bootstrap+echarts+mysql的鱼村小馆订餐后台管理系统
📋 个人简介 💖 作者简介:大家好,我是阿牛,全栈领域优质创作者。😜📝 个人主页:馆主阿牛🔥🎉 支持我:点赞👍收藏⭐️留言Ὅ…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
