基于OpenMP的并行混合PVS算法及其应用

发布时间：2018-08-26 08:16

【摘要】：计算机博弈是人工智能中一个非常具有挑战性的研究方向，对各种博弈树搜索算法和优化措施的研究和组合，又是计算机博弈中研究的重点。国际象棋计算机博弈已经获得了巨大的成就，早已具备击败人类冠军的智能。中国象棋计算机博弈的研究起步较晚，难度更大，挑战性更强，吸引了越来越多的研究者对其进行研究，也取得了不俗的成就。 OpenMP是一种基于共享内存的并行化程序设计的标准，具有开发简单、抽象度高、可移植性强等诸多优点。多核CPU的问世和普及，使廉价的普通PC也能进行基于共享内存的并行计算。使用OpenMP标准，将已有算法在多核PC环境下进行并行计算，能充分应用硬件资源，具有很强的实用性。本文对各种博弈树搜索算法及优化措施进行了分析和比较，并阐述了OpenMP标准下的共享内存的并行程序设计方法。针对中国象棋计算机博弈，本文将空着裁剪、置换表、吃子启发、置换表启发、历史启发、杀手启发融入博弈树搜索的PVS（主要变例搜索）算法，设计了一种混合PVS算法，提高了剪枝效率，使算法能在相同的时间内搜索更深的层次。进一步，以广泛普及的多核PC为环境，在OpenMP2.5标准下，以PVSplitting（主要变例分裂）策略对混合PVS算法进行了并行化设计，相比于串行PVS算法，并行优化后，可充分利用了多核CPU资源，提高了搜索效率。本文还用面向对象方法设计了一个真实的多核PC环境下的中国象棋计算机博弈系统，，将OpenMP下的并行混合PVS算法运用于搜索引擎中，对其进行了实际试验，同时针对优化估值函数的自适应遗传算法进行了改进，并使用OpenMP2.5进行了并行化设计，为多核PC环境下中国象棋计算机博弈系统的设计与优化提供了一种便捷而有效的思路。
[Abstract]:Computer game is a very challenging research direction in artificial intelligence. The research and combination of various game tree search algorithms and optimization measures are also the focus of computer game research. Chess computer games have achieved great success and have long been intelligent enough to beat human champions. The research of Chinese chess computer game started late, more difficult, more challenging, attracted more and more researchers to study it. OpenMP is a parallel programming standard based on shared memory, which has many advantages, such as simple development, high abstraction, strong portability and so on. With the advent and popularity of multi-core CPU, low-cost PC can also perform parallel computing based on shared memory. Using OpenMP standard, the existing algorithms are used in multi-core PC environment, which can make full use of hardware resources and have strong practicability. This paper analyzes and compares various game tree search algorithms and optimization measures, and expounds the parallel programming method of shared memory based on OpenMP standard. Aiming at Chinese chess computer game, this paper designs a hybrid PVS algorithm based on PVS (main variant search) algorithm, which combines empty cut, permutation table, eat-elicitation, permutation table heuristic, historical heuristic and killer heuristic into game tree search. The pruning efficiency is improved so that the algorithm can search deeper layers in the same time. Furthermore, based on the widely used multi-core PC, the hybrid PVS algorithm is parallelized by using the PVSplitting (main variant splitting) strategy under the OpenMP2.5 standard. Compared with the serial PVS algorithm, the multi-core CPU resources can be fully utilized after parallel optimization. The search efficiency is improved. This paper also designs a real Chinese chess computer game system based on multi-core PC using object-oriented method. The parallel hybrid PVS algorithm based on OpenMP is applied to the search engine, and a practical experiment is carried out on it. At the same time, the adaptive genetic algorithm for optimizing the estimation function is improved, and the parallel design is carried out by using OpenMP2.5, which provides a convenient and effective way for the design and optimization of Chinese chess computer game system under multi-core PC environment.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP18

【参考文献】