检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

五子棋人机博弈算法的研究及改进

计算机与数字工程 2024年第4期52卷 963-965,972页

作者：符秀辉谷文通沈阳化工大学信息工程学院沈阳110142

如今人工智能的领域正在不断延伸,计算机博弈如今已经成为了人工智能中很重要的一个领域。论文以五子棋为研究对象,简要介绍了五子棋游戏中几种常用的搜索算法:α-β剪枝算法,置换表搜索算法,迭代加深算法和uct算法,并分别将几种算法应... 详细信息

如今人工智能的领域正在不断延伸,计算机博弈如今已经成为了人工智能中很重要的一个领域。论文以五子棋为研究对象,简要介绍了五子棋游戏中几种常用的搜索算法:α-β剪枝算法,置换表搜索算法,迭代加深算法和uct算法,并分别将几种算法应用到五子棋系统中做实验,实验结果证明uct算法相较其他几种算法胜率更高。并在此基础上提出改进uct算法,改进的方法是将强化学习算法和uct算法相结合,有利于进一步提高五子棋系统胜率。

关键词：人工智能计算机博弈五子棋 uct算法

在线全文

学校读者我要写书评

暂无评论

基于改进uct算法的国际跳棋博弈系统研究

智能计算机与应用 2022年第1期12卷 128-131页

作者：张家铭王静文李媛沈阳工业大学理学院沈阳110870

国际跳棋的博弈系统中,uct算法是一个比较新颖的算法,其效果得到了广泛认可。但是uct算法的缺点也同样明显,终局下的处理明显不如稳定性更强的Alpha-Beta算法。为避免uct算法的不稳定性,本文采取限制搜索深度和增加扩展条件的方法对uct... 详细信息

国际跳棋的博弈系统中,uct算法是一个比较新颖的算法,其效果得到了广泛认可。但是uct算法的缺点也同样明显,终局下的处理明显不如稳定性更强的Alpha-Beta算法。为避免uct算法的不稳定性,本文采取限制搜索深度和增加扩展条件的方法对uct算法进行改进,改进后的uct算法胜率远超过改进前的uct算法胜率,使得博弈水平得到了极大的提升。

关键词：国际跳棋 uct算法 Alpha-Beta算法 uct算法的不稳定性

在线全文

学校读者我要写书评

暂无评论

改进uct算法在爱恩斯坦棋中的应用

计算机科学 2018年第12期45卷 196-200页

作者：张小川李琴南海彭丽蓉重庆理工大学计算机科学与工程学院重庆400054 重庆工业职业技术学院科研处重庆401120

uct(Upper Confidence Bound Apply to Tree)算法是蒙特卡罗搜索算法的延展,因其鲁棒性强而受到广泛关注,且被应用于计算机博弈系统。爱恩斯坦棋是近年国内博弈大赛引进的新棋种,在竞赛中投骰子所引发的随机性和娱乐性吸引了广大学者的... 详细信息

uct(Upper Confidence Bound Apply to Tree)算法是蒙特卡罗搜索算法的延展,因其鲁棒性强而受到广泛关注,且被应用于计算机博弈系统。爱恩斯坦棋是近年国内博弈大赛引进的新棋种,在竞赛中投骰子所引发的随机性和娱乐性吸引了广大学者的目光。从全局优化着法角度出发,在爱恩斯坦棋博弈系统中引入uct算法。首先,针对当前计算机多核现状,利用并行计算方法进一步优化uct算法;其次,针对uct算法的最优着法需求,引入当前估值因子(WINK)和次优节点平衡因子(uctK),以此辅助增加估值的精确度,决策胜率与着法的优先关系,提高算法的收敛效率;最后,构造了爱恩斯坦棋博弈系统,通过与基于极大极小算法、α-β算法以及蒙特卡罗算法的爱恩斯坦棋博弈系统进行机-机对弈,其胜率提高了25%,并在全国计算机博弈大赛中获冠军,这进一步验证了改进算法的有效性。

关键词： uct算法爱恩斯坦棋并行计算平衡优化

在线全文

学校读者我要写书评

暂无评论

基于预期收益策略与uct的德州扑克算法

重庆理工大学学报（自然科学） 2021年第3期35卷 166-173页

作者：王亚杰丁傲冬祁冰枝张云博沈阳航空航天大学工程训练中心沈阳110135 沈阳航空航天大学计算机学院沈阳110135

