基于博弈树的开源五子棋AI教程[3 极大极小搜索]

基于博弈树的开源五子棋AI教程[3 极大极小搜索]

  • 引子
  • 极大极小搜索原理
  • alpha-beta剪枝
  • 负极大搜索
  • 尾记

引子

极大极小搜索是博弈树搜索中最常用的算法,广泛应用于各类零和游戏中,例如象棋,围棋等棋类游戏。算法思想也是合乎人类的思考逻辑的:博弈双方轮流决策,并且认为双方都是理性的,都希望自己的利益最大化或者对手利益最小化。
在介绍算法前,了解博弈树的基本知识是必要的。博弈树的节点代表状态,在五子棋中就代表一个盘面;博弈树的边代表决策,对于五子棋就是落子的位置。博弈树搜索算法就是通过特定的顺序从根节点遍历整个博弈树来找到最佳的决策路径,这一路径在后文被称为PV路径(主要变例路径,Principal Variation)。
1博弈树

极大极小搜索原理

极大极小搜索双方轮流决策,尽可能的使得己方得分最大化。其将博弈双方命名为Max层和Min层,Max层最大化自己得分,Min层最小化对方得分,然后通过树的深度优先遍历获取PV路径。这里给出wiki中文给出的伪代码。

function  minimax(node, depth, maximizingPlayer) isif depth = 0 or node is a terminal node thenreturn the heuristic value of nodeif maximizingPlayer thenvalue := −∞for each child of node dovalue := max(value, minimax(child, depth − 1, FALSE))return valueelse (* minimizing player *)value := +for each child of node dovalue := min(value, minimax(child, depth − 1, TRUE))return value

极大极小搜索

alpha-beta剪枝

五子棋虽然复杂度比不上围棋,在我看到一些文章中指出五子棋的分支因子为35,意味着每个盘面平均有35个合理着法。对于指数膨胀的博弈树,深度加深后,叶子节点的数量是恐怖的,想完整遍历完整个树几乎是不可能完成的事,剪枝算法应运而生。

AB剪枝
alpha-beta剪枝(AB剪枝)是常见的优化方法,算法可以在保证最终的搜索结果不变的情况下尽可能的减少搜索节点。对于每一个节点都有一个alpha值和beta值来记录从根节点搜索到当前节点获取到的搜索信息,alpha值保存了当前max层玩家最好的走法,beta值记录了max层最坏的走法。当发现最好的走法的得分比最坏走法得分还高是(alpha>=beta)这个节点就应当被裁剪。
这种说法看着比较难以理解,下面给出四个AB剪枝例子来加深概念。
在这里插入图片描述
在这里插入图片描述

函数 alphaBeta(node, depth, α, β, maximizingPlayer):如果 depth = 0 或 node 是一个终端节点:返回 node 的评估值如果 maximizingPlayer:最大值初始化为 -∞对于每个子节点 child of node:最大值 = max(最大值, alphaBeta(child, depth - 1, α, β, False))α = max(α, 最大值)如果 β ≤ α:跳出循环(剪枝)返回 最大值否则:最小值初始化为 +∞对于每个子节点 child of node:最小值 = min(最小值, alphaBeta(child, depth - 1, α, β, True))β = min(β, 最小值)如果 β ≤ α:跳出循环(剪枝)返回 最小值

AB剪枝的搜索效率高度依赖子节点顺序,PV路径将更有利于剪枝发生。后面将在启发式搜索中详细介绍节点排序技术。

负极大搜索

极大极小的搜索中需要区分Max,Min玩家,为了代码简约提出了负极大搜索算法。算法认为对于任何一个节点,一个玩家的得分和另一玩家的损失是一样的。

函数 negaMax(node, depth, α, β):如果 depth = 0 或 node 是一个终端节点:返回 node 的评估值最大值初始化为 -∞对于每个子节点 child of node:分数 = -negaMax(child, depth - 1, -β, -α)最大值 = max(最大值, 分数)α = max(α, 分数)如果 α ≥ β:跳出循环(剪枝)返回 最大值

