【正文】 另外，我還要感謝在這幾年來對我有所教導的老師，他們孜孜不倦的教誨不但讓我學到了很多知識，而且讓我掌握了學習的方法，更教會了我做人處事的道理，在此表示感謝。人機界面還需要改進，不太美觀計算機在思考時程序會出現(xiàn)假死狀態(tài)。通過本次實踐，也發(fā)現(xiàn)了自己很多的不足，自己的實踐能力還需要進一步提高，在設計過程中經驗不中，以后需要多多學習，特別是編寫的代碼效率不高。167。從表（）可以看出，極小窗口算法PVS效率是比AlphaBeta效率要高的，因為它一開始就用很小的窗口搜索，但加入預估值排序后PVS算法比AlphaBeta算法效率要低一些了，大概是因為預估值的關系，一開始搜索到了比較好的節(jié)點，減小了AlphaBeta的窗口，剪枝效率已經很高，而PVS算法畢竟要多搜索一次，故反而不如預估值排序的AlphaBeta算法。 各算法效率對比下表給出了各種算法的效率（占有用cpu時間）。但這些并行執(zhí)行必須在for循環(huán)結束時同步。二、 OpenMP的使用要在Visual C++ 2005 中使用OpenMP其實不難，只要將 Project 的Properties中C/C++里Language的OpenMP Support開啟（參數(shù)為 /openmp），就可以讓VC++2005 在編譯時支持OpenMP 的語法了；而在編寫使用OpenMP 的程序時，則需要先include OpenMP的頭文件：。167。 有限范圍限定其實，在棋盤上很多位置都是不必要去搜索它的得分的，我們這里采用一種簡單的判定方法，即如果在某一坐標范圍內都不存在棋子，則我們認為這個位置沒有下子的意義，不必要搜索。使用hash方法的Alphabeta截枝搜索在本設計中將hash表與排序的alphabeta算法相結合，具體實現(xiàn)在CHashAlphaBeta類中（），與排序的AlphaBeta算法大體差不多，但在每一個節(jié)點的搜索中，加入以下操作，一，檢查該節(jié)點是否已經存在于hash表中，若存在并且深度比當前的搜索深度大，則該節(jié)點不用搜索，直接返回表中的值。上面僅列出了hash碼的生成方法，校驗值的方法一樣，但使用64位的隨機數(shù)組。x15。Hash碼的代碼如下：unsigned long inline hashCode(int board[][15]){//hash值生成函數(shù) unsigned long key=0。 void setHashItem(unsigned long key,HashItem amp。//根據(jù)棋盤生成32位hash值 unsigned long hashCode(unsigned long parHash,int side,int y,int x)。//64位校驗生成隨機數(shù) unsigned long hash32[3][15][15]。這里的設計思想是，如何歷史得分的深度比當前高，證明歷史得分比當前所期望的精度還要高（深度越深精度越高），可以直接采用歷史得分，否則，只能像預估值一樣，作為搜索時的一個參考（參與排序）。//得到得分的搜索深度}。顯而易見，哈稀表很適合完成這項工作。預估值排序的PVS實現(xiàn)在CSortedPVS類中。該結構保存子節(jié)點某一走法（記錄在pos中）的粗略估值，用stl::vector psArray保存所有子節(jié)點及其估值，用STL模板庫中的sort函數(shù)進行排序，該排序算法需要向量中的元素有重載的“”操作函數(shù)，用來比較排序。 int value。167。if(valuealpha) value=generate(cboard,WHITE,depth1,pe,value,beta)。 極小窗口搜索/PVS算法一、算法分析顧名思義，極小窗口搜索中的窗口是最小的（0容量），該算法先計算第一個子節(jié)點的值作為當前最佳節(jié)點值best，如果是取極大值的節(jié)點，對以后的子節(jié)點搜索中，用(alpha,alpha+1)窗口大小搜索，對于取極小值的節(jié)點，則用(beta1,beta)對后繼子節(jié)點進行搜索，得到值value，由于不能取邊界，這實際上是零大小的窗口搜索，所以很快能得到結果，比如取極大值的節(jié)點，要么value比alpha大，要么比alpha小，比alpha小的節(jié)點直接可以忽略過了，但如果比alpha大，value也并不準確，但可以確定，最大的值肯定比value還要大，故必須重新搜索，采用新的窗口大小，取極大值的節(jié)點采用(value,beta)，取極小值的節(jié)點采用(alph,value)進行搜索。這可以從兩個方面加以考慮，第一種就是人為地減小這個窗口的大小，比較經典的算法有Failsoft AlphaBeta算法、渴望搜索、極小窗口搜索（又稱PVS算法），PVS算法是一種很優(yōu)秀的算法，在實際應用中相當普遍，故本文采用PVS搜索來優(yōu)化。 }167。 if(valuebeta){ beta=value。 int cboard[15][15]。i15*15。 if(valuealpha){ alpha=value。 int cboard[15][15]。i15*15。//最小子節(jié)點的最 } return beta。 board[y][x]=side。 board[y][x]=NONE。 到葉子節(jié)點估值返回?！璶1n2nknn21n2m…………n2kn為極小值節(jié)點（白方）n1到nk為極大值節(jié)點（黑方）n1=20n11=33 Beta 截枝再來看另一方的情況，如上圖（圖83）情況與圖81相反，n為取極小值節(jié)點，它的某子節(jié)點的值為20(n1)，搜索其后繼子節(jié)點，如圖中的n2，n2的子節(jié)點中某子節(jié)點n21的值為33，而n2取極大值，n2的值至少為33，故n2的父節(jié)點不可能選擇n2，所以n2中一旦搜索發(fā)現(xiàn)其子節(jié)點值大于兄弟節(jié)點中的最小值，就沒有搜索必要了。167。 else best=min(value,best)。 游戲結束返回估值 深度為0估值返回 Best=極大極小值 for(each possible pos){ board[y][x]=side。在上面深度為1的算法中，我們看到，每一個結點產生子結點，要在這子結點中選擇一個對自己最有利的子結點，所以，對于黑方來說，總是選擇子結點值為最大的結點來走，而不會選擇其它結點，所以，該最大值的子結點值就是該結點的值。要讓計算機足夠聰明，必須采用某種搜索算法。 =。x++){ board[y][x]=side。 for(int y=0。 極大極小值算法有了估值算法，我們可以簡單地試著產生一個最大估值的走法，如下圖所示：……12n 深度為1的對弈樹根結點表示當前棋盤局勢，此時該電腦下子，它試著產生每一種可能走法，對于五子棋，最多15*15種，每一種走法都用估值引擎估值，如果此時電腦執(zhí)黑子，它會選擇估值最大的一種走法（估值引擎中棋局的值是黑方的價值減去白方的價值），因為這種走法對自己最有利，如果執(zhí)白子，則選擇估值最小的走法。計算值的過程實際上就是統(tǒng)計連續(xù)相同二子，三子，四子，五子的過程，依次按左下方，下方，右下方，右方掃描棋盤上每個棋子連續(xù)相連數(shù)目，然后計算分數(shù)，最后加上每個棋子所在位置的分數(shù)。另外，每個位置也給予不同的分數(shù)，如下面數(shù)組所示：const int CEvaluation::m_nPosValue[15][15]={ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,1,2,2,2,2,2,2,2,2,2,2,2,1,0}, {0,1,2,3,3,3,3,3,3,3,3,3,2,1,0}, {0,1,2,3,4,4,4,4,4,4,4,3,2,1,0}, {0,1,2,3,4,5,5,5,5,5,4,3,2,1,0}, {0,1,2,3,4,5,6,6,6,5,4,3,2,1,0}, {0,1,2,3,4,5,6,7,6,5,4,3,2,1,0}, {0,1,2,3,4,5,6,6,6,5,4,3,2,1,0}, {0,1,2,3,4,5,5,5,5,5,4,3,2,1,0}, {0,1,2,3,4,4,4,4,4,4,4,3,2,1,0}, {0,1,2,3,3,3,3,3,3,3,3,3,2,1,0}, {0,1,2,2,2,2,2,2,2,2,2,2,2,1,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} }。//沖3分數(shù)const int THREE=300。const int MAX_VALUE=99999。167。所以該Think操作就是查看鼠標是否按下，如果按下則取得按下位置返回。另外，從歷史棧中取出最后一次下子坐標，將棋子外線用紅色繪制。載入與保存一致，先讀取文件標識，如果標識不對，則不載入，然后載入棋盤數(shù)據(jù)，再載入歷史棧，然后根據(jù)歷史棧中最后一個模棋子設置好當前玩家。 設置計算機智力對話框 悔棋、新局、保存、載入、退出按鈕在棋盤類（CChessBoard）中用一個棧來保存下棋歷史，該棧中數(shù)據(jù)元素為POINT類型，悔棋時進行出棧操作，每次出棧兩個棋子位置，將它們對應棋盤坐標設置為無子(NONE)。}167。而基于對話框的程序有自己的消息循環(huán)，在消息循環(huán)中要調用ContinueDodal()函數(shù)，幫游戲循環(huán)合適在這一函數(shù)中處