【正文】 求 7第3章 人機界面設計 8第4章 面向?qū)ο蠓治?11167。 人機博弈和五子棋 5167。 人工智能 5167。 功能要求 7167。 功能模型 12第5章 面向?qū)ο笤O計 14167。 游戲循環(huán) 17167。 極大極小值算法 21167。 預估排序和歷史啟發(fā) 30167。 成果與不足 36參考文獻 37致　謝 38第1章 引言167。它的發(fā)展歷史和計算機科學的發(fā)展歷史是聯(lián)系在一起的，但也不僅僅局限于計算機科學，也涉及到心理學、哲學、語言學、醫(yī)學等很多門學科。 對弈規(guī)則 每種對弈游戲都有不同的規(guī)則，規(guī)定了棋子的走法（如象棋）或者能下子的位置以及勝負的判定。它在博弈技術中也是很重要的，從某種意義上來說，搜索也是為了估值，或者說對估值作修正。第2章 需求分析167。能設置計算機智能等級。167。如果退出程序，此時顯示“確認退出”對話框。其屬性如下：（1） Board，記錄棋盤上各棋子的位置信息。玩家對象：表示下棋者，可以是人，計算機，一個棋盤對象對應兩個玩家對象。167。接收下子：該操作由棋盤對象負責，它接收玩家發(fā)來的下子位置，同時判斷是否合法，不合法則不作任何操作，合法則改變棋盤狀態(tài)，以及把當前玩家更改為另一方。棋盤類(1)屬性board：表示1515棋盤，可用一個二維數(shù)組表示int board[15][15]。Undo()，接受玩家的悔棋，恢復棋盤到該玩家上次應下子的狀態(tài)。int IsGameOver()。CPlayer *pBlackPlayer,*pWhitePlayer,*pCurrentPlayer。//所指定位置可以放相當?shù)钠遄臃祷豻rue，否則false bool Undo(void)。 玩家類，它表示玩家，它是一個純虛類，為“人”、“計算機”玩家的公共接口。//該玩家所持何子public: virtual POINT Think(char board[][15])=0。167。在游戲循環(huán)中，每當有一個玩家由Think()操作得到了一個下子位置，然后就調(diào)用棋盤類的PutChess()來下子，該函數(shù)檢查下子位置是否合法，如果不合法，則什么也不做，直接返回。167。//重繪棋盤 int side=()。如下圖所示： 五子棋程序界面 黑方，白方下拉列表框黑白下拉列表框在CFiveChessDlg類中類型為CComboBox類的成員對象， 名稱分別為m_boBlack、m_boWhite。保存按鈕按下后先彈出一個保存文件的對話框。 棋盤的繪制棋盤的繪制在CFiveChessDlg類中的重繪函數(shù)（OnPaint）中處理，先用畫線函數(shù)畫好棋盤網(wǎng)格，15*15個格，從坐標（15，15）處繪制，每格30象素。167。一直在正確位置按下了鼠標為止，然后清除掉bMouse標志（表示我已經(jīng)下過棋子了，需要重新接收鼠標按下）。計算機估值也就是對這種好壞的一個量化，最簡單的是靜態(tài)估值，它僅從當前棋局來考慮，五子棋的靜態(tài)估值最簡單直觀的便是根據(jù)相連的棋子數(shù)來評價棋局好壞。//沖2分數(shù)const int TWO=40。//沖4分數(shù)const int FOUR=2000。其定義如下：int value(int board[][15],int side)。故有一個重載版的估值函數(shù)：int value(int board[][15],int side,int pvalue,int y,int x)。 if(side==BLACK) best=MAX_VALUE。y++)for(int x=0。 board[y][x]=NONE。 }}return pos。class CSearch{public: virtual POINT Search(int board[][15],int side,int depth,CEvaluation *pE)=0。但是此時n1……nk的節(jié)點值此時還不知，比如說n1的值必須要通過計算n1的子結點n11……n1k，一直到達葉子結點為止，n結點為黑方，則n1為白方，它會選擇所有子結點值為最小的作為自己的結點值，n2,n3,……,nk結點的值計算也一樣，最后，n2,n3,……,nk當中最大的一個結點就作為n的結點值，也就是需要確定的走法。 board[y][x]=NONE。}CmaxMinSearch類在其公共接口中調(diào)用這個函數(shù)，選擇最佳的一個走法，其Search函數(shù)如下：POINT CMaxMinSearch::Search(int board[][15],int side,int depth,CEvaluation *pe)。我們將取極大值節(jié)點（上圖中n）所產(chǎn)生子節(jié)點的最大值用變量alpha表示，如果子節(jié)點（極小值節(jié)點）在搜索過程中，產(chǎn)生的孫子節(jié)點值小于alpha，則子節(jié)點不需要搜索了，這叫做alpha截枝。再推而廣之，任何一層取最小值的節(jié)點，它的子節(jié)點值大于beta，則應該截枝。 board[y][x]=side。//子節(jié)點的最大值記錄到alpha中 } return alpha。 board[y][x]=NONE。 int alpha=MAX_VALUE,beta=MAX_VALUE。int x=i%15。 cboard[y][x]=BLACK。 =y。int x=i%15。 cboard[y][x]=WHITE。 =y。故對于最取節(jié)點，alpha=MAX_VALUE，beta=MAX_VALUE，而alphabeta算法在搜索取極大值節(jié)點的子節(jié)點時，alpha值不怕增大，在搜索取最小值節(jié)點的子節(jié)點時，beta值不斷減小，隨著這個窗口不斷減小，剪枝效率也就越來越高。后面我們一分別實現(xiàn)。所以，僅需要對Search函數(shù)中調(diào)用generate處稍稍進行修改：將黑方處的代碼：int value=generate(board,WHITE,depth1,pe,alpha,beta)。改為：int value=generate(cboard,BLACK,depth1,pe,beta1,beta)。這可以采用子節(jié)點預估值排序和歷史啟發(fā)兩種方式實現(xiàn)一、 預估排序?qū)τ谖遄悠澹畲致缘暮靡慌袛鄻藴示褪强雌灞P上同一方的棋子連續(xù)相連的個數(shù)，在大多數(shù)情況也確實是這樣，我們的估值函數(shù)就是這樣編寫的，所以，對于要搜索的子節(jié)點，可以對這些子節(jié)點先進行粗略的估值，將這些子節(jié)點按他們的估值進行排序，然后，按排序后的節(jié)點順序進行搜索。b){ return value。預估值排序的AlphaBeta算法實現(xiàn)在CSortedAlphaBeta類中。所要解決的問題又有兩個，一是如何保存已經(jīng)搜索過的歷史記錄，二是如果快速取得這些保存的記錄。//64位hash校驗值 int value。具體原理篇幅所限，不再贅述，請參見hash表的相關文章。//hash表大小 HashItem *buf。 ~CBoardHash(void)。 __int64 checkSum(unsigned long long parCheck,int side,int y,int x)。}這里介紹它們的公共接口，hashCode和checkSum有兩個重載版本，一個接受棋盤數(shù)組，根據(jù)棋局信息生成hash碼和校驗值，hash碼用來在hash表中定位，校驗值用來檢查根據(jù)hash碼定位于表中的信息是否就是當前的棋局信息（通過當前棋局調(diào)用checkSum函數(shù)與表項中的check_sum比較）。y15。 } } return key。}校驗碼的生成方式一樣的就不再說明了。三、每次子節(jié)點返回后，更新哈稀表。本設計中將有限范圍限定與hash表、預估排序的alphabeta結合，其實現(xiàn)類為CRangeLimit，它繼承自CHashAlphaBeta。本程序采用OpenMP優(yōu)化。i15*15。另外，在并行運行中所調(diào)用的函數(shù)也應該注意共享變量的問題，上面的for循環(huán)中調(diào)用了generate，generate中除估值引擎的指針pe外都使用的是局部變量，而pe中所用的估值函數(shù)value()也全都未涉及共享變量寫的問題，所以就不需要臨界區(qū)操作了。計算機為單核的pentium M 。速度最快的是“有限范圍限定+Hash+估值排序+AlphaBeta”，因為有效范圍限定大大減少了搜索范圍?，F(xiàn)在計算機向著并行處理方向發(fā)展，在本次設計中也考慮了并行處理，通過學習OpenMP的使用，初步了解和掌握了并行處理的一些基本原理，如同步、互斥、共享變量等使用方法。采用Hash表的算法效率還不太高，需要進一步優(yōu)化。參考文獻1．《MFC Windows 程序設計》清華大學出版社 Jeff Prosise著2003年7月 2．《數(shù)據(jù)結構》嚴蔚敏 吳偉民著著1998年5月3．《PC游戲編程（人機博弈）》重慶大學出版社 王小春著2002年6月4.《深入淺出MFC第2版》 華中科技大學出版社 侯俊杰 著2001年2月++面向?qū)ο蟪绦蛟O計 清華大學出版社 譚浩強2006年1月6.《OpenMp API用戶指南》 百度文庫 Sun studio2011年1月7．《軟件工程》機械工業(yè)出版社 陸麗娜著2000年3月 8．《連珠五子棋入門》金盾出版社 彭建國，那威著2001年7月 9．《人工智能及其應用》 清華大學出版社 蔡自興1999年1月36致　謝在論文即將完成之際，本人在此向所有關心我的及幫助我的老師和同學們致以最真誠的