导读:本文包含了博弈树搜索算法论文开题报告文献综述及选题提纲参考文献，主要关键词:非合作博弈,微电网,布谷鸟搜索算法,多目标优化
博弈树搜索算法论文文献综述
曹瑛,刘建锋,范梦琪,叶涛[1]（2018）在《基于非合作博弈的布谷鸟搜索算法在微电网多目标优化中的应用》一文中研究指出在微电网多目标优化过程中,不同目标之间往往相互影响,相互制约。随着可再生能源的高比例接入,必然会对电网造成冲击,降低其稳定运行水平;同时联络线功率波动也会影响清洁能源的并网比重,从而无法保证可再生能源的充分利用。作为同时需要优化的主体,两者具有一定的效益冲突。为实现两者利益的最大化,采用一种基于二人零和博弈模型的线性加权法,得出Nash稳定策略下的最佳权重系数,并将该系数应用于风-光-储协调的混合发电系统多目标优化模型中,将多目标问题转化为单目标问题,再应用布谷鸟搜索算法(CS)对该模型进行求解。结果表明,较之传统多目标算法,该方法可以使微电网整体获得更大收益,既提高了可再生能源渗透率,又有效抑制了联络线随机功率波动。(本文来源于《上海电力学院学报》期刊2018年06期）
郭晓霞,韩燮,赵融[2]（2018）在《基于知识库的象棋机器博弈搜索算法研究》一文中研究指出为了解决重复局面导致时间资源和硬件资源的浪费问题,以中国象棋为研究对象,提出了一种构建计算机象棋(执红棋和执黑棋)博弈知识库的方法,知识库自动记录每次计算机"思考"时经过Alpha-Beta算法和历史启发算法搜索到的最佳走法和当前棋盘局面,下一次遇到相同局面时,直接检索知识库获取最佳对弈走法;使用Zobrist哈希技术中的一个哈希值来唯一标识一个棋盘局面,以减少知识库检索时造成的时间消耗;针对开局就使用Alpha-Beta算法搜索意义不大的问题,引入了多种专家开局走法。在Visual Studio C++环境下对时间消耗进行对比实验,结果证明了所提出知识库的有效性。(本文来源于《中国科技论文》期刊2018年20期）
李卓轩,李媛,冉冠阳,王静文[3]（2018）在《基于PVS搜索算法的亚马逊棋博弈系统的设计》一文中研究指出亚马逊棋是一种复杂度介于围棋和中国象棋之间的博弈游戏。其复杂性主要是具有极大的分支因子,在搜索过程中难以达到较高的深度。本文采用了PVS搜索算法,通过缩小剪枝窗口,从而有效增加剪枝效率,同时结合了历史启发增强和置换表技术,极大提高了搜索深度。使用该技术开发的亚马逊棋软件,其博弈水平得到了有效提高。(本文来源于《智能计算机与应用》期刊2018年05期）
季辉,丁泽军[4]（2018）在《双人博弈问题中的蒙特卡洛树搜索算法的改进》一文中研究指出蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显着改进了蒙特卡洛树搜索的准确性和效率。(本文来源于《计算机科学》期刊2018年01期）
季辉[5]（2017）在《双人博弈问题中的蒙特卡洛树搜索算法的改进》一文中研究指出人工智能是现在非常重要的研究领域,不仅仅在计算机领域,各行各业都有着广泛的运用。机器学习是人工智能的重要分支,随着机器学习方法的不断发展,人们对于人工智能的理解也有了更深层次的理解,从指导计算机学习逻辑推理,到教会计算机一些先验知识做成专家系统,到现在让计算机学会自我学习。不仅仅在于处理大数据上,人工智能有着广泛的运用,在指导人类制定策略上也有着更加重要的指导作用。双人博弈游戏中的AI算法就是人工智能的重要的发展方向与运用前景。AlphaGo的出现标志着双人博弈问题上的最大的难题围棋也被攻破,AlphaGo巧妙的将深度学习和蒙特卡洛树搜索算法,卷积神经网络等方法结合在一起,大大提升了围棋AI的计算效率,使得在人类规则下,计算机击败最优秀的职业棋手成为现实。AlphaGo的成功并不意味着现在的算法就是最优的,在研究过程中发现蒙特卡洛树搜索算法中还存在着不少的问题与隐患。蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这样复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,导致收敛慢。本文中我们指出,双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略;由此我们提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性导致失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,我们还结合了几种常见的剪枝策略。实验测试说明,该新算法显着改进了蒙特卡洛树搜索的准确性和效率。(本文来源于《中国科学技术大学》期刊2017-10-08）
南海[6]（2016）在《单回合的回合制战棋博弈模型搜索算法研究》一文中研究指出战棋博弈(Turn-Based War Chess,TBW)是回合制策略游戏(Turn-Based Strategy,TBS)的重要成分,但目前其人工智能关注度还不够。受限于战棋具有丰富多样的元素,目前还没有一个标准化的数学模型,从而导致了战棋博弈目前的研究还停留在较为简单的层次上。随着移动端游戏的井喷式发展,战棋博弈类游戏因其触屏操作、轻量级、碎片化时间而拥有更大的发展潜力,然而因其人机博弈部分智能低下,严重影响了用户体验和产品黏性,成为束缚其游戏性的瓶颈。战棋博弈本质上是由横向的组合优化问题和纵向的博弈树搜索问题结合的产物,既可以看作是一个分阶段的多智能体协同作业的规划问题,也可以看作是一个分支系数巨大的树搜索问题。所以,其背后潜藏着的对以上传统问题体系的扩充和发展,其研究意义都超出了对战棋游戏本身的研究。如今,基于大数据、云计算和机器学习的新一轮弱人工智能研究正在蓬勃兴起,使得运用更为有效的技术让战棋博弈的人工智能获得较大程度的提升成为了可能。本论文较为系统的分析了战棋博弈的特性,基于特征选择了从棋类博弈的角度来研究战棋的机器博弈。首先建立战棋游戏的通用博弈模型,提出横向的组合优化和纵向的博弈树搜索的理论框架,阐明横向分支系数巨大的关键难题,其次,针对横向问题提出单回合穷举搜索的按序枚举法和递归枚举法,并深入分析它们的性能和各自的适用性。随后就计算冗余问题提出两套优化策略——单位移动范围的简化和搜索空间的简化,通过理论实验证实了它们在不改变有效搜索空间的前提下能大幅的提高搜索效率。然后就搜索过程中比较耗时的单位移动范围计算,引入动态最短路径树(Dynamic Shortest Path Tree,DSPT)的新的研究方法,提出关于动态删除节点的MRDA_SPT(Multi-node Removed Dynamic Algorithm of Shortest Path Tree)改进算法,并通过理论分析和实验验证,该算法的效率均优于现有其他方法。最后,基于新算法又提出动态更新单位移动范围的DR_SPT(Dynamic Range Shortest Path Tree)算法,通过实验表明它能显着的提高计算移动范围的效率,从而整体上提升了战棋博弈单回合搜索速度。本论文的研究成果包括如下:(1)对战棋博弈进行建模和研究,并提出纵向和横向的研究框架。研究结果表明,本质上,战棋博弈属于二人(或多人)零和完全信息博弈,因其每回合全部棋子都可移动,并且移动顺序敏感的特点,战棋博弈构成了一个分支系数异常庞大的博弈树。本论文对该博弈树的规模进行了理论上的计算,并与其它主流棋类对比,发现战棋的博弈树分支系数会随着棋子的数量和每个棋子的移动范围的增大而急剧增大。最后,在博弈树理论的框架下就纵向和横向的研究路线给予了展望。(2)提出战棋博弈的单回合搜索算法并做完备性证明和性能比较。单回合搜索是战棋博弈树第一层展开的核心算法,其效率也是整个战棋博弈性能的关键指标。针对顺序优先还是行为优先提出了两种单回合搜索算法:1、按序枚举法;2、递归枚举法。它们的主要区别是选择不同的排列算法:前者采用字典序法,后者采用递归法,而它们体现出来了不同的搜索架构:前者基于序列,后者基于行动。从理论上证明了两个算法都是最优解的,并从理论和实验分析了他们效率的差别:棋子在所有位置上的扩展操作(ops1)的次数总和,递归枚举法比按序枚举法在各种条件下都有不同程度的减少。(3)就单回合搜索计算复杂度高、计算冗余的问题提出了两套优化策略——1、简化单位移动范围的计算;2、划分与简化搜索空间。通过理论证明和实验检验,证实了这两种策略可以在不改变有效搜索空间的前提下大幅的提高搜索效率。(4)提出MRDA_SPT改进算法,提升了动态最短路径树(DSPT)关于节点动态删除的效率。首先对动态最短路径树(DSPT)进行了较为系统的研究,并针对前人的工作当中DSPT动态节点删除算法存在冗余的问题提出了新算法——MRDA_SPT改进算法,从理论上分析其复杂度,通过与目前较快的算法做对比实验,表明了MRDA_SPT改进算法具有更高的效率和更快的运行速度。(5)提出高效率动态计算单位移动范围的DR_SPT算法并通过实验验证其高效性。实验分析出战棋博弈搜索的一个重要的耗时计算是对棋子移动范围的计算,根据移动范围在搜索算法中会动态改变这一特点,提出基于动态最短路径树和MRDA_SPT改进算法的DR_SPT算法,该算法对棋子移动范围做增量计算,从而大大提高了搜索中棋子移动范围计算的速度,并从整体上提高战棋博弈搜索的效率。(本文来源于《重庆大学》期刊2016-09-01）
高强[7]（2016）在《计算机博弈问题的复杂性、理论解及相关搜索算法研究》一文中研究指出计算机博弈就是计算机下棋。图灵测试便是要通过下棋检测计算机智能水平的高低。计算机博弈属于人工智能领域的一个重要分支。计算机的博弈水平代表了计算机的智能水平。让计算机能够战胜人类高手,并处于不败之地,一直是国内外学者们致力于研究的目标。1997年的“深蓝”战胜了国际象棋大师卡斯帕洛夫,这在世界上反响巨大,它表明计算机可以战胜人类天才。这在一定程度上说明计算机思考问题的能力已经更加接近于人脑了。冯诺依曼和摩根斯坦早在1944年,就在他们的《博弈论及经济行为》一书中提出了二人零和博弈理论。而棋类博弈问题是这一理论的具体表现。实现计算机博弈问题的理论解(即不败解)一直都是全世界机器博弈研究学者梦寐以求的事情。近年来,随着计算机硬件水平的不断提高,一些博弈问题已被求解,比如:四子棋(Connect Four)、五子棋(Go-moku)和西洋跳棋(Checkers)等等。但是对于一些复杂度很高的棋类问题(如:中国象棋、日本将棋和围棋等),学者们在研究这些问题的理论解时,还停留在求解这些棋类的残局问题上。尽管现在硬件水平在迅速的提高,但还是需要将研究重点放在博弈问题的理论上,诸如:博弈问题的计算复杂性、状态复杂度和博弈树复杂度、理论解求解途径及相关搜索算法等。本文主要围绕求解计算机博弈问题做了深入的研究工作,为了从理论角度探讨求解计算机博弈问题的难易程度,全面研究了计算复杂性理论并实现了对中国象棋的计算复杂性证明;研究了博弈问题的状态复杂度和博弈树复杂度的估算方法,并根据这两个数值来决定各种博弈问题应该采取哪一种求解策略;针对当前求解博弈问题比较常用的一种搜索算法-证据计数法(PNS,Proof-number search),提出了一种改进的PNS算法;以牛角棋和六子棋为例,研究了求解这两个博弈问题应该采取的具体方法。此外,还从全局的角度研究和综述了博弈问题的主流搜索算法。概括起来本文主要研究成果有以下几点:介绍并分析了计算理论的一些基本概念,论述了时间复杂性和空间复杂性中的各个主要分类(包括:P、NP、NP-complete、PSPACE、PSPACE-complete、EXPTIME、EXPTIME-complete等),分析了各个复杂性类之间的关系;并给出了NP问题为非多项式时间问题的推论;重点研究了中国象棋的计算复杂性,构建了一个n×n的中国象棋归约模型,在该模型上模拟进行G3游戏,并最终证明了 G3游戏可多项式时间内归约到n×n的中国象棋,进而证明了中国象棋属于EXPTIME-complete问题。阐述了计算机博弈问题的状态复杂度和博弈树复杂度的估算方法。在常见的复杂度估算方法的基础上,根据不同博弈问题的走棋特点,对估算过程中可能存在的一些非法局面进行了分析和排除,并详细地估算了亚马逊棋、苏拉卡尔塔棋的状态复杂度和六子棋、点格棋的博弈树复杂度。介绍了计算机博弈问题理论解相关的一些理论知识,并且综述了五子棋、8 X8西洋跳棋以及围棋的残局被求解的思路以及所采用的核心技术。以牛角棋为例,分析了求解牛角棋应该采取的求解策略,实现了对牛角棋的求解。提出了一种基于连珠类型的六子棋求解策略,阐述了该求解策略的算法构成,主要包括基于连珠类型的走法生成器、一种基于迫着数的算法(即alpha-beta剪枝和TSS的混合算法)调用策略和证据计数法。以7X7棋盘规模的六子棋开局为例,验证了这一求解策略具有较强的求解能力。在搜索算法方面,详细阐述了基于与或树的证据计数法原理,综述了证据计数法在一些落子类博弈系统中的应用;论述了证据计数法和PN2算法的缺陷,基于PN2算法,本文提出了一种两级的PN算法,即PN-DFPN,通过实验证明,PN-DFPN在搜索效率和求解能力上都要优于PN2;此外,论述了非合作动态博弈问题的复杂度和理论解以及两者的关系,并综述了该类博弈问题的基本搜索算法和一些基于alpha-beta的高级搜索算法,还详细阐述了当前广泛应用于非合作动态博弈问题中的几种新算法。本文对提出的算法、方法和结论给出了理论证明,并且通过了实验验证,这对今后实现求解复杂度更高的博弈问题提供了理论支持和有益方法。(本文来源于《东北大学》期刊2016-03-10）
李阳[8]（2015）在《中国象棋博弈树搜索算法的研究与实现》一文中研究指出计算机博弈是人工智能研究最早承担的任务之一。相比于成熟的国际象棋计算机博弈,中国象棋计算机博弈的研究还比较滞后。随着人工智能技术的发展,中国象棋计算机博弈问题逐渐吸引了越来越多的学者投入其中。本文在研究国际象棋计算机博弈成熟技术的基础上,结合近年来中国象棋计算机博弈的发展,对着法生成器中核心的博弈树搜索算法进行了深入的研究。首先,对中国象棋博弈系统进行深入的研究,设计了象棋系统中各种数据结构,实现了着法生成器和局面评估函数。其次,对基于穷尽搜索策略的各种剪枝算法进行了研究,采取迭代深化方法避免了“水平效应”引发的战略性错误。再次,研究了基于最佳优先搜索策略的B*算法,针对B*算法过于依赖评估函数的问题,设计并实现了基于概率的BSP搜索算法。最后,在VC++6.0的环境下,构建了中国象棋人机对弈系统,并根据不同搜索策略,实现了以剪枝搜索算法为核心的着法生成器和基于概率的BSP搜索算法的着法生成器。通过棋局分析和人机对弈对以上着法生成器进行了分析和比较。实验结果证明采用BSP搜索算法效率高、着法更准确。(本文来源于《燕山大学》期刊2015-05-01）
何利[9]（2014）在《基于混沌搜索算法的铁矿石贸易Stackelberg博弈均衡研究》一文中研究指出构建了二层规划的铁矿石贸易双寡头二级供应链Stackelberg博弈模型,运用混沌搜索算法进行了案例分析。案例数据表明:铁矿石生产商决策的Stackelberg博弈均衡解没有实现整体最优和个体最优,但如果没有合作却是均衡结果;整体最优实现了铁矿石供应商和钢铁生产商的收益优化,但却没有实现均衡,因为钢铁生产商有改进决策增加收益的可能性来背离合作;钢铁生产商改变全局最优会损害铁矿石生产商的收益,降低整体供应链的收益。(本文来源于《资源开发与市场》期刊2014年11期）
汪孔斌,尹弼民[10]（2013）在《基于博弈论的启发式搜索算法的改进研究》一文中研究指出基于博弈理论提出了一种路径搜索问题的优化算法。将路径搜索问题的搜索空间映射为博弈的策略组合空间,而路径搜索问题的目标函数映射为博弈的效用函数,通过遍历博弈支持集搜索纳什均衡解,并利用启发思想根据博弈的结构制定搜索策略,以期望用最小的代价减少搜索节点数、提高应用系统的性能及效率。(本文来源于《铜陵职业技术学院学报》期刊2013年04期）
博弈树搜索算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
为了解决重复局面导致时间资源和硬件资源的浪费问题,以中国象棋为研究对象,提出了一种构建计算机象棋(执红棋和执黑棋)博弈知识库的方法,知识库自动记录每次计算机"思考"时经过Alpha-Beta算法和历史启发算法搜索到的最佳走法和当前棋盘局面,下一次遇到相同局面时,直接检索知识库获取最佳对弈走法;使用Zobrist哈希技术中的一个哈希值来唯一标识一个棋盘局面,以减少知识库检索时造成的时间消耗;针对开局就使用Alpha-Beta算法搜索意义不大的问题,引入了多种专家开局走法。在Visual Studio C++环境下对时间消耗进行对比实验,结果证明了所提出知识库的有效性。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
博弈树搜索算法论文参考文献
[1].曹瑛,刘建锋,范梦琪,叶涛.基于非合作博弈的布谷鸟搜索算法在微电网多目标优化中的应用[J].上海电力学院学报.2018
[2].郭晓霞,韩燮,赵融.基于知识库的象棋机器博弈搜索算法研究[J].中国科技论文.2018
[3].李卓轩,李媛,冉冠阳,王静文.基于PVS搜索算法的亚马逊棋博弈系统的设计[J].智能计算机与应用.2018
[4].季辉,丁泽军.双人博弈问题中的蒙特卡洛树搜索算法的改进[J].计算机科学.2018
[5].季辉.双人博弈问题中的蒙特卡洛树搜索算法的改进[D].中国科学技术大学.2017
[6].南海.单回合的回合制战棋博弈模型搜索算法研究[D].重庆大学.2016
[7].高强.计算机博弈问题的复杂性、理论解及相关搜索算法研究[D].东北大学.2016
[8].李阳.中国象棋博弈树搜索算法的研究与实现[D].燕山大学.2015
[9].何利.基于混沌搜索算法的铁矿石贸易Stackelberg博弈均衡研究[J].资源开发与市场.2014
[10].汪孔斌,尹弼民.基于博弈论的启发式搜索算法的改进研究[J].铜陵职业技术学院学报.2013