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

基于博弈树的开源五子棋AI教程[5 启发式搜索]

文章目录

  • 1 最大化攻击者/最小化防守者排序
  • 2 置换表启发
  • 3 杀手表启发
  • 4 历史表启发
  • 历史表以及杀手表的维护
    • 初始化
    • 追加杀手表项
    • 清空杀手表

启发式搜索的姿势千奇百怪,本文只讨论一下几种

//搜索空间
#define Search_Space_MVA    0     //最优价值攻击者[分数最大]
#define Search_Space_MCP    1     //最优棋型
#define Search_Space_MHT    2     //历史表排序
#define Search_Space_MKT    3     //杀手表排序
#define Search_Space_MT     4     //综合技术[MVA + MHT + MKT + 置换表]
#define Search_Space_FS     5     //第一手生成策略

1 最大化攻击者/最小化防守者排序

这里就是最简单对于当前节点棋盘分数/分数的增长量进行排序。得分越高,出现越靠前。

//视角为 evalPlayer
void GameBoard::getSearchSpaceAroundStonesMaxValuableAttacter(QList<MPoint> &searchVectors,QList<MPoint> &seachSpace,MPlayerType evalPlayer, MPlayerType searchPlayer,quint8 searchType /* = MINIMAX_SEARCH*/) {bool maximizingPlayer = evalPlayer == searchPlayer;int cutLength = getSearchCutLength(seachSpace, maximizingPlayer, searchType);QList<int> searchVectorsScores;searchVectors.reserve(cutLength);searchVectorsScores.reserve(cutLength);quint16 savedSearchBoardPatternDirection[boardSize][boardSize];int minScore = INT_MAX;  // 记录最小分数for (const auto& s : seachSpace) {quint64 key = zobristSearchHash.generateHash(s, PLAYER_NONE, searchPlayer);int scoreCur;if (!zobristSearchHash.getLeafTable(searchPlayer, scoreCur, key)) {setSearchBoard(s, searchPlayer, savedSearchBoardPatternDirection);  // 模拟落子scoreCur = evaluateBoard(searchPlayer);setSearchBoard(s, PLAYER_NONE, savedSearchBoardPatternDirection);  // 撤销模拟落子}if (scoreCur <= minScore && searchVectors.size() >= cutLength) {continue; // 如果当前分数不够高且列表已满,跳过}// 插入排序int insertPos = 0;for (; insertPos < qMin(searchVectors.size(), cutLength); ++insertPos) {if (scoreCur > searchVectorsScores[insertPos]) {break;}}if (insertPos < cutLength) {searchVectors.insert(insertPos, s);searchVectorsScores.insert(insertPos, scoreCur);if (searchVectors.size() > cutLength) {searchVectors.removeLast(); // 移除最小分数的元素searchVectorsScores.removeLast();}minScore = searchVectorsScores.last(); // 更新最小分数}}// sortSearchResultByCoference(searchVectors, searchHash, maximizingPlayer, searchType);
}

2 置换表启发

置换表保存了搜索过程中最优价值的节点信息,如果发现当前搜索状态在置换表,那么这一状态应该率先被搜索。

//返回的值:[0,id-1]是使用历史表启发后的结果
int GameBoard::sortMoveBySearchHistoryTable(QVector<MPoint> &searchVector,quint8 startPosition/*=0*/, quint8 searchType/*=minimax_search*/)
{Q_UNUSED(searchType);if(!globalParam::utilGameSetting.IsOpenSearchHistoryTable) return startPosition;QReadLocker locker(&globalParam::historyTableLock);std::sort(searchVector.begin() + startPosition, searchVector.end(), [](const MPoint &a, const MPoint &b) {return globalParam::historyTable[a.x()][a.y()] > globalParam::historyTable[b.x()][b.y()];});//只保留有值点for(;startPosition < searchVector.size(); startPosition ++){if(globalParam::historyTable[searchVector.at(startPosition).x()][searchVector.at(startPosition).y()] == 0) break;}return startPosition;
}

3 杀手表启发

