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

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