针对虚拟遗憾最小化算法和传统上限置信区间算法等过于依赖领域知识或者需要大量对局记录训练的问题,以二人无限注德州扑克为研究对象,提出了基于预期收益策略的改进uct算法。首先,使用蒙特卡罗方法即多次随机生成对方底牌和未知公共牌... 详细信息

针对虚拟遗憾最小化算法和传统上限置信区间算法等过于依赖领域知识或者需要大量对局记录训练的问题,以二人无限注德州扑克为研究对象,提出了基于预期收益策略的改进uct算法。首先,使用蒙特卡罗方法即多次随机生成对方底牌和未知公共牌,然后比较双方牌型大小,计算己方胜率;其次,根据己方胜率和己方动作下注量计算预期收益并根据每个动作的预期收益,选择一个最大的动作作为下一步;最后,根据己方胜率与对手下注量评估对手胜率,从而将预期收益策略作为对手策略模型应用在传统uct算法中。在开局筹码量为20 000的情况下,改进后的uct算法与基于预期收益策略实现的德州扑克程序THPZZ进行100局的对弈,平均每局赢得的筹码量为655,水平显著高于THPZZ。

关键词： uct算法蒙特卡罗德州扑克预期收益对手胜率评估非完备信息博弈

基于静态评估的计算机围棋uct算法改进研究

在线全文

学校读者我要写书评

暂无评论

基于静态评估的计算机围棋UCT算法改进研究

作者：张玉琪南昌航空大学

学位级别：硕士

计算机博弈是人工智能研究的重要领域之一,棋类博弈又是计算机博弈中的重要分支,目前其他棋类博弈均得到了较圆满的解决,唯有计算机围棋的最高水平还不及人类的初级棋手。围棋是检验人工智能发展水平的试金石,开发出与职业棋手程度相当... 详细信息

计算机博弈是人工智能研究的重要领域之一,棋类博弈又是计算机博弈中的重要分支,目前其他棋类博弈均得到了较圆满的解决,唯有计算机围棋的最高水平还不及人类的初级棋手。围棋是检验人工智能发展水平的试金石,开发出与职业棋手程度相当的计算机围棋程序有助于对人类认知科学的探索。对当前棋局做出准确高效的静态评估不仅有利于棋手判断当前局势,确定攻防着点,引导下一步棋的走向,而且能够指导信心上界树(Upper Confidence bounds applied to Trees,简称为uct)算法平衡探索与利用。本文提出了一种棋子影响函数,并在此基础上构建了一个量化模型来解决棋局的静态评估问题;然后将静态评估结果与uct算法相结合,构造出一种uct剪枝策略。本文所设计的算法可以提高程序的运行效率,从而提升程序棋力,具有一定的理论研究意义与实际应用价值。本文主要研究成果有:(1)设计了一种棋子的影响函数Influ。过去的影响函数通常没有考虑到对方棋子的阻挡问题,从而造成计算影响值时精度较低。本文采用直线和斜线距离相结合的方式来表征棋子到空点的距离,并利用A*算法进行路径寻优,最终获取单个棋子对空点的影响值;(2)基于Influ棋子影响函数,构造Value全局静态评估量化模型。首先,将单个棋子对空点的影响值线性叠加;然后,进行边角调整、阈值规范和归一化操作等处理步骤,获得棋盘上所有空点受到的总的影响值;最后,使用多级种群竞争消亡法优化模型参数,最终得到Value量化模型。实验表明,Value模型的计算结果与职业棋手的判断非常接近,计算精度适用于棋局的序盘和中盘阶段,为后续的剪枝策略奠定了基础;(3)将Value模型获得的静态评估结果与uct算法相结合,构造剪枝策略Static。利用静态评估值作为节点的评分标准,以此减少搜索深度,从而在单位时间内增加蒙特卡罗模拟次数,并指导搜索偏向有意义的方向。实验表明,Static剪枝策略可以提高搜索效率,进而提升程序的棋力。

关键词：计算机围棋静态评估 uct算法

基于uct算法和深度强化学习的非完备博弈策略研究与应用

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于UCT算法和深度强化学习的非完备博弈策略研究与应用

作者：沈恒恒安徽大学

学位级别：硕士

计算机博弈在人工智能领域中占据着重要的地位,是极具挑战性的研究方向。近年来,非完备信息博弈研究成为了检验人工智能发展的重要试金石。现实世界中存在很多的非完备信息博弈场景,例如经济交易、军事博弈、自动驾驶等。因此,对非完备... 详细信息