杀手表保存了搜索过程中某一指定搜索深度下各个节点的剪枝信息。搜索过程中,在因为某节点产生的剪枝次数越多,这个值也就越大。

//返回的值:[0,id-1]是使用杀手表启发后的结果
int GameBoard::sortMoveBySearchKillerTable(QVector<MPoint> &searchVector, quint8 startPosition/*=0*/, quint8 searchType/*=minimax_search*/)
{Q_UNUSED(searchType);if(!globalParam::utilGameSetting.IsOpenKillerTable) return startPosition;QReadLocker locker(&globalParam::killerTableLock);int depth = searchSpacePlayers.size();std::sort(searchVector.begin() + startPosition, searchVector.end(), [depth](const MPoint &a, const MPoint &b) {return globalParam::killerTable[depth][UtilGetMPointPosID(a)] > globalParam::killerTable[depth][UtilGetMPointPosID(b)];});//只保留有值点for(;startPosition < searchVector.size(); startPosition ++){if(globalParam::killerTable[depth][UtilGetMPointPosID(searchVector.at(startPosition))] == 0) break;}return startPosition;
}

4 历史表启发

类似于杀手表,但是历史表忽略了搜索深度信息。只要在搜索过程中因为某一节点产生了剪枝,这个节点的价值就会变大。

//返回的值:[0,id-1]是使用历史表启发后的结果
int GameBoard::sortMoveBySearchHistoryTable(QVector<MPoint> &searchVector,quint8 startPosition/*=0*/, quint8 searchType/*=minimax_search*/)
{Q_UNUSED(searchType);if(!globalParam::utilGameSetting.IsOpenSearchHistoryTable) return startPosition;QReadLocker locker(&globalParam::historyTableLock);std::sort(searchVector.begin() + startPosition, searchVector.end(), [](const MPoint &a, const MPoint &b) {return globalParam::historyTable[a.x()][a.y()] > globalParam::historyTable[b.x()][b.y()];});//只保留有值点for(;startPosition < searchVector.size(); startPosition ++){if(globalParam::historyTable[searchVector.at(startPosition).x()][searchVector.at(startPosition).y()] == 0) break;}return startPosition;
}

历史表以及杀手表的维护

杀手表和历史表的方法类似,这里仅提供杀手表的维护过程。

初始化

QReadWriteLock globalParam::killerTableLock;
int globalParam::killerTable[GameSetting::BoardSize * GameSetting::BoardSize + 1][GameSetting::BoardSize * GameSetting::BoardSize] = {{0}};

追加杀手表项

//追加杀手表表项
//depth:表示距离叶子的深度
void GameBoard::appendSearchKillerTable(const MPoint &position, int depth, quint8 NABSearchHashFlag)
{if(!globalParam::utilGameSetting.IsOpenKillerTable) return;QWriteLocker locker(&globalParam::killerTableLock);//随着搜索的加深,逐渐靠近叶子节点,depth的值逐步变小,对于历史表的贡献也在变小if(NABSearchHashFlag == hashfLowerBound){globalParam::killerTable[searchSpacePlayers.size()][UtilGetMPointPosID(position)] += depth * depth;}
}

清空杀手表

//清楚所有的杀手表
void GameBoard::clearSearchKillerTable()
{if(!globalParam::utilGameSetting.IsOpenKillerTable) return;QWriteLocker locker(&globalParam::killerTableLock);//全部置零清除杀手表for(int row = 0;row < boardSizeSquare + 1; ++row){for(int col = 0; col < boardSizeSquare; ++col){globalParam::killerTable[row][col] = 0;}}//    //使用累积影响的方式清除杀手表//    for(int row = 0;row < boardSizeSquare + 1; ++row){//        for(int col = 0; col < boardSizeSquare; ++col){//            globalParam::killerTable[row][col] = globalParam::historyTable[row][col] >> 2;//        }//    }
}

相关文章:

基于博弈树的开源五子棋AI教程[5 启发式搜索]

