一种基于 OpenMP 的并行混合 PVS 算法

摘要

针对传统串行混合 PVS（principal variation search，主要变例搜索）算法的计算量大、执行耗时长和无法利用多核资源的不足，提出了一种基于 OpenMP（open multi-processing）的并行混合 PVS 算法。该算法应用了PVSplitting（主要变例分裂）策略，自底向上将博弈树每一层的首个 PV 节点的每个分支的搜索线程化，利用多核CPU 并行执行，并对临界区和线程调度进行了合理设计，以提高搜索效率。最后，基于一个真实的中国象棋博弈系统进行了实验，结果表明，该算法拥有较高的剪枝率和加速比，能够明显提升混合 PVS 算法的执行性能。%The traditional hybrid PVS algorithm fails in large amount of calculation and long execution time,and cannot take advantage of the multi-cores resources.This paper proposed a parallel hybrid PVS algorithm based on OpenMP.This algorithm used the PVSplitting strategy,and threaded the search for the branchs of every level’s first PV node on game-tree from bottom to up,executed by parallel processing on multi-cores CPU.It also presented the rational designed of critical section and thread scheduling for improving the search efficiency.Finally,this paper conducted experiments on the basis of a real Chinese chess computer game system.The results show that this algorithm has high pruning efficiency and speedup ratio,and can improve re-markably the performance of hybrid PVS algorithm.