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

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

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

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

基于PVM的启发式搜索的并行计算模型设计

通过分析人工智能中的A和A^*启发式搜索,提出了通过PVM工具包,设计和实现A和A^*启发式搜索的并行计算模型。在启发搜索过程中同时进行评估函数计算,使计算的速度加快。解决了在搜索解空间庞大,评估函数计算复杂的情况下,使用单计算机计算速度慢的问题。该文实现了基于PVM的启发式搜索过程,该模型可应用于一般性启发式搜索问题的并行计算模型。     

UIO序列生成算法的继续改进

为解决传统的UIO(唯一输入输出)序列方法中使用的UIO搜索树规模过于庞大的问题,分析了UIO树的构造过程,并结合LANG算法提出的一系列的剪枝方法和节点链搜索技术,提出了一种改进的UIO序列算法,使用转换表格连接方法替代传统的构造UIO树的方法,并将节点链搜索技术在算法循环调用,去掉不需要的节点,加快UIO序列生成,降低搜索空间。通过实验结果表明,与现有算法相比,该算法在降低时间复杂度和空间复杂度两方面有较大改进。     

基于Expectimax搜索与Double DQN的非完备信息博弈算法

麻将作为典型的非完备信息博弈游戏主要通过传统Expectimax搜索算法实现,其剪枝策略与估值函数基于人工先验知识设计,存在假设不合理等问题。提出一种结合Expectimax搜索与Double DQN强化学习算法的非完备信息博弈算法。在Expectimax搜索树扩展过程中,采用Double DQN输出的估值设计估值函数并在限定搜索层数内获得分支估值,同时设计剪枝策略对打牌动作进行排序与部分扩展实现搜索树剪枝。在Double DQN模型训练过程中,将麻将信息编码为特征数据输入神经网络获得估值,使用Expectimax搜索算法得到最优动作以改进探索策略。实验结果表明,与Expectimax搜索算法、Double DQN算法等监督学习算法相比,该算法在麻将游戏上胜率与得分更高,具有更优异的博弈性能。     

博弈算法在黑白棋中的应用

计算机博弈是一种对策性游戏,是人工智能的主要研究领域之一,它涉及人工智能中的搜索方法、推理技术和决策规划等。目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。文中通过一个黑白棋程序的设计,将生成的博弈树节点的估值过程和对博弈树搜索过程相结合,采用传统的Alpha-Beta剪枝和极大-极小原则方法给出了博弈程序设计的核心内容:包括博弈树搜索和估值函数两个方面,提出了对原算法的一种改进,该算法提高了搜索速度。实验结果验证了算法的有效性。     

博弈算法在黑白棋中的应用

计算机博弈是一种对策性游戏，是人工智能的主要研究领域之一．它涉及人工智能中的搜索方法、推理技术和决策规划等。目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。文中通过一个黑白棋程序的设计，将生成的博弈树节点的估值过程和对博弈树搜索过程相结合，采用传统的Alpha—Beta剪枝和极大一极小原则方法给出了博弈程序设计的核心内容：包括博弈树搜索和估值函数两个方面，提出了对原算法的一种改进，该算法提高了搜索速度。实验结果验证了算法的有效性。     

基于覆盖树的可扩展邻近搜索方法

针对邻近搜索技术受限于网络协议的支持以及存在空间嵌入误差的问题,提出一种基于覆盖树的可扩展邻近搜索方法CPS,包括覆盖树构建与维护协议和k近邻搜索算法两部分。节点自主计算自身所处层次,构造一棵层次化树。邻居维护协议负责维护覆盖树结构,确保其适应动态的网络环境。k近邻搜索算法通过对覆盖树剪枝,构造各层候选节点集合,提高搜索效率。实验结果表明,CPS的搜索精度优于典型的邻近搜索方法Tiers。     

基于重叠区域的高性能近似kD树算法

kD树是近邻搜索中应用最广泛的算法之一,针对其性能随着空间维度的增加而迅速降低的问题,提出一种可应用到高维空间的kD树搜索算法——okD树.在该okD树的创建过程中,左右子结点之间保留重叠区域,重叠区域不参与后续的划分而是直接传递到子结点;在搜索过程中,对于存在重叠区域的子结点不进行回溯,以提高okD树的搜索效率,不进行回溯的子结点中包含的重叠区域扩大了搜索范围,从而提高了搜索精度.实验结果表明okD树算法的性能优于当前主流的近似kD树算法.     

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索，进行这些查询用到的算法与位置和范围查询的算法不同，需要专门进行研究，介绍了一种分支界限遍历R树算法，并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程，以减少搜索空间中需访问结点的数量，有效地进行k-NN搜索。     

局域网分布式并行计算环境的建立及应用

