【正文】 (int y=0。y15。y++){ for(int x=0。x15。x++){ key^=hash32[board[y][x]][y][x]。 } } return key。}該函數(shù)根據(jù)當(dāng)前棋局棋盤上各位置的棋子狀態(tài)使用hash32數(shù)組中的不同隨機數(shù)進(jìn)行異或運算，生成hash碼，從而保證不同的棋局hash碼盡可能不同。上面僅列出了hash碼的生成方法，校驗值的方法一樣，但使用64位的隨機數(shù)組。另一個版本的hash生成函數(shù)需要父節(jié)點的hash值以及下子的坐標(biāo)，可以知道，父節(jié)點與子節(jié)點僅一個棋盤坐標(biāo)上的棋子不同，僅需要進(jìn)行一次has運算，所以可以大大簡化計算，其實現(xiàn)如下：unsigned long hashCode(unsigned long parHash,int side,int y,int x){ return parHash^ hash32[side][y][x]。}校驗碼的生成方式一樣的就不再說明了。另外兩個函數(shù)getHashItem與setHashItem顧名思義，分別是根據(jù)hash碼取得與設(shè)置hash表元素的值。使用hash方法的Alphabeta截枝搜索在本設(shè)計中將hash表與排序的alphabeta算法相結(jié)合，具體實現(xiàn)在CHashAlphaBeta類中（），與排序的AlphaBeta算法大體差不多，但在每一個節(jié)點的搜索中，加入以下操作，一，檢查該節(jié)點是否已經(jīng)存在于hash表中，若存在并且深度比當(dāng)前的搜索深度大，則該節(jié)點不用搜索，直接返回表中的值。二、計算出該節(jié)點子節(jié)點的hash值和校驗值，查找表中是否有子節(jié)點，若有，則用其值作為預(yù)估值，沒有的話用估值函數(shù)估值作為預(yù)估值然后排序。三、每次子節(jié)點返回后，更新哈稀表。167。 有限范圍限定其實，在棋盤上很多位置都是不必要去搜索它的得分的，我們這里采用一種簡單的判定方法，即如果在某一坐標(biāo)范圍內(nèi)都不存在棋子，則我們認(rèn)為這個位置沒有下子的意義，不必要搜索。在本設(shè)計中半徑范圍為2內(nèi)都沒有棋子，則不搜索。本設(shè)計中將有限范圍限定與hash表、預(yù)估排序的alphabeta結(jié)合，其實現(xiàn)類為CRangeLimit，它繼承自CHashAlphaBeta。需要改變的代碼并不多，在將走法放入要排序的數(shù)組前先檢查該走法的坐標(biāo)范圍為2內(nèi)有沒有棋子，有則加入待排序數(shù)組，否則不加入。167。 多核優(yōu)化現(xiàn)在，計算機已經(jīng)具有一定程度的智能了，但該程序效率仍然不高，當(dāng)深度為3時，現(xiàn)在的計算機可能仍然要花費以分為計時間，第一步用時達(dá)85秒，現(xiàn)代的計算機已經(jīng)向多核發(fā)展，4核已經(jīng)很普及，所以，可以考慮讓每個cpu核心都能能發(fā)揮作用。本程序采用OpenMP優(yōu)化。一、 OpenMP簡介OpenMP是由OpenMP Architecture Review Board牽頭提出的，并已被廣泛接受的，用于共享內(nèi)存并行系統(tǒng)的多線程程序設(shè)計的一套指導(dǎo)性注釋(Compiler Directive)。二、 OpenMP的使用要在Visual C++ 2005 中使用OpenMP其實不難，只要將 Project 的Properties中C/C++里L(fēng)anguage的OpenMP Support開啟（參數(shù)為 /openmp），就可以讓VC++2005 在編譯時支持OpenMP 的語法了；而在編寫使用OpenMP 的程序時，則需要先include OpenMP的頭文件：。在所有的CSearch類的派生類中的Search函數(shù)中遍歷每一種走法的for語句中使用了OpenMP：pragma omp parallel for for(int i=0。i15*15。i++){//償試每一個位置這一循環(huán)試著在棋盤上的每個位置上下子，pragma omp parallel for表示后面的for語句可以并行執(zhí)行。但這些并行執(zhí)行必須在for循環(huán)結(jié)束時同步。三、 需要注意的問題所有并行執(zhí)行需要注意的問題便是共享變量的讀寫，在并行的for循環(huán)中的共享變量（在for循環(huán)外定義的變量）有best和pos，并且對它們進(jìn)行了寫操作，所以必須定義臨界區(qū)（pragma omp critical[臨界區(qū)名]）。另外，在并行運行中所調(diào)用的函數(shù)也應(yīng)該注意共享變量的問題，上面的for循環(huán)中調(diào)用了generate，generate中除估值引擎的指針pe外都使用的是局部變量，而pe中所用的估值函數(shù)value()也全都未涉及共享變量寫的問題，所以就不需要臨界區(qū)操作了。第8章 總結(jié)結(jié)論167。 各算法效率對比下表給出了各種算法的效率（占有用cpu時間）。計算機為白方，黑方先下。計算機為單核的pentium M 。算法123456平均每步耗時極大極小值92183275361449544AlphaBeta182843597695PVS131624364965估值排序AlphaBeta112345估值排序PVS112345Hash+估值排序+AlphaBeta122345有限范圍限定+Hash+估值排序+AlphaBeta000111 各搜索算法在深度3時cpu耗時 各搜索算法在深度4時cpu耗時算法123456平均每步耗時估值排序AlphaBeta293135384143估值排序PVS2932384246488Hash+估值排序+AlphaBeta273541434648有限范圍限定+Hash+估值排序+AlphaBeta011222因為極大極小值算法不截枝，由極大極小值算法可以知道，當(dāng)深度為3時，白方的第一步需要計算224*223*222=11089344個葉子節(jié)點，故計算機每秒能計算大約11089344/92=120536，即每秒大約計算12萬步，可見，估值函數(shù)的效率并不太高。從表（）可以看出，極小窗口算法PVS效率是比AlphaBeta效率要高的，因為它一開始就用很小的窗口搜索，但加入預(yù)估值排序后PVS算法比AlphaBeta算法效率要低一些了，大概是因為預(yù)估值的關(guān)系，一開始搜索到了比較好的節(jié)點，減小了AlphaBeta的窗口，剪枝效率已經(jīng)很高，而PVS算法畢竟要多搜索一次，故反而不如預(yù)估值排序的AlphaBeta算法。當(dāng)引入預(yù)估值排序后，由于一開始就搜索了比較好的走法，所以AlphaBeta的截枝效率大大地提高，加入hash表后效率基本差不多，但第2步卻花了較長時間，再看后面的幾步的時間差，基本上是差不多的。速度最快的是“有限范圍限定+Hash+估值排序+AlphaBeta”，因為有效范圍限定大大減少了搜索范圍。 綜上所述，計算機博弈中的搜索算法是以AlphaBeta截枝為基礎(chǔ)的，其截枝效率的高低取決于AlphaBeta表示的窗口大小，窗口越小，截枝效率越高，其后的各種算法都是圍繞減小AlphaBeta的這個窗口來進(jìn)行改進(jìn)的。167。 成果與不足通過本次畢業(yè)設(shè)計，基本上掌握了博弈算法的構(gòu)成，包括走法產(chǎn)生，估值，和搜索三個部分，并一一對這幾部分進(jìn)行了實現(xiàn)，特別對搜索算法進(jìn)行實現(xiàn)，掌握了基本的AlphaBeta算法原理，能夠初步地根據(jù)實際情況運用AlphaBeta算法并作一定程度的改進(jìn)?，F(xiàn)在計算機向著并行處理方向發(fā)展，在本次設(shè)計中也考慮了并行處理，通過學(xué)習(xí)OpenMP的使用，初步了解和掌握了并行處理的一些基本原理，如同步、互斥、共享變量等使用方法。同時，在實現(xiàn)過程中對軟件工程的一些原理也進(jìn)行了學(xué)習(xí)，初步掌握了軟件開發(fā)的分析、設(shè)計、實現(xiàn)的過程，為將來的進(jìn)一步學(xué)習(xí)實踐打下了一定的基礎(chǔ)。通過本次實踐，也發(fā)現(xiàn)了自己很多的不足，自己的實踐能力還需要進(jìn)一步提高，在設(shè)計過程中經(jīng)驗不中，以后需要多多學(xué)習(xí)，特別是編寫的代碼效率不高。如估值部分的效率還不高，需要進(jìn)一步優(yōu)化。采用Hash表的算法效率還不太高，需要進(jìn)一步優(yōu)化。對于并行的搜索算法沒有進(jìn)行深入的探索，這也是今后努力改進(jìn)的一個方向。人機界面還需要改進(jìn)，不太美觀計算機在思考時程序會出現(xiàn)假死狀態(tài)。上述這些方面都當(dāng)前應(yīng)該改進(jìn)的方面，當(dāng)然，不足之處還有很多，計算機科學(xué)知識浩如大海，在今后我將繼續(xù)努力在計算機科學(xué)領(lǐng)域?qū)W習(xí)探究。參考文獻(xiàn)1．《MFC Windows 程序設(shè)計》清華大學(xué)出版社 Jeff Prosise著2003年7月 2．《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏 吳偉民著著1998年5月3．《PC游戲編程（人機博弈）》重慶大學(xué)出版社 王小春著2002年6月4.《深入淺出MFC第2版》 華中科技大學(xué)出版社 侯俊杰 著2001年2月++面向?qū)ο蟪绦蛟O(shè)計 清華大學(xué)出版社 譚浩強2006年1月6.《OpenMp API用戶指南》 百度文庫 Sun studio2011年1月7．《軟件工程》機械工業(yè)出版社 陸麗娜著2000年3月 8．《連珠五子棋入門》金盾出版社 彭建國，那威著2001年7月 9．《人工智能及其應(yīng)用》 清華大學(xué)出版社 蔡自興1999年1月36致　謝在論文即將完成之際，本人在此向所有關(guān)心我的及幫助我的老師和同學(xué)們致以最真誠的感謝。在本次畢業(yè)設(shè)計中，我從指導(dǎo)老師官老師，從選題到論文結(jié)束，官老師都給了我不少幫助，提出了許多寶貴意見，沒有他的指導(dǎo)，我就不能較好的完成課題設(shè)計的任務(wù)。另外，我還要感謝在這幾年來對我有所教導(dǎo)的老師，他們孜孜不倦的教誨不但讓我學(xué)到了很多知識，而且讓我掌握了學(xué)習(xí)的方法，更教會了我做人處事的道理，在此表示感謝。