基于alpha-beta剪枝搜索算法的中国象棋游戏设计

设计一个优秀的中国象棋游戏具有一定的经济与社会价值。但是在该系统的设计过程中,搜索算法的设计异常重要,如何设计合理的人机搜索算法实现高效和合法的行棋规则就成为我们研究的重点。文章通过对常用的人机搜索算法进行介绍,并对其进行了分析和应用。

中国象棋Alpha-Beta搜索算法的研究与改进

针对中国象棋机器博弈中较为高效的Alpha-Beta搜索算法进行研究,以提升其效率.依据Alpha-Beta搜索算法的效率与子节点扩展的排列顺序高度相关的事实及中国象棋自身的特点,本研究从优化着法的排列顺序入手,设计出了启发能力较强的着法排列方案,并进一步提出了扩大窗口的内部迭代加深算法对上述着法排列方案进行修正,从而使着法顺序得到了进一步的优化.实验数据证明,本研究明显提升了Alpha-Beta算法的效率.

改进的模板匹配金字塔搜索算法

针对模板匹配和智能检索技术对效率的要求,提出了改进的金字塔分层搜索算法,分别从算法剪枝和并行匹配两方面对算法进行改进。采用边缘梯度作为基础匹配描述子,改进的搜索算法融合了预先终止、匹配进程中终止、边缘点稀疏、逐层重叠筛选四种方法来降低算法的搜索空间复杂度。在算法中引入PPL并行库实现了多模板的并行匹配。实验结果显示,选择合适的参数,针对特定的模板匹配任务,改进后的金字塔搜索算法在保证准确检测目标的基础上,与传统的金字塔搜索算法相比效率提升56.3%。

基于剪枝法的Costas阵列通用搜索算法

给出了一种基于剪枝法的Costas阵列通用搜索算法 .由于采用了剪枝法 ,在遍历过程中剪去了不满足Costas阵列条件的分枝 ,这样既避免了大量不必要的回溯 ,又在遍历的同时生成了Costas阵列 ,而不需另外判断是不是Costas阵列 ,因而比遍历加判断的回溯算法效率更高 .用汇编语言程序实现了该算法 ,并穷尽地求出了一定阶数 (1≤n≤ 2 0阶 )的所有Costas阵列 ,实验结果表明杨义先等关于Costas阵列的第 4猜想不成立 .

基于α-β剪枝算法的五子棋游戏设计与实现

五子棋是一种两人对弈的策略类游戏,极易上手,深受人们喜爱。在此设计并研发了一种基于α-β剪枝智能搜索算法的人机对弈五子棋游戏,在原游戏趣味性和娱乐性的基础上增加了智能性与挑战性。经测试,该程序具有较高智能,可以击败有一定基础的游戏玩家,在休闲娱乐中能够帮助玩家提升棋艺,具有一定的实用性。

五子棋中Alpha-Beta搜索算法的研究与改进

对五子棋中Alpha-Beta搜索算法进行研究。依据五子棋的特点,提出一种局部搜索的算法,该算法可直接减少搜索的平均分枝因子。结合Alpha-Beta搜索算法效率与子节点着法顺序高度相关的特点,给出静态评价启发以及迭代深化的方法优化着法顺序。实验结果表明,该方法能提升Alpha-Beta搜索算法的效率。

多种搜索算法的五子棋博弈算法研究

主要选择五子棋为研究对象,应用Alpha-Beta剪枝算法、置换表技术搜索算法,研究人工智能模拟人类思考的推算过程,实现博弈效果。在Alpha-Beta剪枝算法中引入迭代加深以及局部搜索方法,提高程序棋技。在此基础上使用Monte Carlo方法和深度学习方法结合的方式来提高下棋技巧。实验结果表明,该算法相比于上述几种方法有明显的改进。

博弈树搜索算法研究

通过讨论人工智能中用于计算机博奕的一般技术如极大极小搜索、Alpha-Beta剪枝、小窗口搜索,对五子棋博奕的内在规律进行了分析研究,给出解决五子棋博奕的2种优化算法,这2种优化算法大大提高了搜索效率,相比之下引入置换表后的优化算法的搜索效率更高。

基于知识库的象棋机器博弈搜索算法研究

为了解决重复局面导致时间资源和硬件资源的浪费问题,以中国象棋为研究对象,提出了一种构建计算机象棋(执红棋和执黑棋)博弈知识库的方法,知识库自动记录每次计算机"思考"时经过Alpha-Beta算法和历史启发算法搜索到的最佳走法和当前棋盘局面,下一次遇到相同局面时,直接检索知识库获取最佳对弈走法;使用Zobrist哈希技术中的一个哈希值来唯一标识一个棋盘局面,以减少知识库检索时造成的时间消耗;针对开局就使用Alpha-Beta算法搜索意义不大的问题,引入了多种专家开局走法。在Visual Studio C++环境下对时间消耗进行对比实验,结果证明了所提出知识库的有效性。

智能搜索算法在棋类零和博弈中的应用

介绍了3种智能搜索算法及人机博弈的一种形式——零和博弈,并通过一个实例——中国象棋介绍了智能搜索算法在棋类零和博弈游戏中的应用。

机器博弈及其搜索算法的研究

机器博弈是人工智能一个传统的研究领域。从机器博弈的基本理论出发,介绍了机器博弈理论和机器博弈系统的一般构成,重点阐述了现今已存在的各种机器博弈搜索算法及其优缺点。

基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现