值得注意的一点,极大极小搜索和负极大搜索的评分函数是不一样。极大极小搜索中,无论是max层最大化自己得分,还是min层最小化对方得分,其评分的视角始终是最大层玩家。然而在负极大搜索中,max层和min层的概念已然不复存在,无论哪一方在进行决策时关注点都是最大化己方得分,因此其评分视角是当前层玩家,而不是最大层玩家。
选择负极大搜索的意义不仅在于代码简约,逻辑清晰,还有最重要的一点是置换表。极大极小搜索中,在交换双方玩家,或者将博弈树中某一中间节点作为根节点(玩家身份发生变化max玩家变成min玩家)时,我们需要考虑很多问题,置换表中的分数是不是合理的?评分视角是不是我们希望的?置换标记位是不是合理的?评分的上界是不是依旧可靠?是不是应该变成下界?但是在负极大搜索中我们就无需考虑,因为无论是分数还是标记位视角都是当前层玩家。由于我们在评分过程中,不同视角不是完全对称,其分数并不是严格相等的,置换表在玩家角色变化时并不是严格安全的,可能会造成不稳定的现象,但是这种变化在我看来时完全可以接受的。

//fail-soft negMax Alpha-Beta pruning search
int GameAI::NABSearch(int depth, int alpha, int beta, bool maximizingPlayer, quint8 searchSpaceType)
{int score;int evalPlayer = globalParam::AIPlayer;MPlayerType searchPlayer = maximizingPlayer ? evalPlayer : UtilReservePlayer(evalPlayer);if(zobristSearchHash.getNABTranspositionTable(score, depth, alpha, beta)) {return score;}//  或 游戏结束// ??或 分数过大过小score = evaluateBoard(evalPlayer);//负极大搜索中评估必须searchPlayerif(!maximizingPlayer) score *= -1;if (qAbs(score) > globalParam::utilGameSetting.MaxScore || checkSearchBoardWiner() != PLAYER_NONE){//保存置换表return score;}// 达到搜索深度if (depth == 0){//保存置换表//VCFQList<MPoint> vcf, vcfpath;if(VCXSearch(globalParam::utilGameSetting.MaxVctSearchDepth, maximizingPlayer, VCT_SEARCH, vcf, vcfpath)){qDebug() << "NABsearch : find vct";if(maximizingPlayer) return globalParam::utilGameSetting.MaxScore;else return -globalParam::utilGameSetting.MaxScore;}return score;}// 着法生成QVector<MPoint> searchPoints;getSortedSearchSpace(searchPoints, evalPlayer, searchPlayer, searchSpaceType);int scoreBest = -INT_MAX;int hashf = hashfUperBound;MPoint moveBest(InvalidMPoint);quint16 savedSearchBoardPatternDirection[boardSize][boardSize];for (const auto &curPoint : searchPoints) {if (!searchBoardHasPiece(curPoint)) {setSearchBoard(curPoint, searchPlayer, savedSearchBoardPatternDirection);// searchPlayer落子score = -NABSearch(depth - 1, -beta, -alpha, !maximizingPlayer,searchSpaceType);setSearchBoard(curPoint, PLAYER_NONE, savedSearchBoardPatternDirection);// 撤销落子if (score > scoreBest) {scoreBest = score;moveBest = curPoint;if (score >= beta) {hashf = hashfLowerBound;appendSearchKillerTable(curPoint, depth, hashf);aiCalInfo.cutTreeTimesCurrentTurn ++;break; // Alpha-Beta 剪枝}if (score > alpha) {alpha = score;hashf = hashfExact;}}}}//更新历史表appendSearchHistoryTable(moveBest, depth, hashf);// 更新置换表zobristSearchHash.appendNABTranspositionTable(depth, scoreBest, hashf, moveBest, UtilReservePlayer(searchPlayer));return scoreBest;
}

尾记

