在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.
分享到:
相关推荐
后端开发是一个涉及广泛技术和工具的领域,这些资源对于构建健壮、可扩展和高效的Web应用程序至关重要。以下是对后端开发资源的简要介绍: 首先,掌握一门或多门编程语言是后端开发的基础。Java、Python和Node.js是其中最受欢迎的几种。Java以其跨平台性和丰富的库而著名,Python则因其简洁的语法和广泛的应用领域而备受欢迎。Node.js则通过其基于JavaScript的单线程异步I/O模型,为Web开发提供了高性能的解决方案。 其次,数据库技术是后端开发中不可或缺的一部分。关系型数据库(如MySQL、PostgreSQL)和非关系型数据库(如MongoDB、Redis)各有其特点和应用场景。关系型数据库适合存储结构化数据,而非关系型数据库则更适合处理大量非结构化数据。 此外,Web开发框架也是后端开发的重要资源。例如,Express是一个基于Node.js的Web应用开发框架,它提供了丰富的API和中间件支持,使得开发人员能够快速地构建Web应用程序。Django则是一个用Python编写的Web应用框架,它采用了MVC的软件设计模式,使得代码结构更加清晰和易于维护。
华为数字化转型实践28个精华问答glkm.pptx
新员工入职培训全流程资料包(100+个文件) 1入职流程指引 万科新职员入职通知书 万科新职员入职引导手册 新进员工跟进管理表 新员工入职报到工作单(文职) 新员工入职报到流程 新员工入职流程表 新员工入职手续办理流程(工厂 新员工入职手续清单 新员工入职须知 新员工入职训流程 新员工入职引导表(导师用) 2 入职工具表格 3 培训方案计划 4培训管理流程 5培训教材课件 6 培训效果检测 7 员工管理制度 8 劳动合同协议 9 新员工培训PPT模板(28套)
FX5U PLC作为主、从站的通讯方式程序实例,以及包含详细说明文件...
技术需求报告-集行波测距与故障录波功能于一体的电网综合故障分析系统.docx
最新二开版本源码博客论坛源码,UI很漂亮,可切换皮肤界面.rar最新二开版本源码博客论坛源码,UI很漂亮,可切换皮肤界面.rar
2024-2030全球及中国广谱防晒霜行业研究及十五五规划分析报告
基于Qt Creator实现中国象棋人机对战, c++实现.zip
华为用“三阶段十二步”法保证业务战略引领数字化转型glkx.pptx
基于matlab实现自适应稳健波束形成对角加载算法,其与输入信噪比的关系.rar
热塑性弹性体,全球前21强生产商排名及市场份额
详见:https://blog.csdn.net/Timi2019/article/details/138357258 【项目技术】 python+Django+mysql 【实现功能】 网站前台: (1)用户可以在不登录的情况下访问本系统,但是不能进行数据的分析,也不能对自己的个人信息进行修改。 (2)用户的注册与登录:游客想要在一个网站对自己的信息进行修改的话,需要经过一系列的有验证信息的注册,成为网站的正式用户后,可以编辑或修改自己的个人信息。 (3)评论分析:用户可以在网站内对所有的评论进行查看和分析。 (4)个人信息:通过个人信息查看功能可以查看自己的个人信息,还可以对密码进行修改。 (5)系统简介:用户可以在网站的首页上查看系统的信息,如用户数量、新闻数量、评价数量等信息。 网站后台: (6)用户信息管理:管理员可以查看和维护网站内所有的用户信息,可以通过用户的编号或者用户名进行查找,查找到具体的用户后可以对用户的信息进行修改,也可以直接删除用户的信息。 (7)新闻管理模块:后台管理员可以对网站内的新闻信息进行管理
某知名大型集团信息化项目建设方案qy.pptx
基于matlab实现潮流计算程序,MATLAB潮流计算程序.rar
搭建数据分析和机器学习平台,实现如下功能:设计一个网页版的用户界面,支持从本地选取数据集、自动可视化分析、查看训练记录、查看训练模型参数和绘图和支持完成机器学习任务。核心工具:streamlit和pycaret,部署和运行方便,只需streamlit run main.py命令即可。
一种统一的单隐层的前馈网络(SLFNs)的在线序列学习算法。该算法被称为在线序极端学习机器(OS-ELM),可以学习固定或不同块大小的逐块或逐块数据)。OS-ELM中加性节点的激活函数可以是任意有界的不变分段连续函数,RBF节点的激活函数可以是任意可积的分段连续函数。在OS-ELM中,随机选择隐藏节点的参数(加性节点的输入权值和偏差或RBF节点的中心和影响因子),并根据顺序到达的数据解析确定输出权值。该算法采用了Huang等人开发的批处理学习的思想,该思想已被证明比其他批处理训练方法非常快。除了选择隐藏节点的数量外,还不需要手动选择其他控制参数。
仿我图网素材购买素材下载素材交易平台网站源码.rar仿我图网素材购买素材下载素材交易平台网站源码.rar
python tkinter
2024-2030全球与中国伊维菌素片剂市场现状及未来发展趋势
Python数据分析大作业(ARIMA 自回归积分滑动平均模型) 4000+字 图文分析文档 销售价格&库存分析+完整python代码