文章目录 1 最大化攻击者/最小化防守者排序2 置换表启发3 杀手表启发4 历史表启发历史表以及杀手表的维护初始化追加杀手表项清空杀手表 启发式搜索的姿势千奇百怪&#xff0c;本文只讨论一下几种 //搜索空间 #define Search_Space_MVA 0 //最优价值攻击者[分数最大] #d…...

JavaScript原型,原型链 ? 有什么特点?

一、原型 JavaScript 常被描述为一种基于原型的语言——每个对象拥有一个原型对象 当试图访问一个对象的属性时&#xff0c;它不仅仅在该对象上搜寻&#xff0c;还会搜寻该对象的原型&#xff0c;以及该对象的原型的原型&#xff0c;依次层层向上搜索&#xff0c;直到找到一个…...

Unity 问题 之 ScrollView ,LayoutGroup,ContentSizeFitter 一起使用时,动态变化时无法及时刷新更新适配界面的问题

Unity 问题 之 ScrollView ,LayoutGroup,ContentSizeFitter 一起使用时&#xff0c;动态变化时无法及时刷新更新适配界面的问题 目录 Unity 问题 之 ScrollView ,LayoutGroup,ContentSizeFitter 一起使用时&#xff0c;动态变化时无法及时刷新更新适配界面的问题 一、简单介绍…...

linux 中 C++的环境搭建以及测试工具的简单介绍

文章目录 makefleCMakegdb调试 与 coredumpValgrind 内存检测gtest 单元测试 makefile 介绍 安装 : sudo apt install make makefile 的规则: 举例说明 包括&#xff1a;目标文件 、 依赖文件 、 生成规则 使用 &#xff1a; make make clean CMake : CMake是一个…...

448. 找到所有数组中消失的数字

找到所有数组中消失的数字 描述 : 给你一个含 n 个整数的数组 nums &#xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字&#xff0c;并以数组的形式返回结果。 题目 : LeetCode 448. 找到所有数组中消失的数字: 448. 找…...

为何在下雪天它“失宠”了,传统雪地靴居然不适合下雪穿

随着冬至的到来&#xff0c;一年之中最寒冷的“三九天”正式拉开序幕。近期各地纷纷下起了大雪&#xff0c;在这场大雪中雪地靴似乎“失宠”了。在社交媒体上&#xff0c;有网友吐槽“雪地靴根本不能下雪穿”&#xff0c;后面有不少网友纷纷分享了自己在雪地靴上尴尬的经历&…...

第34节: Vue3 调用内联处理程序中的方法

在UniApp中使用Vue3框架时&#xff0c;你可以在模板中直接调用组件内联处理程序中的方法。以下是一个示例&#xff1a; <template> <view> <button click"handleClick">Click me</button> <p>{{ message }}</p> </view&…...

JavaScript--明明白白Promise (Park One)

明明白白Promise (Park One) Promise是一种用于处理异步操作的特殊对象。它代表了一个尚未完成但最终会完成的操作&#xff0c;并可以在操作完成后返回结果或错误。 Promise有三种状态&#xff1a;pending&#xff08;进行中&#xff09;、fulfilled&#xff08;已完成&#…...

el-form与el-upload结合上传带附件的表单数据(后端篇)

1.写在之前 本文采用Spring Boot MinIO MySQLMybatis Plus技术栈&#xff0c;参考ruoyi-vue-pro项目。 前端实现请看本篇文章el-form与el-upload结合上传带附件的表单数据&#xff08;前端篇&#xff09;-CSDN博客。 2.需求描述 在OA办公系统中&#xff0c;流程表单申请人…...

postMessage——不同源的网页直接通过localStorage/sessionStorage/Cookies——技能提升

最近遇到一个问题&#xff0c;就是不同源的两个网页之间进行localstorage或者cookie的共享。 上周其实遇到过一次&#xff0c;觉得麻烦就让后端换了种方式处理了&#xff0c;昨天又遇到了同样的问题。 使用场景 比如从网页A通过iframe跳转到网页B&#xff0c;而且这两个网页…...

上市公司-绿色投资者数据集(2000-2022)

