基于OpenMP的并行混合PVS算法及其應用.pdf

1、 計算機博弈是人工智能中一個非常具有挑戰(zhàn)性的研究方向，對各種博弈樹搜索算法和優(yōu)化措施的研究和組合，又是計算機博弈中研究的重點。國際象棋計算機博弈已經(jīng)獲得了巨大的成就，早已具備擊敗人類冠軍的智能。中國象棋計算機博弈的研究起步較晚，難度更大，挑戰(zhàn)性更強，吸引了越來越多的研究者對其進行研究，也取得了不俗的成就。
OpenMP是一種基于共享內(nèi)存的并行化程序設計的標準，具有開發(fā)簡單、抽象度高、可移植性強等諸多優(yōu)點。多核 CPU 的

2、問世和普及，使廉價的普通 PC也能進行基于共享內(nèi)存的并行計算。使用 OpenMP標準，將已有算法在多核 PC環(huán)境下進行并行計算，能充分應用硬件資源，具有很強的實用性。
本文對各種博弈樹搜索算法及優(yōu)化措施進行了分析和比較，并闡述了OpenMP標準下的共享內(nèi)存的并行程序設計方法。針對中國象棋計算機博弈，本文將空著裁剪、置換表、吃子啟發(fā)、置換表啟發(fā)、歷史啟發(fā)、殺手啟發(fā)融入博弈樹搜索的 PVS(主要變例搜索)算法，設計了一種混合

3、PVS 算法，提高了剪枝效率，使算法能在相同的時間內(nèi)搜索更深的層次。進一步，以廣泛普及的多核PC 為環(huán)境，在 OpenMP 2.5 標準下，以 PVSplitting(主要變例分裂)策略對混合 PVS算法進行了并行化設計，相比于串行 PVS算法，并行優(yōu)化后，可充分利用了多核 CPU資源，提高了搜索效率。
本文還用面向?qū)ο蠓椒ㄔO計了一個真實的多核PC環(huán)境下的中國象棋計算機博弈系統(tǒng)，將 OpenMP 下的并行混合 PVS 算法