当前位置: 首页 > news >正文

蒙特卡洛树搜索(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的循环结构就是让程序“杀个回马枪”&#xff0…...

超全的命令(代码)执行漏洞无回显的姿势总结(附带详细代码和测试分析过程)

目录 漏洞代码 突破方式 重定向 dnslog外部通信 burpsuite burpcollaborator外部通信 日志监听 netcat监听 反弹shell的各种姿势 漏洞代码 <?php shell_exec($_GET[a]); ?>这里使用了无回显的shell执行函数shell_exec&#xff0c;给html目录的权限是777 突破方…...

STM32MP157-Linux音频应用编程-简易语音助手

文章目录前言STM32MP157简易语音助手alsa-lib简介&#xff1a;移植alsa-lib库&#xff1a;libcurl库简介&#xff1a;移植libcurl库&#xff1a;API调用修改asrmain.c文件修改token.c文件录音文件IO打开音频文件硬件控制sysfs文件系统数据解析和控制多线程主循环实现效果及注意…...

Python-OpenCV图像处理:学习图像算术运算,如加减法、图像混合、按位运算,以及如何实现它们

目录 目标 图像添加 图像混合算法 按位运算 目标 学习对图像的几种算术运算,如加法、减法、位运算等。了解这些功能:cv.add()、...

并发编程——ReentrantLock

如果有兴趣了解更多相关内容&#xff0c;欢迎来我的个人网站看看&#xff1a;耶瞳空间 一&#xff1a;基本介绍 从Java 5开始&#xff0c;引入了一个高级的处理并发的java.util.concurrent包&#xff0c;它提供了大量更高级的并发功能&#xff0c;能大大简化多线程程序的编写…...

English Learning - L2 第 3 次小组纠音 [ʌ] [ɒ] [ʊ] [ɪ] [ə] [e] 2023.3.4 周六

English Learning - L2 第 3 次小组纠音 [ʌ] [ɒ] [ʊ] [ɪ] [ə] [e] 2023.3.4 周六共性问题小元音 [ʌ]小元音 [ɒ]小元音 [ʊ]小元音 [ɪ]小元音 [ə]小元音 [e]我的发音问题纠音过程共性问题 小元音 [ʌ] 口型容易偏大 解决办法&#xff1a;因为嘴角没有放松&#xff0c…...

STM32之关门狗

看门狗介绍在由单片机构成的微型计算机系统中&#xff0c;由于单片机的工作常常会受到来自外界电磁场的干扰&#xff0c;造成程序的跑飞&#xff0c;而陷入死循环&#xff0c;程序的正常运行被打断&#xff0c;由单片机控制的系统无法继续工作&#xff0c;会造成整个系统的陷入…...

Apollo控制部分1-- ControlComponent组件介绍

Apollo控制部分1-- ControlComponent组件介绍摘要一、ControlComponent1、启动文件解析2、ControlComponent()组件函数解析1&#xff09;ControlComponent::ControlComponent() 构造函数2&#xff09;ControlComponent::Init() 初始化函数&#xff08;执行一次&#xff09;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…...

【网络】序列化和反序列化

&#x1f941;作者&#xff1a; 华丞臧. &#x1f4d5;​​​​专栏&#xff1a;【网络】 各位读者老爷如果觉得博主写的不错&#xff0c;请诸位多多支持(点赞收藏关注)。如果有错误的地方&#xff0c;欢迎在评论区指出。 推荐一款刷题网站 &#x1f449; LeetCode刷题网站 文章…...

【代码随想录训练营】【Day32】第八章|贪心算法|122.买卖股票的最佳时机II |55. 跳跃游戏|45.跳跃游戏II

买卖股票的最佳时机II 题目详细&#xff1a;LeetCode.122 买卖股票的最佳时机&#xff0c;怎么都能够想出来个思路&#xff0c;假如我们每天都能预知明天的股票是涨是降&#xff0c;那么贪心策略就是在涨之前买股票&#xff0c;在降的前一天卖掉&#xff0c;这就是买卖股票的…...

constexpr 和 常量表达式

&#x1f440;&#x1f440;常量表达式 常量表达式是指值不会改变并且在编译过程就能得到计算结果的表达式。 字面值属于常量表达式&#xff0c;用常量表达式初始化的const对象也是常量表达式。 那么是什么来就决定是不是常量表达式呢&#xff1f;一个对象是不是常量表达式主要…...

Vue响应式原理————Object.defineProperty()和proxy的用法分享

Vue框架一个比较核心的功能就是我们的数据是响应式的&#xff0c;这样我们在修改数据的时候&#xff0c;页面会自动帮我们更新&#xff0c;那么想要实现这个功能就要实现对一个数据的劫持&#xff0c;即在取值和设置值的同时我们能够检测到即数据劫持。vue2响应式的实现原理所依…...

CSDN 编程竞赛三十四期题解

竞赛总览 CSDN 编程竞赛三十四期&#xff1a;比赛详情 (csdn.net) 本期的题目和第三十一期竞赛的题目竟然高度重合&#xff0c;真不知道该写点什么了。 不过&#xff0c;上次那道测试数据有bug的题已经修复了&#xff0c;答题过程挺顺利的&#xff0c;没有遇到新的问题。 竞…...

C#教程06 运算符

文章目录 一、算术运算符加法运算符(+)减法运算符(-)乘法运算符(*)除法运算符(/)二、逻辑运算符与运算符(&&)或运算符(||)非运算符(!)三、比较运算符等于运算符(==)大于运算符(>)小于运算符(<)大于等于运算符(>=)小于等于运算符(<=…...

软测入门(六)pytest单元测试

pytest pytest是python的一种单元测试框架&#xff0c;同自带的unit test测试框架类似&#xff0c;但pytest更简洁高效。 单元测试&#xff1a; 测试 函数、类、方法能不能正常运行测试的结果是否符合我们的预期结果 安装 pip install -U pytest基本使用 通过pytest包使用…...

经典分类模型回顾5—DenseNet实现图像分类(matlab)

DenseNet&#xff0c;全称为Densely Connected Convolutional Networks&#xff0c;中文名为密集连接卷积网络&#xff0c;是由李沐等人在2017年提出的一种深度神经网络架构。 DenseNet旨在解决深度神经网络中的梯度消失问题和参数数量过多的问题&#xff0c;通过构建密集连接…...

基于flask+bootstrap+echarts+mysql的鱼村小馆订餐后台管理系统

&#x1f4cb; 个人简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是阿牛&#xff0c;全栈领域优质创作者。&#x1f61c;&#x1f4dd; 个人主页&#xff1a;馆主阿牛&#x1f525;&#x1f389; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4d…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...