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

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

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

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

UCT算法在计算机围棋中的应用与改进

计算机围棋博弈是人工智能研究的重要方向,其庞大的空间复杂度给研究者带来了巨大挑战。传统的基于模式识别和博弈树搜索的专家系统方法很难有进一步的提升,UCT算法的出现带来了现代计算机围棋时代。本文将UCT算法应用到九路计算机围棋博弈系统中,由于UCT算法模拟过程适合并行化处理,故本文通过多核并行计算对UCT算法进行改进,通过与单核算法程序进行实际对弈,证明了并行优化的可行性。

UCT算法在不围棋博弈中的实现

计算机博弈是人工智能领域的挑战性课题,它利用计算机进行分析、判断和推理,从而得到理性的决策.不围棋是近年来计算机博弈竞赛的一个棋种,属于围棋的变体,其规则是先吃子或棋子自杀的一方为负.通过分析不围棋博弈模型的特点,提出了对上限信心界树搜索(UCT)算法的一个优化方法,在算法的启动过程优先选择评分较高的盘面进行模拟博弈,以便得到更好的落子选择.在与著名的OASE-NoGo软件的试验对弈中,以该算法为核心设计的不围棋软件取得了90%以上的胜率,证明是可行、有效的.

局部UCT算法在围棋死活题上的性能测试

为了探索UCT算法在局部搜索中的可靠性,文中在改写Fuego的全局UCT搜索算法的基础上,实现了封闭域局部UCT搜索算法,并在64个标准的围棋死活题上进行了测试。初步结果表明,虽然有一小部分死活问题(11个,约17%)还不能正确求解,但封闭域局部UCT算法基本能够较快地(十几秒内)求解出大部分围棋死活测试问题。文中测试对如何改进大棋盘上的UCT算法性能有指导意义。

基于点格棋的UCT算法研究与分析

以博弈树搜索为核心的α-β剪枝算法,受限于估值函数对设计者棋力水平的依赖,难以实现更进一步的提升。论文提出的UCT(Upper Confidence Bound Apply to Tree)算法结合了UCB公式和蒙特卡洛树搜索算法,弱化了算法本身对估值函数的依赖性,最大化利用计算机的算力优势,提升算法的整体效率,并利用其并行化优势优化算法,基于点格棋进行了算法的实现。

面向搜索时间受限的完全信息博弈UCT算法改进研究

针对完全信息博弈中搜索时间受限的算法设计问题,在考虑博弈模型不同特点及对结局影响程度的基础上,提出了分阶段的算法模型,给出了三阶段博弈算法设计方法。通过改造影响搜索策略的目标函数,使得在时间受限的前提下,能够方便控制每一阶段均更有效地搜索出较好策略,并给出相应的算法实现与分析。以点格棋为对象,给出了通过改造UCT算法中UCB公式的实现思路,设计了方向引导控制策略、多种算法混合、二进制压缩和并行化处理等技巧,有效提升了算法的效率和稳定性,并通过试验验证了所给出方法的有效性和效率。

UCT算法在“宽带+”营销案设计中的应用研究

通信运营商现行推广的业务种类多样,需要通过合理的设计才能将家庭宽带业务与其他业务做科学且有竞争力的套餐式营销。文章研究将UCT(Upper Confidence Bound applied to Trees)算法应用于'宽带+'营销案设计中,可以提高数据分析精准度和效率,为宽带营销案设计提出合理化建议。

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

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

基于UCT搜索算法的点格棋博弈系统研究

蒙特卡罗树搜索(MCTS)在许多完备的信息双人游戏中获得成功。本文给出了UCT(Upper Confidence Bound Apply to Tree)算法结合了UCB公式和蒙特卡洛树搜索算法,同时与局面评估相结合,根据点格棋长链和环的特点对算法进行了优化。有利于更快更准地找到当前局面的最优解。

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

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

基于蒙特卡洛树搜索的土石方动态调配算法及验证

针对堆石坝填筑进度控制以及土石方动态调运问题,受AlphaGo-Zero的启发,本文提出了一个基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的土石方智能动态调配模型。该模型以当前累计填筑工程量、紧邻前一月份完成工程量以及当前月份为状态,用各月填筑工作面对应的填筑可达强度约束动作空间,综合考虑节点工期、总工期、坝面施工机械费用和土石方调运费用等因素构造奖励函数。此外,结合本文研究问题的特点,对MCTS迭代中的上限置信区间算法(upper confidence bound apply to tree,UCT)进行了改进和比较分析,最后以一个工程实例对本文提出模型的有效性进行了验证分析。结果表明,与施工仿真相比,以MCTS为框架的土石方动态调配模型的计算分析时间大大减少,为土石方动态调配问题提供了新的模型与手段。

结合神经网络的改进UCT在国际跳棋中的应用

针对UCT算法的准确性受搜索次数影响较大的问题,提出一种结合神经网络的改进UCT算法。利用神经网络输出每一步的平均行动价值Q,结合改进的UCT算法寻找搜索过程中的高潜力节点。将传统UCT搜索改进为3个阶段:首先,通过已训练好的神经网络模型和UCT算法对当前所有子节点进行初次搜索,获得高潜力子节点;其次,利用剪枝操作去掉部分子节点,提升被搜索节点的质量;最后,二次搜索保留的高潜力子节点获得最优策略。另外,在分次搜索的过程中引入节点保留数量因子R和搜索比例因子P,辅助分次搜索,增加搜索的有效性。将其引入国际跳棋游戏中,实验结果表明:改进后的算法与其他算法相比胜率有所提升,验证了该算法的可行性。

蜜罐博弈中信念驱动的攻防策略优化机制

作为一种典型的欺骗防御手段,蜜罐技术在主动诱捕攻击者方面具有重要意义。然而现有设计方法主要通过博弈模型来优化蜜罐的诱捕决策,忽略了攻击者的信念对双方博弈决策的影响,存在自适应优化决策能力弱、易被攻击者识破并利用等不足。为此,提出了基于信念的蜜罐博弈机制(Belief Based Honeypot Game Mechanism, BHGM)。BHGM基于攻击者完成任务的多轮博弈过程,重点关注蜜罐采取动作对攻击者信念的影响以及信念对攻击者是否继续攻击的影响。同时,基于树上限置信区间(Upper Confidence Bound Apply to Tree, UCT)设计了信念驱动的攻防最优策略求解算法。仿真实验结果表明,信念驱动的攻击方策略能基于当前信念选择继续攻击或及时止损以获得最大收益,而信念驱动的蜜罐策略在考虑风险的情况下能尽量降低攻击方怀疑,以诱骗其继续攻击,从而获得更大收益。