Parallel Hybrid PVS Algorithm Based On OpenMP And Its Application

Computer game is a challenging research branch in artificial intelligence, astudy and combination of various search algorithm and optional approach of gametree, and a key point among the computer game researches. Chess computer gamehas got great achievement in the world and has owned the intelligence to beat thehuman champion. However, the research on Chinese chess computer game startedmuch later, and therefore it has more difficulties and greater challenge. More andmore researchers have interest in it and have had good success.OpenMP is a standard of parallel programming design based on shared-memory.It has many advantages, such as simple development, high abstract degree andprobability. With the appearance and popularity of multi-core processor, the commonPC with low-price can be used to parallel computing. If we put the former algorithminto the PC with multi-core processor and have the parallel computing under theOpenMP standard, we can make full use of hardware sources, so it has morepracticability.This paper analyzes and compares kinds of search algorithm and optionalapproach of game tree and elaborates the designing methods of shared-memoryparallel programming under the OpenMP standard. In the light of Chinese chesscomputer game, the paper combines the null move pruning, translation table,capturing heuristic, killer heuristic, history heuristic and translation table heuristicinto the PVS algorithm aiming at game tree search and mix them into PVS algorithmso that we can improve the efficiency of pruning and make the algorithm searchmore deeply with the same time consuming. Moreover, by means of PVSplitting inthe popular multi-core processor under the OpenMP standard, the paper paralleloptimizes a hybrid PVS algorithm to fully utilize multi-core processor sources andimprove the efficiency of search.What’s more, the paper designs a system of Chinese chess computer game in thecondition of a real multi-core processor by the object-oriented approach andexperiments on the parallel hybrid PVS algorithm. At the same time the paperimproves and designs parallel the adaptive genetic algorithm to optimize evaluationfunction in the OpenMP2.5standard and provides a convenient and effectivethought used to design and optimize the system of Chinese chess computer game in the condition of multi-core processor.