在Alpha-Beta算法的并行化的过程中,一个较为困难的问题是判断从哪里开始并行搜索,因为一个分支的搜索可能会发现并行进行的另一个搜索完全可以避免.正因为如此,Alpha-Beta算法是一个很难并行的算法.
虽然仿真可能预计出设计的Alpha-Beta并行算法具有非常好的性能,但是很多仿真都是基于一些不现实的假设的基础上.在实际的实现中,以下的因素经常会导致Alpha-Beta并行算法的并行效率低下[11]:
1. 同步开销（Synchronization Overhead）.如果算法中存在过多的同步点(synchronization point）,那么处理器很多时候会处于空闲（idle）状态.
2. 通信开销（Communication Overhead）.进程（process）之间需要互通信息,通信开销的影响程度取决于通信频率和通信延时（communication latency）.
3. 搜索开销（Search Overhead）.一个处理器完成的工作也许对另外一个处理器的搜索有利,如果这些信息不能很好地共享,会增加很多不必要的搜索.
这些开销并不相互独立,例如,增加通信会导致通信开销的增加,但是有可能减少搜索开销,再如,减少同步点能减少同步开销,但是可能会增加搜索开销.
在对Alpha-Beta算法进行并行化的时候,不仅要尽量利用算法的并行性,又要尽量减少上述的几种开销.基于不同的基本思想,很多的并行Alpha-Beta算法被先后提出来.对这些算法可以按照各种不同的标准进行分类和分析,例如[12]:
1. 按照处理器体系结构（processor hierarchy）分类.按照处理器树（processor tree）的可变性（rigidity）分为静态（static）和动态（dynamic）,静态处理器树:一个或者多个处理器作为主处理器（master）,其他处理器作为从处理器（salve）.主处理器控制从处理器,这个结构在博弈树的搜索过程中都是固定的.动态处理器树则随着处理器的空闲和忙碌情况的变化而变化.
2. 按照控制分布（control distribution）分类.如果算法的进行由少部分主处理器控制,则称它为集中式的（centralized）,如果算法的进行是由所有处理器控制,则称它为分布式（distributed）的.
3. 按照可发生并行的结点类型分类.在[4]的中将结点分成三类:type1,type 2,type 3.在次基础上,将type 2的结点分成两种:当在搜索完一个type 2的结点的子树之后,如果没有办法将它被剪枝,那么就将它称为bad type 2结点,否则称为good type 2结点.经过这样的分类,就可以列出一个算法可能并行搜索的结点.
4. 按照同步结点的种类分类.一些算法在搜索一个结点时,需要等待该结点的前几个子结点返回估值后才能并行搜索其他的子结点,这使得算法的并行性受到约束.按照上述结点分类,可以列出算法需要进行这种同步的结点的种类.
按照上述各种标准,可以对各算法进行定性的分析,但是如果脱离了算法的具体实现来对比算法性能,难以得到可靠的分析结果.这些具体实现中,一些需要考虑重要的因素包括:
1. 底层硬件（underlying hardware）.算法的具体实现可能使用各种不同的底层硬件,一些实现中甚至使用软件实现的硬件仿真器来验证算法.
2. 博弈树的种类.常见的博弈树有国际象棋树（chess tree）,黑白棋树（Othello tree）,西洋跳棋树（checkerstree）,和人工树.若博弈树不是由游戏的博弈程序产生的,则称这个博弈树为人工树（artifcialtrees）.
3. 并行算法基于何种串行算法.很多串行算法进在Alpha-Beta算法的基础上进行了改进,并行算法基于的串行算法对最后的性能也有影响.
4. 转移表的实现方法.转移表中的信息共享效率对于并行算法的性能有着非常关键的影响.转移表的两种主要实现方法是分布式消息传递（distributedmessage-passing）和共享内存（shared-memory）.共享内存的转移表的实现往往需要特殊的硬件支持,但是一般来说,它比基于消息传递的分布式转移表速度快.也有一些算法中处理器维护本地转移表（localtransposition tables）,而不共享信息.
本文章欢迎转载，请保留原始博客链接http://blog.csdn.net/fsdev/article
--------------------
[4] Knuth, D.E. and Moore, R.W. (1975). An Analysis of Alpha-Beta Pruning.Artificial Intelligence, 6:293–326.
[11] Brockington, M. G. and Schaeffer, J. (1996). APHID Game-Tree Search.Presented at Advances in Computer Chess 8, Maastricht.
[12] Brockington, M.G. (1996). A Taxonomy of Parallel Game-Tree SearchingAlgorithms. ICCA Journal, Vol. 19, No. 3, pp. 162-174.
分享到：
相关推荐
一篇实用的博弈树并行搜索算法论文，以中国象棋AI为例描述了基于OpenMP平台和NegaScout（PVS）算法的博弈树并行搜索算法，并以中国象棋为例做了实验。
在分析现有并行Prim算法的基础上，提出了适于GPU架构的压缩邻接表图表示形式，开发了基于GPU的min-reduction数据并行原语，在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语...
并行计算 陈国良编著 呵呵 大家来下载 是第三版《并行计算:结构•算法•编程(第3版)》是并行计算系列丛书之开篇，它以并行计算为主题，围绕并行计算机、并行算法和并行程序设计展开讨论，强调融并行计算机体系结构、...
在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路（VLSI）设计、代码设计、图象处理和电子工程等科技领域中，存在... 最后，在引入邻域结构概念的基础上，介绍一种通用的近似算法——局部搜索算法。
从1985年到1993年，召开了五届国际遗传算法学术会议,遗 传算法巳经有了很大的发展，并开始渗透到人工智能、神经网络、 机器人和运筹学等领域.遗传算法是多学科相互结合与渗透的产 物，它已发展成一种自组织、自适应...
3.1实验目的与要求 ...5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
主要内容为关于亚马逊棋的蒙特卡洛博弈算法的并行优化综述，对相关内容进行了调研和总结，首先是引言部分，简要介绍亚马逊棋的相关知识，其次介绍应用于亚马逊棋的相关博弈算法，如：极大化极小法(MiniMax)、Negamax...
在之前的五子棋alphabeta--VCF VCT版本的基础上，进行了如下改进，智能得到了增强，还有改进空间 1，减少参数传递。 2，加入了并行计算。 注意:运行时参数栈的大小设大一点，设为200M(-Xss204800k)。
非数值算法 常用非数值并行算法介绍 模拟退火算法新解的产生和接受可分为如下四个步骤： 1、模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火算法源程序 一、模拟退火算法
遗传并行算法-高性能,可以结合自己实际情况,进行修改.
并行算法 并行算法 并行算法 并行算法 并行算法 并行算法
并行图论算法并行图论算法并行图论算法并行图论算法
Bellman Ford算法的并行实现
beta-NTI的计算需要根据观察数据（OTU表和遗传发育树）多次构建零模型，该过程非常耗时，不利于科研人员进行数据的探索。但每个零模型的构建相互独立，可同时进行，R语言并行计算可加快beta-NTI的计算速度。本文内容...
利用k_means聚类算法的MapReduce并行化实现，为学习hadoop的同学提供参考
并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案
所谓并行算法是指一次可执行多个操作的算法。对并行算法的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中，我们将阐述一些简单的并行算法以说明一些基本概念和...
最短路径的并行算法综述--介绍几种最短路并行算法的基本概念。