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

针对传统串行混合PVS(Principal Variation Search，主要变例搜索)算法的计算量大、执行耗时长和无法利用多核资源的不足，提出了一种基于OpenMP(Open Multi-Processing)的并行混合PVS算法，该算法应用了PVSplitting(主要变例分裂)策略，自底向上将博弈树每一层的首个PV结点的每个分支的搜索线程化，利用多核CPU并行执行，并对临界区和线程调度进行了合理设计，以提高搜索效率。最后，基于一个真实的中国象棋博弈系统进行了实验，结果表明该算法拥有较高的剪枝率和加速比，能够明显提升混合PVS算法的执行性能。

A parallel hybrid PVS algorithm based on OpenMP

The traditional hybrid PVS (Principal Variation Search) 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 (Open Multi-Processing). This algorithm used the PVSplitting strategy, and the search for the branchs of every level''s first PV node on game-tree are threading 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, and the results show that this algorithm has high pruning efficiency and speedup ratio, and can improve remarkably the performance of hybrid PVS algorithm.