基于OpenMP的并行混合PVS算法及其應(yīng)用.pdf

1、 計(jì)算機(jī)博弈是人工智能中一個(gè)非常具有挑戰(zhàn)性的研究方向，對(duì)各種博弈樹(shù)搜索算法和優(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)，具有開(kāi)發(fā)簡(jiǎn)單、抽象度高、可移植性強(qiáng)等諸多優(yōu)點(diǎn)。多核 CPU 的

2、問(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ì)各種博弈樹(shù)搜索算法及優(yōu)化措施進(jìn)行了分析和比較，并闡述了OpenMP標(biāo)準(zhǔn)下的共享內(nèi)存的并行程序設(shè)計(jì)方法。針對(duì)中國(guó)象棋計(jì)算機(jī)博弈，本文將空著裁剪、置換表、吃子啟發(fā)、置換表啟發(fā)、歷史啟發(fā)、殺手啟發(fā)融入博弈樹(shù)搜索的 PVS(主要變例搜索)算法，設(shè)計(jì)了一種混合

3、PVS 算法，提高了剪枝效率，使算法能在相同的時(shí)間內(nèi)搜索更深的層次。進(jìn)一步，以廣泛普及的多核PC 為環(huán)境，在 OpenMP 2.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 算法