基于intel多核多處理器的兩個(gè)經(jīng)典游戲ai算法的并行化研究

1、R E S A E R C H O N T H E P A R A I ，L I Z A T I O N O FT W O C L A S S I C A L G A M E ’S m A L G O R I T H MB A S E D O N I N T E L ’SM U I J I C O R EM U L T I P R O C E S S O RA T h e s i s S u b m i t t e dt oS o u

2、t h e a s tU n i v e r s i t yF o r t h e A c a d e m i c D e g r e eo f M a s t e ro f‘●一 E n g i n e e r i n g 一 一B YZ o u F e n gS u p e r v i s e db yP r o f ．Y A N G Q u a n —s h e n gS c h o o lo f C o m p u t e r

3、S c i e n c e a nE n g i n e e r i n gS o u t h e a s tU n i v e r s i t y目前，隨著多核處理器的迅速發(fā)展，單核時(shí)代已經(jīng)成為歷史，尤其是由多個(gè)多核處理器組成的多處理器系統(tǒng)，更是為應(yīng)用軟件性能改善提供了硬件基礎(chǔ)。然而我們的軟件卻大多停留在單核時(shí)代，并沒(méi)有充分利用多核多處理器架構(gòu)所帶來(lái)的優(yōu)勢(shì)，對(duì)自身性能加以提升。對(duì)現(xiàn)有軟件的改進(jìn)以及并行程序的開(kāi)發(fā)勢(shì)在必行。因此與多核技術(shù)

4、相結(jié)合，把過(guò)去串行化的程序并行化將能充分利用多核多處理器的性能優(yōu)勢(shì)，提高程序的效率。．現(xiàn)今，游戲產(chǎn)業(yè)也是迅猛發(fā)展，在多核多處理器架構(gòu)的P C 上應(yīng)用很廣泛，然而現(xiàn)在的很多游戲沒(méi)能充分發(fā)揮多核多處理器架構(gòu)的優(yōu)勢(shì)。本文以棋類游戲中的五子棋和球類游戲中的足球作為例子，對(duì)這兩個(gè)游戲的兩種經(jīng)典越算法一博弈樹(shù)搜索算法和遺傳算法進(jìn)行并行化研究。有關(guān)提高樹(shù)搜索算法的性能的研究，一直以來(lái)都是學(xué)術(shù)界的熱點(diǎn)問(wèn)題，新的算法層出不窮。而研究樹(shù)搜索算法最重要的實(shí)驗(yàn)

5、溫床是在研究如何在二人棋類游戲中找到最優(yōu)解，即游戲樹(shù)的搜索。自上世紀(jì)9 0 年代以來(lái)，學(xué)者和研究員們對(duì)于樹(shù)搜索算法的研究轉(zhuǎn)向了并行化并提出了數(shù)量眾多的并行樹(shù)搜索算法。同時(shí)，遺傳算法在人工智能中發(fā)揮了重要作用，遺傳算法的并行化研究也日趨重要。我國(guó)有關(guān)遺傳算法和并行計(jì)算的研究，從2 0 世紀(jì)9 0 年代以來(lái)一直不斷地發(fā)展，特別是近年來(lái)，遺傳算法和并行計(jì)算的應(yīng)用在許多領(lǐng)域取得了很好的效果，成就矚目。本文首先分析了多核多處理器架構(gòu)的特點(diǎn)，提出了