博弈树并行搜索算法

本文分析了博弈树并行搜索算法中的主变量分裂算法的同步开锁问题。     

围棋死活问题的计算机求解

提出了一种基于搜索的围棋死活问题的求解方法,并实现了一个围棋死活问题求解程序SharpSense。对比实验表明,SharpSense的性能明显优于同类程序,对封闭围棋死活问题的解题能力达到了围棋专业棋手的水平。SharpSense还发现了围棋死活问题经典著作《围棋死活大全》中的两个错误。     

双人博弈问题中的蒙特卡洛树搜索算法的改进

蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。 由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显著改进了蒙特卡洛树搜索的准确性和效率。     

面向多智能体博弈的并行蒙特卡洛树搜索算法研究

蒙特卡洛树搜索算法是一种常用的强化学习算法,博弈过程中动态空间的指数级增长是制约该算法学习效率的因素。基于并行方法对蒙特卡洛树搜索算法进行优化,提出基于胜率估值传递的并行蒙特卡洛树搜索算法。改进后的并行博弈搜索策略框架包含一个主进程和多个子进程,其中子进程用于探索,主进程根据子进程传递的胜率估值数据进行决策。结合多智能体博弈平台Pommerman进行实验验证,与传统的蒙特卡罗树搜索算法相比,并行蒙特卡罗树搜索算法有效提高了资源利用率、博弈胜率及决策效率。     

中国象棋计算机博弈关键技术分析

机器博弈被认为是人工智能领域最具挑战性的研究方向之一．国际象棋的计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的“搏杀”，“深蓝”计算机的胜利也给人类留下了难以忘怀的记忆．中国象棋计算机博弈的难度绝不亚于国际象棋，不仅涉足学者太少，而且参考资料不多．在国际象棋成熟技术的基础上，结合在中国象棋机器博弈方面的多年实践，总结出一套过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点，最后提出了当前研究的热点与方向．     

并行计算机博弈系统设计与改进

计算机博弈的核心技术是搜索。本文针对单核条件下的搜索算法、并行条件下的搜索算法两个方面进行了研究。单核搜索算法方面,简单地介绍了博弈单核条件下的选择性搜索思想,本文研究了几种已有的多核条件下博弈并行搜索方法,分析了其优劣,并针对性地提出了改进方案,给出了系统实践的结果,比较了改进方法与原有方法的效果差异。最后,本文探讨了Alpha-Beta并行搜索系统实现中一些特殊的程序设计技巧。     

一种博弈树静态估值算法--△Feature状态估值

在考虑下棋操作对棋盘影响的局部性后,提出了棋博弈的△feature状态估值算法,通过计算博弈树中相邻结点的特征变化来避免在叶结点上扫描整个棋盘,有效地减少了静态估值的时间开销。若棋子影响的局部范围足够小,还可以考虑将局部范围的所有情况列成表,以查表代替棋形匹配。ΔAFeature状态估值算法也可以与其它优化博弈树搜索的方法一同使用,达到更好的效果。     

一种博弈树静态估值算法——ΔFeature状态估值

在考虑下棋操作对棋盘影响的局部性后,提出了棋博弈的Δfeature状态估值算法,通过计算博弈树中相邻结点的特征变化来避免在叶结点上扫描整个棋盘,有效地减少了静态估值的时间开销。若棋子影响的局部范围足够小,还可以考虑将局部范围的所有情况列成表,以查表代替棋形匹配。ΔFeature状态估值算法也可以与其它优化博弈树搜索的方法一同使用,达到更好的效果。     

博弈树启发式搜索的α-β剪枝技术研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,对扩展出的子节点按照估价函数大小顺序插入到搜索树中,从而在α-β剪枝过程中剪掉更多的分枝,提高搜索效率。     

采用时间差分算法的九路围棋机器博弈系统

围棋机器博弈是机器博弈中重要的分支之一,其庞大的博弈空间给机器博弈研究者带来了巨大挑战.目前围棋机器博弈多采用静态估值搜索与蒙特卡洛树搜索,故将时间差分算法引入至九路围棋机器博弈系统中,提出基于时间差分算法的围棋机器博弈系统模型,该博弈系统具有一定的自学习能力,能在不断的对弈中逐步提高博弈能力.通过与采用α-β搜索算法的博弈系统进行实际对弈,证明了该方法的可行性.     

一种基于启发式搜索的论文元数据提取算法

随着大量的科研论文以电子文档的形式出现, 为了高效地检索这些科研文献资料,从中精确地抽取这些论文头部的元数据信息显得十分有必要.在条件随机场模型的基础上,提出了一种启发式搜索算法来对论文头部的元数据信息进行提取.该算法首先利用文本分块技术和特征提取规则来对文本进行预处理,然后结合条件随机场概率模型利用启发式搜索来进行元数据的提取.实验结果表明,在相同概率模型的基础上,该算法有着较好的性能,在精确度和召回率方面都有了明显的提高.     

一个线性的启发式图搜索算法

本文描述了一个能够改善启发函数的启发式图搜索算法．它利用搜索过程中的信息,改动启发函数h,保持搜索树上始终满足单调限制条件,使算法的最坏复杂度从B′的O（N²）（L.Méró,1984）降为O（N）．本文还证明了新算法的可采纳性、线性的复杂度,并同算法B′作了性能比较．     

对称无关的模式编码方法在定式学习中的应用

计算机围棋中的定式可以从棋谱中学习，采用与模式对称性无关的编码方法可以取得更好的储存效果，这是一种基于模式的邻近特征、轮廓特征和行列特征的模式编码方法，与模式的平移、旋转、翻转及黑白对称性无关，实验结果表明其哈希性能良好，模式间的查找迅速，也可以在官子和死活问题中得以应用。     

基于Alpha-Beta搜索算法的中国象棋人机对战的设计与实现

计算机博弈是人工智能研究的一个重要分支,人类在计算机博弈领域的研究取得了大量的研究成果,这些成果在人工智能领域产生了重要影响。中国象棋计算机博弈的研究起步晚于国际象棋,但国际象棋计算机博弈研究的成果为我们提供了很多的借鉴技术。近年来随着研究的不断深入,中国象棋计算机博弈越来越成为继国际象棋后计算机博弈研究的热点之一。     

分布式博弈树搜索算法

本文提出了分布式博弈树搜索ＤＤＳ算法，从通信开销、存储开销、加速比等方面分析了算法性能，并与ＳＳＳ和α－β算法在搜索结点个数方面作了比较，模拟实验表明ＤＤＳ是一种高效实用的分布式搜索算法。     

多因素问题的启发式搜索算法MFRA

本文新定义了一类多因素启妇式搜索问题，提出了适于此类问题求解的启发式搜索算法ＭＦＲＡ。文中研究了算法ＭＦＲＡ的可采纳性质，单调限制性质和比较性质等。基于算法ＩＤＡ的思想，提出了ＭＦＲＡ的改进算法ＭＦＲＡ－ＩＤＡ，这一算法具有线性存储空间这一重要特性。