一篇实用的博弈树并行搜索算法论文

所需积分/C币:12 2018-10-17 01:07:40 1.15MB PDF
16
收藏 收藏
举报

一篇实用的博弈树并行搜索算法论文,以中国象棋AI为例描述了基于OpenMP平台和NegaScout(PVS)算法的博弈树并行搜索算法,并以中国象棋为例做了实验。
58· 计算机应用研究 第33卷 是一种基于博弈树子树分割的并行策略,某个处理器从待搜索算法(即图3中三角形所表示的分支调用的算法)PVS_P 的节点开始,从最左侧展开每一层的首个PⅤ节点,直到最大算法除了最左侧的分支调用自身单独递归处理之外,其他的 搜索深度第D层的最左边的节点被展开,将估值传回第D-1节点展开后,在循环内对每个节点以串行形式调用递归算法 层的父节点,冉和其他处理器一起对剩佘节点并行搜索,每个PVS_S进行搜索,线程发生递归时,仅由该线程自己处理,不 子树的搜索交给一个处理器处理。将搜索到的估值再传回给再启动子线程 第D-2层的父节点,所有的处理器再对剩余的节点进行并行2.4数据分解与临界区的设计 搜索,将搜索到的佔值再传回给第D-3层的父节点……反复 节点对象、着法列表p、搜索深度 depth、返回的估值 value 如此,直到传回最终的估值。可见,博弈树每一层最左侧的节等应为每个并行线程复制一份私有副本,并继承进入循环前相 点越“好”, PVSplitting策略的效率越高。 基于 OpenMP并行编程模型与 PVSplilling并行策略的以 应对象的值。搜索到的“好”的着法 Good Move、最大搜索深度 上特点,本文提出了混合PⅤS算法的一种并行设计及实现方 下的最佳着法 Bestmove及其估值best、窗口下界值α应设置为 共亨对象。如果某个线程找到了更好的节点,更新a值,缩小 法。以下将对该并行混合PS算法中的核心部分,包括任务 分解、算法描述形式、数据分解与临界区的设计以及线程调度窗∏范围,使其他线程可能引发更多剪枝。共享对象的更新操 的设计四个方面进行详细介绍。 作,需要对其关键代码段或锁机制进行俫护。前述二值变量 Endloo和剪枝分支的估值va也应设置为共享对象,但任 2.2任务分解 线程发生剪枝更新了上ndLo∞p后,上 slOop值就不会再发生变 混合PVS算法中,搜各分支对应的循坏占据了绝大部化,故不需要对其进行保护。 分计算量,需要进行循环并行化。因各种优化措施能使博弈树 设置个历史得分表数组、个系手着法表数组和个置 节点排列倾向良序,接近极小树,根据这个特点,本文采用换表数组,每个CPU核拥有各自的一个历史得分表、杀于着法 PⅤ Splitting并行策略。 OpenMP下这种并行PNS算法的执行过表和置换表。线程搜索到更好的着法时,只更新对应CP核 程如图3所小。 的历史得分表、杀手着法表和置换表,但是可以对全部的置换 表、历史得分表和杀手着法表进行查询操作。例如,要在置换 表屮登找某个局面对应的佔值信息时,查找置换表数组中所有 的置换表,若任意一个置换表合中,则查找成功;若所有的置换 表都没有命中,则查找失败,如果多个置换表都命中,则选择搜 P 索层次最深的项值。着法的历史得分是历史得分表数组中该 着法的得分的累加。每个CPU核在某一深度下,仅设置一个 图3基于 SpLitting的并行PVS算法示意图 杀手着法,节点排序时,选择两个历史得分最高的杀手着法优 图3中,最大搜索深度为4,并行线程数为3,主线程P1从先搜索。这样避免了对这些对象的与操作进行加锁解锁 根节点PV沿着最左边的分支一直搜索到第4层的第一个叶操作。 子节点P4,将PV4的估值传回给第3层最左边的节点PⅤ3, 线程只在更新最佳着法及其估值和α值时才使用锁操 再创建出派生线程P2和P3,与主线程P一起,对PV3的其他作,这些操作瞬间即可完成,因为使用了节点排序技术,只有少 孩子节点并行搜索,V3获得估值,这个估值传回给第2层最数分支会更新这些共享变量,锁操作带来的影响非常小 左边的节点PV2,个线程对PⅤ2剩下的孩子节点并行搜索,2.5线程调度设计 PⅤ2的估值传给PV1,三个线程一起对PV1剩下的孩子节点并 传统的 SPLitting并行策咯会出现某些处理器对P节 行搜索,PV1获得了佔值。对于不在最左边的分支中的节点,点的搜索还在进行,但其他处理器已完成对非P节点的搜索 每个线程首先以进行空窗探测,空窗探測失败后再以较大窗口空闲下来等待的情况,出现∫额外的同步开销。在进行线程调 进行重新搜素。 度设计时可针对上述不是进行改进。 展开根节点下的个孩子节点时,可对第一个孩子节点 因引入了启发式搜索,故排序越靠前的节点应越优先搜 po单独进行递归处理,对剩余节点P1P2…、Pn-1的并行搜索索。对某层而言,应为每个线程分配 个尚未搜索的节 可以在循环内处理。为了将循环收为满足0enMP要求的单点保持并行执行的顺序与串行相同。在循环内,每个CPU核 人口单出口语句,引入一值变量 EndLoop表示循环内是否发静态分配1次迭代,这样一日某个线程空窗探测失败后以较大 生了剪枝,若某线程发生了剪枝,则改变Enoo值,并用窗口进行搜索时,相应的CPU核分配到的后续线程就少。这 变量val记录对应的估值,其他线程搜索前检测 EndLoop的样虽然增加了线程分配的开销,但最有利于负载平衡。因为 值。若已发生剪枝,则执行 conTinue语句,线程结束,否则执Pv节点和非PV节点搜索的时间差距相对较大,负我平衡的 行搜索。 收益远大于线程分配的开销。在中国象棋中,每个节点下的分 2.3算法形式的修改 支不超过50个,线程分配的开销卡常小 为避免算法递归时发生嵌套并行,导致线程数量迅速激 为进一步减少额外的同步开销,可以将PVS_S算法循环 増的问题,这里将混合PⅤS算法在形式上作一些变化,将算内的每一个分支的搜索定义为一个任务(ask)。这样一旦有 法分解成两个与混合PVS算法类似的算法PVsP和PVS CPU核完成∫某一节点下分配给它的全部擭索线程,就可以 PVS_P算法调用μVS_S算法。ⅣV5_P算法是优化后的并行参与其他木完成搜索的CPU核对应的搜索分支,选择一个任 算法的入口,PⅤSS算法是递归形式的串行执行的混合PVS务执行,减少同步开销。 第1期 邹竞,等:一种基于 OpenMP的并行泯合PVS算法 表1并行线程数对平均估值节点数和置换表平均命中数的影响 3实验 搜索深度 2线程并行混合PVS算4线程并行混合PVS 3.1实验设计 串行混合PVS算法每 走一步的平均估值节点 法每走一步的平均佔值算法每走一护的平均 为验证本文设计的并行混合PVS算法的有效性,开发了 数和置换表平均命中数 节点数和置换表平均命估值节点数和置换表 中数 平均命中数 个具实环境下的中国象棋博弈系统來进行实验分析。该系44286/756 5964/771 6568/851 统使用Ⅶ rosoft Visual C++2012结合 Intel Parallel studio530132/486 33794/586l 381257088 2013开发,使用支持 OpenMP3.0的dC++编译器编译。7 140282/11973 432518/59027 559485/58481 92504/82706 棋盘表示采用文献[11]屮的双向映射数据结构.即256个元8214391419532426095802/245813 3310346/282374 素的一维棋盘数组和48个元素的棋子数组。估值函数使用文 1382073/1041057 13053639/1296356161346271379035 献[12]中的估值策略。测试所用的硬件环境采用 Intel Core 结合以上实验结果可知,在并行线程数不超过CPU核数 i7-2670M(主频2.2GH,4核)的徵处理器,4GDR3内的前提下,随着并行线程效的增加,平均每个线程佔值节点数 存,操作系统使用64位 Windows7中文旗舰版。 降低了,而置换表的全局命中数也比牛行模式下有了较大幅度 3.2实验分析 的提高。随着搜索深度的增加,并行模式的优势越来越明显, 从第7层开始,在2线程并行模式下的加速比维持在1.6以 加速比和并行效率是衡量并行算法效率的两个重要指上,在4线程并行模式下的加速比也维持在2.1以上。到了第 标。设博华树的搜索深度为k时,算法在串行时耗时为8层和第9层,2线程并行模式和4线程并行模式下的加速比 72(1),而p个线程的并行耗时为7(P),使用加速比S(P)来分别达到了17和2.7以上。各项实验结果显示,并行化后混 1"(1) 衡量算法执行时间改进程度,则有S(P)=了〈°∝厶合PⅤVS算法的性能提升非常明显。同时,在4线程并行环境 (p)用来衡量搜索深度为k时,线程使用CPU核的利用率,则下,并行混合PⅤS算法并行效率的绝对数值不高,这是因为获 得了某节点下最左侧分支的估值后,并行线程对后续分支的搜 有E(p)=32)7:(1) Dp·TA(p) 索,初始均以同一窗冂进行搜索,而在串行模式下,同一节点下 中国象棋最复杂的是开局阶段的搜索根据文献[14,选的子树,因先搜索的线程可史新窗口边界,使后搜索的子树的 取10个有代表性的开局着法,分别测试串行2线程并行4线窗口范围变窄。 程并行模式下算法母走一步的平均耗时(亳秒),并计算2线 实验屮也发现,4线程并行模式在少数情况下走出了与串 行馍式下不同的好棋。说明当出现多个最佳节点时,并行模式 程并行4线程并行下的平均加速比S4(P)和平均效率Ek(p), 搜索深度从4层到9层。图4给出了开局阶段随着搜索深度下会出现排在较后的最住节点先完成搜索的情况,使得算法能 的递增,串行、2线程并行和4线程并行下算法每走一步的平够走出“冷招”,这是串行模式做不到的 均耗时。图5和6分别给出了算法的加速比和并行效率在不4结束语 同搜索深度下的变化情况。 不文针对计算机博弈中常用的混合PVS算法的不足,提 单线程串行 2线程串行 出基于 PVSplilling并行策略、使用 OpenMP标准对混合PVS算 ◆·2线程串行 4线程串行 ▲-4线程串行 法进行并行化改进。实验结果表明,该混合PVS算法具有较 高的剪枝效率,并行化后能有效利用多核CPU的处理能力,获 得较大的性能提升,还有可能走出“冷招”。随着多核CPU的 普及,该并行算法将具有较大的应用价值 05 该算法的不足主要表现在:a) OpenMP模型不够灵活,算 44.555.566.577.588.59 44.555.566.577.588.59 搜索深度 搜索深度 法的加速比和效率提升空问有限;b)每个CPL拥有独立的置 图4搜索时间比较图 图5加速比比较图 换表、着法历史得分表和杀手着法表,置换表所占的内存空间 较大。如何解决这些冋题是今后工作的重点。 0.9今·2线程串行 参考文献: -4线程串行 0.7 [1 Rutko D. Fuzzified tree search in real domain games [C//Proc of International Conference on Advances in Artificial Intelligence be 0 0.4 lin: Springer, 2011: 149-161 [2 Reinefld A. An improvement of the scout tree-search algorithm [J] Journal of the International Computer Chess Association, 1983 0.1- 6(4):4-14 44.555566.577588.59 搜索深度 [3 Strnad D, Guid N. Parallel alpha-beta algorithm on the GPU[C]// 图6并行效率比较图 Proc of the 33 rd International Conference on Information Technology Interfaces, Washington DC: IEEE Computer Society, 2011: 571 搜索深度从4层到9层时,串行、2线程并行4线程并行 57 模式下的混合PvS算法每走一步的平均估值节点数和置换表「41许南山,丛磊,孙风平.并行实现有自学习能力的五子祺AIJ1 平均命中数其结果如表1所示。 计算机工程与应用,2006,30(42):45-47 (下转笃91页) 第1期 尤国华,等:基于缓存层级结构的多核Web服务器动忞请求调度算法 (上接第59页) Games. Washington DC: IEEE Computer Society, 2012: 63-70 [5 The OpenMP API specification for parallel programming [OB/EL]. [10] Kunihito H, Masakazu M. Efficiency of three forward-pruning tech- 2013-10-01. hIlp: //openmp ory/mp-roeIImenIs/Open MP-4.0 niques in shogi: futility pruning, Iiull-move pruning, and late move reduction( LMR)[.]. Journal of the Entertainment Computing 「6]王蕾,崔慈敏,冻莉,等,任务疒行编程模型硏究与进展「.欹 2012,3(3):51-57 件学报,2013,24(1):77-90 [11] Liu Yanli, Zhang Heng, Fu Ping. A hybrid game-tree search algo- L7」张明亮,吴俊,李凡长,极小树叶节,点数定理的补充证明及有关 rithm for playing chess [J]. Journal of Computational Information 分祈[打].模式识別与人工智能,2011,12(4):521-526 Systems,212,8(14):5803-5811 [8] Ly Huizhan, Xiao Chenjun, Li Hongye,etal. Hash table in chinese[12]王骄,孙英龙,吕辉展,等.中国彖祺中亚洲棋规循环问题的解 chess [c]// Proc of the 24th Chinese Control and Decision Confer- 决[J].东北大学学报:自然科学版,2012,33(4):476-481 ence. Washington dc: IEEE Computer Society,2012:3286-3291.13」陈国良,孙广中,徐云,等.并行算法研究方法学LJ」.计算机学 [91 Papadopoulos A, Toumpas K, Chrysopoulos A, ct al. Exploring opt 报,2008,31(9):1493-1502 mization strategies in board game abalone for alpha- beta search[14]黄少龙,象棋实用开局技巧[M].北京:人民体育岀版妵,2005 [C// Proe of IEFF Conference on Cormpulalional Intelligenee and 75-125

...展开详情
试读 5P 一篇实用的博弈树并行搜索算法论文
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
一篇实用的博弈树并行搜索算法论文 12积分/C币 立即下载
1/5
一篇实用的博弈树并行搜索算法论文第1页

试读结束, 可继续读1页

12积分/C币 立即下载 >