最后本来想讨论下AB剪枝中fail-softfail-hard的区别的,限于篇幅就以参考文档的方式放在后面。其次是没有展开AB值的更新以及为什么要剪枝的实际含义,展开说容易绕晕,没有几个合适的例子理解的快。
理解AB剪枝搜索是博弈树搜索的基石,后面利用置换表,杀手表以及多线程加速搜索有这重要的作用。
关于fail-hard和fail-soft的讨论
MTD+置换表
wiki AB剪枝
Minmax 搜索动画

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

物理机搭建hive

一、修改Hadoop配置 修改core-site.xml 配置yarn-site.xml 分发文件&#xff0c;然后重启集群 二、 Hive解压安装 上传文件 添加hive环境便量&#xff0c;source生效 启动高可用集群&#xff0c;启动hive 三、配置mysql元数据库 检查当前系统是否安装过Mysql&#xf…

开启Android学习之旅-5-Activity全屏

Android 两种方式设置全屏&#xff1a; 1. 第一行代码中的方法 通过 getWindow().getDecorView()方法拿到当前Activity的DecorView,再调用 setSystemUiVisibility() 方法来改变系统UI的显示&#xff0c;这里传入了 View.SYSTEM_UI_FLAG_LAYOUT_FULLSCREEN 和 View.SYSTEM_UI_…

服务器部署项目,访问验证码出现Handler dispatch failed....InvocationTargeException

场景&#xff1a; 部署ruoyi-vue的jar。访问验证码接口时&#xff0c;出现异常。本地测试没有问题&#xff0c;起初使用的jdk8&#xff0c;怀疑jdk版本问题&#xff0c;但是本地使用11.0.15版本也没问题&#xff0c;后面也就没管&#xff0c;初步排除jdk版本的问题。之前项目也…

软考高级选择考哪个好?

&#x1f4d2;软考高级总共5个科目&#xff0c;同样是高级证书&#xff0c;认可度也有区别! 大家一般在「信息系统项目管理师」✔️和「系统架构设计师」✔️二选一 1️⃣信息系统项目管理师 ❤️信息系统项目管理师也叫「高项」&#xff0c;考试内容主要是「项目管理」相关&am…

el-tree多个树进行节点同步联动(完整版)

2024.1.11今天我学习了如何对多个el-tree树进行相同节点的联动效果&#xff0c;如图&#xff1a; 这边有两棵树&#xff0c;我们发现第一个树和第二个树之间会有重复的指标&#xff0c;当我们选中第一个树的指标&#xff0c;我们希望第二个树如果也有重复的指标也能进行勾选上&…

这6个免费素材网站,设计师们一定要知道!

设计师找素材就上这6个网站&#xff0c;免费下载&#xff0c;还可以商用&#xff0c;建议收藏好了~ 1、菜鸟图库 https://www.sucai999.com/?vNTYwNDUx 菜鸟图库是我推荐过很多次的网站&#xff0c;主要是站内素材多&#xff0c;像平面、UI、电商等超多设计素材都能找到&…

PLECS如何下载第三方库并导入MOSFET 的xml文件,xml库路径添加方法及相关问题

1. 首先xml库的下载&#xff0c;PLECS提供了一个跳转的链接。 https://www.plexim.com/download/thermal_models 2. 下载一个库&#xff08;以最后一个Wolfspeed为例&#xff0c;属于CREE的SiC MOSFET&#xff09; 下载这个就行&#xff0c;都包含了。不信自己可以试试再下载…

Win10子系统Ubuntu实战(一)

在 Windows 10 中安装 Ubuntu 子系统&#xff08;Windows Subsystem for Linux&#xff0c;简称 WSL&#xff09;有几个主要的用途和好处&#xff1a;Linux 环境的支持、跨平台开发、命令行工具、测试和验证、教育用途。总体而言&#xff0c;WSL 提供了一种将 Windows 和 Linux…

【Linux】Linux系统编程——ls命令

【Linux】Linux 系统编程——ls 命令 1.命令概述 ls 命令是 Linux 和其他类 Unix 操作系统中最常用的命令之一。ls 命令是英文单词 list 的缩写&#xff0c;正如 list 的意思&#xff0c;ls 命令用于列出文件系统中的文件和目录。使用此命令&#xff0c;用户可以查看目录中的…