计算机博弈在人工智能领域中占据着重要的地位,是极具挑战性的研究方向。近年来,非完备信息博弈研究成为了检验人工智能发展的重要试金石。现实世界中存在很多的非完备信息博弈场景,例如经济交易、军事博弈、自动驾驶等。因此,对非完备信息博弈问题的研究具有非常重要的现实意义。掼蛋是一种由四个玩家分为两队进行对抗的非完备信息牌类游戏,存在着随机性、信息隐藏性等特点。在每局掼蛋游戏中存在两张红心级牌,导致决策节点数目呈指数级增长。传统的博弈树搜索算法存在着信息预测不准确、冗余节点多和搜索效率低的问题,不适用于掼蛋博弈。而uct(Upper Confidence Bound Apply to Tree)算法以一种非对称的形式动态扩展博弈树,非常适合博弈树规模较大的情况。本文针对掼蛋博弈的特点改进了uct算法,一方面设计手牌拆分算法用于扩展博弈树,另一方面对博弈树节点进行并行优化,提出了基于手牌拆分的并行uct(Parallel uct based on Hand Splitting)算法。虽然树搜索算法可以充分的利用计算机的算力,但是掼蛋游戏中存在的巨大隐藏信息导致了高维度的博弈状态,使得树搜索算法在提升掼蛋智能体的博弈水平上受限,难以达到在完备信息游戏中的智能效果。强化学习算法有着高效的策略搜索能力,但是难以在信息不完全、高维度的状态空间的情况下收敛。本文针对上述问题引入了基于深度强化学习的近端策略优化(Proximal Policy Optimization,PPO)算法解决信息不完全、高维度的状态空间与动作空间问题。使智能体能够感知高维信息,根据输入的牌局状态得到出牌动作。论文的创新点和主要工作如下:(1)针对非完备信息预测不准确,传统博弈树中存在的冗余节点多和搜索效率低的问题,设计了信息预测模块用于对牌局中隐藏信息的预测,并提出了手牌拆分算法用于扩展博弈树,有效的减小博弈树的规模。将节点并行化处理,提高树搜索效率。通过实验验证,基于手牌拆分算法的并行uct算法有着较高的搜索效率和智能水平。(2)针对掼蛋的高维度动作和状态空间问题,本文研究并设计了基于PPO算法的策略-价值网络。首先,从牌局中提取696维的特征向量,设计神经网络模型。其次,设计了样本数据采集、策略-价值网络训练的自学习过程。最后通过实验验证,基于PPO算法的策略-价值网络经过训练后高于Policy Gradient算法和A2C算法的智能水平。(3)本文在研究掼蛋博弈策略的基础上,设计并实现了掼蛋博弈系统。它包括深度强化学习训练子系统和人机交互对弈子系统。训练子系统用于管理神经网络的样本采集、自学习过程。人机交互对弈子系统可进行策略选择,提供了人-人、人-机和机-机自动对弈功能,并存储对弈过程。综上所述,本文在搜索技术和深度强化学习算法两个方面进行研究。首先将应用于掼蛋博弈中的uct算法进行了改进和并行化,提升算法的搜索效率和智能水平;其次设计了基于PPO算法的策略-价值网络及其训练过程;通过对比实验,验证了基于PPO博弈算法具有更高的智能水平;最后实现了掼蛋博弈系统,为掼蛋博弈策略的研究建立了一个完善的算法设计、分析、验证的实验平台。

关键词：非完备信息博弈掼蛋深度强化学习近端策略优化算法 uct算法

基于uct算法的非完备信息多人军棋博弈系统

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于UCT算法的非完备信息多人军棋博弈系统

作者：张加佳哈尔滨工业大学

学位级别：硕士

博弈游戏的分类方法之一是根据其游戏的参与者是否拥有完备的游戏信息。据此,博弈游戏可以被分为完备信息博弈和非完备信息博弈两个大类。在非完备信息博弈过程中,每个游戏者拥有自己单独的信息集,也就是说,他只拥有整个游戏的部分信息... 详细信息