上市公司-绿色投资者数据&#xff08;2000-2022年&#xff09;是一份涵盖了过去二十多年中国上市公司绿色投资情况的详细数据集。该数据集包括了各上市公司的股票代码、年份、会计年度、股票简称&#xff0c;以及STPT&#xff08;特殊处理股票的标识&#xff09;&#xff0c;行…...

3 pandas之dataframe

定义 DataFrame是一个二维数据结构&#xff0c;即数据以行和列的方式以表格形式对齐。 DataFrame特点&#xff1a; 存在不同类型的列大小可变带有标签的轴可对列和行进行算数运算 构造函数 pandas.DataFrame( data, index, columns, dtype, copy)参数解释&#xff1a; 序号…...

vue-内网,离线使用百度地图(地图瓦片图下载静态资源展示定位)

前言 最近发现很多小伙伴都在问内网怎么使用百度地图&#xff0c;或者是断网情况下能使用百度地图吗 后面经过一番研究&#xff0c;主要难点是&#xff0c;正常情况下我们是访问公网百度图片&#xff0c;数据&#xff0c;才能使用 内网时访问不了百度地图资源时就会使用不了&…...

OpenFeign 万字教程详解

OpenFeign 万字教程详解 目录 一、概述 1.1.OpenFeign是什么&#xff1f;1.2.OpenFeign能干什么1.3.OpenFeign和Feign的区别1.4.FeignClient 二、OpenFeign使用 2.1.OpenFeign 常规远程调用2.2.OpenFeign 微服务使用步骤2.3.OpenFeign 超时控制2.4.OpenFeign 日志打印2.5.O…...

全自动双轴晶圆划片机:半导体制造的关键利器

随着科技的飞速发展&#xff0c;半导体行业正以前所未有的速度向前迈进。在这个过程中&#xff0c;全自动双轴晶圆划片机作为一种重要的设备&#xff0c;在半导体晶圆、集成电路、QFN、发光二极管、miniLED、太阳能电池、电子基片等材料的划切过程中发挥着举足轻重的作用。 全自…...

Android Studio 安装和使用

前些天&#xff0c;打开了几年前的一个Android Studio app项目&#xff0c;使用安卓虚拟机仿真app崩溃&#xff0c;怀疑是不是中间升级过Android Studio导致异常的&#xff0c;马上脑子一热卸载了&#xff0c;结果上次踩过的坑&#xff0c;一个没少又踩一次&#xff0c;谨以此文…...

【已解决】Java中,判断:集合中是否包含指定元素(模糊匹配)比如权限中的user:list或者是user:*这种判断

背景描述 在工作中&#xff0c;有时候&#xff0c;我们需要对list中是否包含了指定元素进行判断&#xff0c;但是&#xff0c;有时候又需要支持模糊匹配&#xff0c;这个时候怎么办呢&#xff1f; 比如权限&#xff0c;我们知道&#xff0c;权限不仅可以配置完整的路径&#…...

【基于激光雷达的路沿检测用于自动驾驶的真值标注】

文章目录 概要主要贡献内容概述实验小结 概要 论文地址&#xff1a;https://arxiv.org/pdf/2312.00534.pdf 路沿检测在自动驾驶中扮演着重要的角色&#xff0c;因为它能够帮助车辆感知道可行驶区域和不可行驶区域。为了开发和验证自动驾驶功能&#xff0c;标注的数据是必不可…...

【Spring实战】配置多数据源

文章目录 1. 配置数据源信息2. 创建第一个数据源3. 创建第二个数据源4. 创建启动类及查询方法5. 启动服务6. 创建表及做数据7. 查询验证8. 详细代码总结 通过上一节的介绍&#xff0c;我们已经知道了如何使用 Spring 进行数据源的配置以及应用。在一些复杂的应用中&#xff0c;…...

DevOps系列文章 : 使用dpkg命令打deb包

创建一个打包的目录&#xff0c;类似rpmbuild&#xff0c;这里创建了目录deb_build mkdir deb_build目标 我有一个hello的二进制文件hello和源码hello.c, 准备安装到/opt/helloworld目录中 步骤 在deb_build目录创建一个文件夹用于存放我的安装文件 mkdir helloworld在he…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...