针对五子棋棋型定义不准确、棋型不充足等问题,提出了一套改进的五子棋棋型模型和估值方法.针对利用极小极大值搜索和Alpha Beta剪枝算法对此棋型模型着棋时存在效率低和博弈水平不高的问题,提出了一系列改进的着棋方法,即利用局部搜索、多线程技术、浅层最优算法优化剪枝算法,以提升着棋的速度和准确率.实验结果表明,提出的着棋方案能提升着棋效率和准确性,设计得出的五子棋博弈系统具备远超过多数人类玩家的棋力.

机器博弈中搜索算法的研究

机器博弈是人工智能领域中一个重要的组成部分,计算机智能和人类棋手之间展开了长达几十年的竞赛。本文首先简要介绍机器博弈的基本理论和机器博弈系统的一般构成,然后对几种经典的机器博弈搜索算法及其特点的进行了讨论说明。

基于立方剪枝的短语机器解码算法改进

柱搜索算法是短语统计机器翻译广泛使用的解码算法.文中在立方剪枝算法的基础上提出了另一种对柱搜索算法的改进算法-基于立方剪枝的逆向递归算法.柱搜索算法对栈中所有的假进行扩展,立方剪枝算法有选择地扩展栈中的前k个最好假设,而基于立方剪枝的逆向递归算法只扩展栈中评分高的假设.实验结果表明获得相同的翻译质量,立方剪枝算法比柱搜索算法快10倍,立方剪枝的改进算法在大规模语料中比立方剪枝算法更节省时间.

博弈树搜索的算法改进

在计算机博弈程序中,通常采用是α-β剪枝算法,为了进一步提高搜索速度,先后又出现了一些改进的算法。本文综合介绍了这些搜索算法的基本思想,并用伪语言对其算法进行了描述。

基于Alpha-Beta算法的苏拉卡尔塔棋博弈系统研究

针对苏拉卡尔塔棋中,可下位置的生成较为繁琐和复杂,进而导致搜索效率较低的问题,本文采用了优化过的可下位置生成算法,使用“三手进攻”策略与Alpha-Beta算法相结合,同时结合了置换表和哈希表技术,大大地提高了搜索效率和深度。该程序在2021年全国大学生计算机博弈大赛上获得了全国亚军的好成绩,验证了该算法的可行性。

一种扩展条件函数依赖的发现算法

扩展条件函数依赖(extended conditional functional dependency,eCFD)是一种描述数据一致性的语义规则,是条件函数依赖(conditional functional dependency,CFD)的扩展.相比于CFD,eCFD能够描述更多的模式从而表达更丰富的语义信息.然而,关注eCFD的研究工作并不多.从给定数据中发现eCFD规则是一个重要问题,据笔者所知,目前还没有这方面的工作.该问题的难点在于,给定数据中所有合法的eCFD规则之间存在不一致的情况,且包含大量冗余,而CFD和传统的函数依赖规则并没有这样的问题.为避免不一致,同时尽可能地消除冗余,定义了"强合法eCFD"和"近似无冗余eCFD".基于这些概念给出了eCFD发现问题的形式化定义,并给出了MeCFD算法.利用划分属性的方法,MeCFD首先生成所有的基本eCFD,然后,通过合并基本eCFD来构造"组合eCFD".使用先深序来搜索候选空间,使得MeCFD仅用常数的存储空间来维护数据划分,节省了大量的空间开销,有效的剪枝策略被用来改进MeCFD的性能.真实数据集上的实验结果显示出MeCFD良好的可扩展性以及剪枝策略和优化方法的有效性.

藏族久棋的一种两阶段计算机博弈算法

为了进一步提升布局的质量以提升藏族久棋博弈智能体程序棋力,提出了藏族久棋的一种两阶段计算机博弈算法,为藏族久棋的布局阶段设计了基于卷积神经网络和蒙特卡洛树搜索的自对弈算法,通过卷积神经网络指导蒙特卡洛树进行搜索,训练出最优模型并生成质量更高的着法;为战斗阶段设计了基于领域知识的Alpha-Beta剪枝算法。通过设计分阶段算法的方式将深度强化学习与领域知识相结合,试图解决藏族久棋博弈算法研究棋谱数据匮乏、博弈智能体的棋力水平较低等问题。实验结果表明:基于两阶段算法的博弈智能体程序与全局使用Alpha-Beta剪枝算法的博弈程序、人类一段棋手进行对弈,分别取得了65%、60%的胜率。基于两阶段算法的博弈智能体程序在一定程度上具备了“学习”和“思考”的能力,棋力得到了提升。

UIO序列的启发式算法

UIO序列是对有限状态机进行功能测试的有效手段 ,在 VLSI设计、通信协议等时序系统中有很强的实际应用背景。文章基于可区分状态组这一概念设计了一个搜索算法 ,进一步利用搜索信息建立了一个基于“小于”关系的启发策略 ,有效的剪枝策略的设计将尽可能消除没有意义的搜索分枝 ,新设计出的多路 OPEN/CLOSED表存储机制也加快了相关的判别和处理过程。这些措施改进了搜索过程 ,减少了搜索信息的产生 ,提高了搜索速度。该算法与以往的算法相比 ,在时间和空间两方面都得到了很大改进。

机器博弈搜索技术分析

计算机博弈是人工智能领域最具挑战性的研究方向之一,机器博弈的核心思想实际上就是博弈树节点的估值过程和对博弈树搜索过程的结合。分析了现今主流的几种机器博弈搜索算法及其优缺点。