博弈游戏的分类方法之一是根据其游戏的参与者是否拥有完备的游戏信息。据此,博弈游戏可以被分为完备信息博弈和非完备信息博弈两个大类。在非完备信息博弈过程中,每个游戏者拥有自己单独的信息集,也就是说,他只拥有整个游戏的部分信息。围绕着完备信息博弈的研究已经取得了相对成熟的结果。很多人工智能程序的核心架构是:当电脑走棋的时候,根据当前棋局创建一个部分的博弈树,利用估值函数对叶结点进行估值,通过估值的结果来进行极大极小值搜索,找到一个在根结点的最佳走步。然而,迄今为止非完备信息下的非常成功的人工智能博弈程序很少。非完备信息博弈问题的解决技术和完备信息有很大的差异,应用于完备信息的技术不一定能够成功的应用到非完备信息博弈中。蒙特卡罗抽样算法是现今应用于非完备信息博弈中的一个基本方法,它通过随机抽样将非完备信息博弈问题转换为完备信息博弈问题,同时通过大规模的抽样次数来逼近真实的情况。该方法在一些非完备信息博弈游戏中,例如Alberta的桥牌程序,已经取得了较好的效果。uct (Upper Confidence Bound Apply to Tree):应用于博弈搜索树的上限置信区间算法。这种新兴的搜索算法采用以上限置信值为依据的先深于先广搜索相结合的方法,在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上,可以在可控的时间内得到当前局势下的相对较优的解决方案。本文探讨了uct算法在非完备信息博弈中超大规模搜索树搜索过程中的应用,并基于该算法结合蒙特卡罗抽样技术和风险评估模型实现了一个具有自动网上挂载功能的四国军棋博弈系统。本文的主要研究成果和创新之处在于:1.实现了uct搜索算法,并将之应用为博弈系统的搜索核心。提高了系统的搜索速度和深度;2.进一步扩充和精确化了四国军旗博弈中的蒙特卡罗抽样技术;3.在已有四国军棋的框架系统上,将蒙特卡罗抽样技术、uct算法和一个简单的风险模型有效结合成了一个具有更强的博弈能力和更高的人工智能水平的新系统。4.新的四国军棋系统可以自动挂载到网络和人类玩家进行博弈,该功能解决了系统棋力客观评估的问题,同时使大规模博弈过程以及对局信息数据库的建立成为了可能。

关键词： uct算法非完备信息博弈蒙特卡罗抽样风险评估模型自动博弈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

点格棋博弈中uct算法的研究与实现

点格棋博弈中UCT算法的研究与实现

作者：刘洋安徽大学

学位级别：硕士

2016年3月谷歌AlphaGo击败世界围棋冠军李世石九段,使人工智能、机器博弈再次成为大众焦点。人工智能是计算机科学的重要研究方向,主要研究用机器来模拟和执行人脑的智力功能,开发相关的理论和技术,从而达到让机器可以能像人一样进行学... 详细信息

2016年3月谷歌AlphaGo击败世界围棋冠军李世石九段,使人工智能、机器博弈再次成为大众焦点。人工智能是计算机科学的重要研究方向,主要研究用机器来模拟和执行人脑的智力功能,开发相关的理论和技术,从而达到让机器可以能像人一样进行学习、思考、判断等各种脑力活动的目标。机器博弈因使用计算机解决博弈问题而得名,它将博弈思想和计算机科学相融合,希望计算机能像人一样做出理性决策。机器博弈作为人工智能极具挑战的分支之一,一直以来都被誉为人工智能的“果蝇”,机器博弈的研究对于人工智能的发展具有积极的推动作用。机器博弈在国外的发展较早,并取得了一定的成就;在国内的发展还比较缓慢,以棋类为载体是目前研究机器博弈的主要方法。点格棋是法国数学家爱德华·卢卡斯在1891年提出的二人纸笔游戏。点格棋博弈系统主要由知识表示、着法生成、搜索算法和估值函数四部分组成,其中搜索算法是核心。搜索算法根据当前局面生成一颗一定深度的博弈树,对博弈树进行向下搜索,传统的点格棋博弈系统所采用的搜索算法多为α-β剪枝算法,采用α-β剪枝算法存在搜索深度浅、浪费时间等问题。另一方面α-β剪枝算法必须有一个估值函数对棋盘的优劣进行评估。目前常采用的估值方法当棋盘中不存在安全边的时候会比较准确,但是如果棋盘中含有安全边,估值会由于安全边占领的顺序不同而存在误差,所以点格棋博弈系统的估值函数设计相对较难。uct算法是蒙特卡洛算法的一种延伸算法,根据大数定理以多次模拟的方式实现对博弈树中节点的价值评估,同时将UCB算法应用到博弈树搜索上,通过UCB算法选择进行评估的节点,引导博弈树向更好的方向生长,有利于更快的获得最优解。uct算法根据大量模拟棋局的结果以概率的方法进行盘面优劣的判断,预估节点的好坏,优先选择表现好的节点。这种方法解决了点格棋目前存在的盘面评估问题。将uct算法应用到点格棋博弈,最后通过实验证明采用uct算法的点格棋博弈系统博弈水平高于α-β剪枝算法。根据点格棋博弈过程中棋盘会存在许多价值相同的边即等价边,这些边选择其中任意一条边进行搜索,与对这些全部进行搜索产生的结果相同,在进行博弈树搜索时只需要对其中一条边进行搜索,据此提出基于等价边裁剪的uct算法在uct算法拓展节点阶段进行等价边裁剪。最后通过实验证明改进算法能够减少博弈树搜索时搜索节点的数量,大幅度提高uct算法的博弈水平。在uct算法模拟棋局阶段,为提高模拟棋局结束后收益值计算的准确性,在原有计算方法的基础上提出了基于修正值的收益值计算方法,不仅对模拟棋局胜负进行了区分,还对胜负的程度进行了量化,使收益值更加的精确;其次,为提高模拟棋局的次数,实现了基于多核CPU的uct算法的并行化,充分利用了多核CPU的计算性能,提高棋局的模拟数量。综合以上两点改进提出基于修正收益值的并行uct算法,通过实验证明基于修正收益值的并行uct算法可以提高博弈树搜索深度和模拟棋局数量,使uct算法的博弈水平更高。本文的创新点如下：1.在认真分析点格棋博弈中经常使用的搜索算法后,发现uct算法相对于传统的α-β剪枝算法有着时间和空间方面的优势,将uct算法运用到点格棋博弈中。2.提出基于等价边裁剪的uct算法：给出等价边的定义,在拓展之前进行等价边裁剪,减少博弈树的搜索空间,提高博弈水平。3.提出基于修正收益值的并行uct算法,包括两个方面改进：第一,提出基于修正值的收益值计算方法,对胜负程度进行区分、量化,提高收益值准确性;第二,为充分利用了计算机性能,提高模拟棋局次数,实现了uct算法的并行化。