刚买的助听器就弄丢了,不想白配,快来看看这8大助听器防丢小技巧

我们知道助听器可以让听损人士重新听到美妙的声音和享受沟通的乐趣。但是&#xff0c;助听器也是一种很贵的物品&#xff0c;如果不小心弄丢了&#xff0c;就会让人心痛不已。 更有甚者&#xff0c;有些人因为害怕丢失助听器&#xff0c;而不敢佩戴助听器&#xff0c;错过了听力…

实现线程同步的几种方式

线程同步 1. 线程同步概念 线程同步是指多个线程协调它们的执行顺序&#xff0c;以确保它们正确、安全地访问共享资源。在并发编程中&#xff0c;当多个线程同时访问共享数据或资源时&#xff0c;可能会导致竞争条件&#xff08;Race Condition&#xff09;和其他并发问题 所…

Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图像圆图,Kotlin(2)

Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图像圆图&#xff0c;Kotlin&#xff08;2&#xff09; 在 https://zhangphil.blog.csdn.net/article/details/135374279 基础上&#xff0c;增加一个功能&#xff0c;当手指在上面的图片…

内 存 取 证

1.用户密码 从内存中获取到用户admin的密码并且破解密码&#xff0c;以Flag{admin,password}形式提交(密码为6位)&#xff1b; 1&#xff09;查看帮助 -h ./volatility_2.6_lin64_standalone -h 2&#xff09;获取内存镜像文件的信息 imageinfo ./volatility_2.6_lin64_stand…

SpringBoot pom.xml文件标签含义

Pom文件 基本构成 通过最简单的一个SpringBoot项目的 Pom文件来了解一下Pom文件的基本构成 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XML…

SpringBoot整合人大金仓数据库KingBase

1 去KingBase官网下载驱动jar包 2 将解压得到的所有jar包放置在libs目录下&#xff08;没有就新建一个目录&#xff09; 3 在pom文件添加相关依赖 <!--添加KingBase所需要的依赖--> <dependency><groupId>com.kingbase</groupId><artifactId>kin…

CentOS安装k8s单机/集群及一些命令

目录 前言 1. 安装docker 2. 安装要求 3.准备网络&#xff08;如果只装单机版可跳过此部&#xff09; 4. 准备工作 5. 安装 5.1. 配置阿里云yum k8s源 5.2 安装kubeadm、kubectl和kubelet 5.3 初始化&#xff0c;只在master执行&#xff0c;子节点不要执行 5.3.1 一些…

vue实现-年、月、日、时、分、秒、星期?

一、文章引导 #mermaid-svg-nP4oT3Y4d6oaxUsg {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-nP4oT3Y4d6oaxUsg .error-icon{fill:#552222;}#mermaid-svg-nP4oT3Y4d6oaxUsg .error-text{fill:#552222;stroke:#55222…

ubuntu系统(9):ubuntu 20.02安装pydot

目录 警告信息 1、确保安装了Python和pip 2、安装Graphviz软件包 3、pip安装pydot 验证 在gem5中&#xff0c;pydot库用于生成图形化输出&#xff0c;特别是生成.dot文件和相关的图像文件&#xff0c;如PDF、PNG等。它与gem5结合使用的一个常见用途是生成系统结构图、内存…

【华为】IPsec VPN 实验配置(动态地址接入)

【华为】IPsec VPN 实验配置&#xff08;动态地址接入&#xff09; 注意实验需求配置思路配置命令拓扑R1基础配置配置第一阶段 IKE SA配置第二阶段 IPsec SA ISP_R2基础配置 R3基础配置配置第一阶段 IKE SA配置第二阶段 IPsec SA PCPC1PC2 检查建立成功查看命令清除IKE / IPsec…

SpringBoot-开启Actuator监控

Spring Boot Actuator是Spring Boot提供的一种管理和监控应用程序的框架&#xff0c;可以帮助我们了解应用程序的运行状况&#xff0c;提供HTTP端点来暴露应用程序的不同方面&#xff0c;如健康状况、指标、日志和运行时信息等。 开启Actuator监控&#xff0c;我们可以通过HTT…