基于OpenMP的并行混合PVS算法及其應(yīng)用
發(fā)布時間：2018-08-26 08:16
【摘要】：計算機博弈是人工智能中一個非常具有挑戰(zhàn)性的研究方向，對各種博弈樹搜索算法和優(yōu)化措施的研究和組合，又是計算機博弈中研究的重點。國際象棋計算機博弈已經(jīng)獲得了巨大的成就，早已具備擊敗人類冠軍的智能。中國象棋計算機博弈的研究起步較晚，難度更大，挑戰(zhàn)性更強，吸引了越來越多的研究者對其進行研究，也取得了不俗的成就。 OpenMP是一種基于共享內(nèi)存的并行化程序設(shè)計的標準，具有開發(fā)簡單、抽象度高、可移植性強等諸多優(yōu)點。多核CPU的問世和普及，使廉價的普通PC也能進行基于共享內(nèi)存的并行計算。使用OpenMP標準，將已有算法在多核PC環(huán)境下進行并行計算，能充分應(yīng)用硬件資源，具有很強的實用性。 本文對各種博弈樹搜索算法及優(yōu)化措施進行了分析和比較，并闡述了OpenMP標準下的共享內(nèi)存的并行程序設(shè)計方法。針對中國象棋計算機博弈，本文將空著裁剪、置換表、吃子啟發(fā)、置換表啟發(fā)、歷史啟發(fā)、殺手啟發(fā)融入博弈樹搜索的PVS（主要變例搜索）算法，設(shè)計了一種混合PVS算法，提高了剪枝效率，使算法能在相同的時間內(nèi)搜索更深的層次。進一步，以廣泛普及的多核PC為環(huán)境，在OpenMP2.5標準下，以PVSplitting（主要變例分裂）策略對混合PVS算法進行了并行化設(shè)計，相比于串行PVS算法，并行優(yōu)化后，可充分利用了多核CPU資源，提高了搜索效率。 本文還用面向?qū)ο蠓椒ㄔO(shè)計了一個真實的多核PC環(huán)境下的中國象棋計算機博弈系統(tǒng)，，將OpenMP下的并行混合PVS算法運用于搜索引擎中，對其進行了實際試驗，同時針對優(yōu)化估值函數(shù)的自適應(yīng)遺傳算法進行了改進，并使用OpenMP2.5進行了并行化設(shè)計，為多核PC環(huán)境下中國象棋計算機博弈系統(tǒng)的設(shè)計與優(yōu)化提供了一種便捷而有效的思路。
[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.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP18
本文編號：2204272
[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.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP18
【參考文獻】
相關(guān)期刊論文 前10條
1 岳金朋;馮速;;中國象棋Alpha-Beta搜索算法的研究與改進[J];北京師范大學(xué)學(xué)報(自然科學(xué)版);2009年02期
2 王曉鵬;王驕;徐心和;鄭新穎;;中國象棋與國際象棋比較分析[J];重慶工學(xué)院學(xué)報(自然科學(xué)版);2007年01期
3 王驕,王濤,羅艷紅,徐心和;中國象棋計算機博弈系統(tǒng)評估函數(shù)的自適應(yīng)遺傳算法實現(xiàn)[J];東北大學(xué)學(xué)報;2005年10期
4 唐天兵;謝祥宏;申文杰;韋凌云;嚴毅;;多核CPU環(huán)境下的并行遺傳算法的研究[J];廣西大學(xué)學(xué)報(自然科學(xué)版);2009年04期
5 張聰品;劉春紅;徐久成;;博弈樹啟發(fā)式搜索的α-β剪枝技術(shù)研究[J];計算機工程與應(yīng)用;2008年16期
6 焦尚彬;劉丁;;博弈樹置換表啟發(fā)式算法研究[J];計算機工程與應(yīng)用;2010年06期
7 王京輝,喬衛(wèi)民;基于PVM的博弈樹的網(wǎng)絡(luò)并行搜索[J];計算機工程;2005年09期
8 陳國良;孫廣中;徐云;呂敏;;并行算法研究方法學(xué)[J];計算機學(xué)報;2008年09期
9 鄒競;;基于MTD(f)的中國象棋人機博弈算法的設(shè)計與優(yōu)化[J];計算機與數(shù)字工程;2008年09期
10 張明亮;吳俊;李凡長;;極小樹葉結(jié)點數(shù)定理的補充證明及有關(guān)分析[J];模式識別與人工智能;2011年04期
本文編號：2204272
本文鏈接：http://www.sikaile.net/kejilunwen/sousuoyinqinglunwen/2204272.html
最近更新
教材專著