关键词：点格棋机器博弈 uct算法等价边修正收益值

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

军棋机器人uct算法及计算机博弈行为研究

军棋机器人UCT算法及计算机博弈行为研究

作者：王宛宛重庆理工大学

学位级别：硕士

机器人技术是当今世界备受关注的前沿课题,伴随着近年来人工智能技术不断的发展,机器人技术也成为了一个令人浮想联翩的技术领域。本文以大家喜闻乐见的中国传统的非完备信息二人军棋计算机博弈作为研究对象,军棋博弈的每方拥有25个棋子... 详细信息

机器人技术是当今世界备受关注的前沿课题,伴随着近年来人工智能技术不断的发展,机器人技术也成为了一个令人浮想联翩的技术领域。本文以大家喜闻乐见的中国传统的非完备信息二人军棋计算机博弈作为研究对象,军棋博弈的每方拥有25个棋子、12种类型棋子,每个棋子的级别、灵活性、价值都不相同,且双方都对彼此的策略一无所知,只能靠推理猜测决定走步,博弈过程中既要学会预防对方的欺骗又要学会蒙骗对手,加入机器人技术的情感识别能够帮助计算机博弈算法更好的识别对方策略,减少因对手欺骗而造成的损失,进而提升计算机博弈程序的战斗力。论文创新工作体现在如下几点:1)利用历史启发表来指导蒙特卡罗算法对敌方棋子隶属度进行模拟,极大的节省了模拟时间,并在我方棋子估值上针对军棋棋子种类多,估值缺乏适时性等问题上提出一种基于探索与收益均衡思想的Q-learning学习算法,完善了博弈过程中的动态估值系统,提高了估值的时效性。2)提出基于uct搜索策略的高价值棋子筛选方法,形成一种多棋子协同博弈方法,实现了多棋子协同对弈,提升了军棋计算机博弈系统中棋子的团体协同性、沟通性、欺骗性、引诱性等高级对抗能力。3)结合博弈机器人意图情感建模理论技术和计算机博弈智能决策算法,提出军棋博弈机器人的行为体系二次构造过程,提升了军棋计算机博弈系统抗欺诈能力。论文作者通过对军棋计算机博弈AI程序估值以及搜索算法上的修改并将程序命名为“KnighTeam-KS”跟随实验室计算机博弈团队参加了2018年安徽大学主办的中国大学生计算机博弈大赛暨第十二届中国计算机博弈锦标赛,并获得全国一等奖,验证了研究成果的可行性。并结合此系统与机器人技术对博弈行为进行二次规划,提高计算机博弈更好与人互动的趣味性。

关键词：军棋 uct算法动态估值协同博弈行为规划