主要介绍了以PVM系统作为局域网并行计算平台,在工作站机群上,建立了局域网分布式并行计算环境,简单介绍了在此并行环境中开发的多层二维二相油藏数值模拟的并行计算软件,利用工作站机群开发并行油藏模拟软件是为了探索解决大规模油藏模拟的行之有效的方法。     

使用不同的博弈树搜索算法解决计算机围棋的吃子问题

使用Alpha Beta搜索和proof number (pn) 搜索解决计算机围棋的吃子问题.对吃子问题形式化并给出了简单有效的评估函数.Alpha Beta搜索使用了包括置换表在内的各种扩展技术.Pn搜索使用了包括df pn在内的4种变体.研究结果显示,对于解决吃子问题pn搜索优于Alpha Beta搜索.并且搜索过程中所产生的数据的一些模式可以帮助在结果未知的情况下对结果进行预测.所设计的算法可以用于解决单独的吃子问题或者计算机围棋比赛中的吃子计算.     

微机环境下基于PVM的网络并行程序开发方法

并行虚拟机ＰＶＭ是一种通用的网络并行程序开发环境,它可以把连网的巨型机,大规模并行机,工作站以及微机作为一大型并行机使用,供人们开发并行算法或运行并行系统。此文对ＰＶＭ的基本情况和最新进展进行介绍,讨论了基于ＰＶＭ的网络并行程序开发方法,最后给出了具体的实例。     

APHID: Asynchronous Parallel Game-Tree Search

Most parallel game-tree search approaches use synchronous methods, where the work is concentrated within a specific part of the tree or at a given search depth. This article shows that asynchronous game-tree search algorithms can be as efficient as or better than synchronous methods in determining the minimax value.  APHID, a new asynchronous parallel game-tree search algorithm, is presented. APHID is implemented as a freely available portable library, making the algorithm easy to integrate into a sequential game-tree searching program. APHID has been added to four programs written by different authors. APHID yields better speedups than synchronous search methods for an Othello and a checkers program and comparable speedups on two chess programs.     

基于PRAM并行模型最大值查找的方法与改进

随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM （Parallel Random Access Machine）下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本（cost）更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.     

State of the art in parallel search techniques for discreteoptimization problems

Discrete optimization problems arise in a variety of domains, such as VLSI design, transportation, scheduling and management, and design optimization. Very often, these problems are solved using state space search techniques. Due to the high computational requirements and inherent parallel nature of search techniques, there has been a great deal of interest in the development of parallel search methods since the dawn of parallel computing. Significant advances have been made in the use of powerful heuristics and parallel processing to solve large-scale discrete optimization problems. Problem instances that were considered computationally intractable only a few years ago are routinely solved currently on server-class symmetric multiprocessors and small workstation clusters. Parallel game-playing programs are challenging the best human minds at games like chess. In this paper, we describe the state of the art in parallel algorithms used for solving discrete optimization problems. We address heuristic and nonheuristic techniques for searching graphs as well as trees, and speed-up anomalies in parallel search that are caused by the inherent speculative nature of search techniques     

基于深度/单目融合视觉及强化学习的机器人定位棋局与行棋策略

中国象棋对弈机器人系统实现的关键包括棋局识别定位和自主行棋策略.\:首先,针对棋局识别与定位问题,提出一种基于单目相机与深度相机视觉融合的棋局识别定位方法.\:该方法利用立体棋子三维特征获取棋子位置,与二维图像识别结果融合计算定位,以提高棋子的识别定位精度.\:其次,针对行棋策略问题,提出一种基于深度神经网络与蒙特卡洛树搜索的决策方法.\:该方法利用具有终局特征判断的蒙特卡洛树进行搜索,使用优化的随机行棋策略指导模拟行棋,训练具有多尺度及残差结构的策略价值网络模型.\:最后,通过自对弈获取训练数据,通过智能体对抗验证、更新模型参数.\:实验表明,相较于单目视觉识别,所提出方法具有更高的精确度和稳定性,识别率达到97%;相较于基准剪枝搜索算法,所提出方法对弈时最多赢得82%的对局,且所需运算时间缩短41%.     

JPI:基于纯Java语言的异构并行处理支持平台

针对使用Ｐａｒａｌｌｅｌ Ｖｉｒｕａｌ Ｍａｃｈｉｎｅl（ＰＶＭ）和ＭｅｓｓａｇｅＰａｓｓｉｎｇ Ｉｎｔｅｒｆａｃｅ（ＭＰＩ）软件包的解决方案,该软件包用纯Ｊａｖａ语言实现了类似于ＰＶＭ和ＭＰＩ所提供的任务调度、通信和全局归约操作等方面的功能,基于ＪＰＩ的并行程序的运行和性能测试表明,ＪＰＩ不仅解决了并行程序在异构环境中的无缝移植问题,并且能够为包括网络密集型在内的并行程度提供有效的开发、运行支持。