【摘要】：計(jì)算機(jī)博弈是人工智能中一個(gè)非常具有挑戰(zhàn)性的研究方向，對(duì)各種博弈樹搜索算法和優(yōu)化措施的研究和組合，又是計(jì)算機(jī)博弈中研究的重點(diǎn)。國(guó)際象棋計(jì)算機(jī)博弈已經(jīng)獲得了巨大的成就，早已具備擊敗人類冠軍的智能。中國(guó)象棋計(jì)算機(jī)博弈的研究起步較晚，難度更大，挑戰(zhàn)性更強(qiáng)，吸引了越來(lái)越多的研究者對(duì)其進(jìn)行研究，也取得了不俗的成就。 OpenMP是一種基于共享內(nèi)存的并行化程序設(shè)計(jì)的標(biāo)準(zhǔn)，具有開發(fā)簡(jiǎn)單、抽象度高、可移植性強(qiáng)等諸多優(yōu)點(diǎn)。多核CPU的問(wèn)世和普及，使廉價(jià)的普通PC也能進(jìn)行基于共享內(nèi)存的并行計(jì)算。使用OpenMP標(biāo)準(zhǔn)，將已有算法在多核PC環(huán)境下進(jìn)行并行計(jì)算，能充分應(yīng)用硬件資源，具有很強(qiáng)的實(shí)用性。 本文對(duì)各種博弈樹搜索算法及優(yōu)化措施進(jìn)行了分析和比較，并闡述了OpenMP標(biāo)準(zhǔn)下的共享內(nèi)存的并行程序設(shè)計(jì)方法。針對(duì)中國(guó)象棋計(jì)算機(jī)博弈，本文將空著裁剪、置換表、吃子啟發(fā)、置換表啟發(fā)、歷史啟發(fā)、殺手啟發(fā)融入博弈樹搜索的PVS（主要變例搜索）算法，設(shè)計(jì)了一種混合PVS算法，提高了剪枝效率，使算法能在相同的時(shí)間內(nèi)搜索更深的層次。進(jìn)一步，以廣泛普及的多核PC為環(huán)境，在OpenMP2.5標(biāo)準(zhǔn)下，以PVSplitting（主要變例分裂）策略對(duì)混合PVS算法進(jìn)行了并行化設(shè)計(jì)，相比于串行PVS算法，并行優(yōu)化后，可充分利用了多核CPU資源，提高了搜索效率。 本文還用面向?qū)ο蠓椒ㄔO(shè)計(jì)了一個(gè)真實(shí)的多核PC環(huán)境下的中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)，，將OpenMP下的并行混合PVS算法運(yùn)用于搜索引擎中，對(duì)其進(jìn)行了實(shí)際試驗(yàn)，同時(shí)針對(duì)優(yōu)化估值函數(shù)的自適應(yīng)遺傳算法進(jìn)行了改進(jìn)，并使用OpenMP2.5進(jìn)行了并行化設(shè)計(jì)，為多核PC環(huán)境下中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)的設(shè)計(jì)與優(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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 岳金朋;馮速;;中國(guó)象棋Alpha-Beta搜索算法的研究與改進(jìn)[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年02期

2 王曉鵬;王驕;徐心和;鄭新穎;;中國(guó)象棋與國(guó)際象棋比較分析[J];重慶工學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年01期

3 王驕,王濤,羅艷紅,徐心和;中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)評(píng)估函數(shù)的自適應(yīng)遺傳算法實(shí)現(xiàn)[J];東北大學(xué)學(xué)報(bào);2005年10期

4 唐天兵;謝祥宏;申文杰;韋凌云;嚴(yán)毅;;多核CPU環(huán)境下的并行遺傳算法的研究[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

5 張聰品;劉春紅;徐久成;;博弈樹啟發(fā)式搜索的α-β剪枝技術(shù)研究[J];計(jì)算機(jī)工程與應(yīng)用;2008年16期

6 焦尚彬;劉丁;;博弈樹置換表啟發(fā)式算法研究[J];計(jì)算機(jī)工程與應(yīng)用;2010年06期

7 王京輝,喬衛(wèi)民;基于PVM的博弈樹的網(wǎng)絡(luò)并行搜索[J];計(jì)算機(jī)工程;2005年09期

8 陳國(guó)良;孫廣中;徐云;呂敏;;并行算法研究方法學(xué)[J];計(jì)算機(jī)學(xué)報(bào);2008年09期

9 鄒競(jìng);;基于MTD(f)的中國(guó)象棋人機(jī)博弈算法的設(shè)計(jì)與優(yōu)化[J];計(jì)算機(jī)與數(shù)字工程;2008年09期

10 張明亮;吳俊;李凡長(zhǎng);;極小樹葉結(jié)點(diǎn)數(shù)定理的補(bǔ)充證明及有關(guān)分析[J];模式識(shí)別與人工智能;2011年04期

本文編號(hào)：2204272