【正文】 得分時(shí)的深度，因?yàn)樵跉v史搜索時(shí)，某些節(jié)點(diǎn)的值可能是比較靠近葉子節(jié)點(diǎn)時(shí)得到的。//棋局的歷史搜索得分 int depth。hash表由于五子棋的子節(jié)點(diǎn)很多（每層最多15*15個(gè)），不可能保存所有的搜索節(jié)點(diǎn)，故只能保存部分節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)很多時(shí)，當(dāng)前搜索的節(jié)點(diǎn)是否被搜索過，如何快速地取得該節(jié)點(diǎn)，這個(gè)時(shí)間最好是常量。也可以將預(yù)估值排序與PVS算法相結(jié)合，與預(yù)估排序的AlphaBeta算法大致相同。 }}。程序中用CSortedAlphaBeta類實(shí)現(xiàn)了排序的AlphaBeta算法，定義了結(jié)構(gòu)：struct CPointScore{ POINT pos。if(valuealpha) value=generate(cboard,WHITE,depth1,pe,alpha,value)。改為：int value=generate(cboard,WHITE,depth1,pe,alpha,alpha+1)。167。因而，改進(jìn)alphabeta效率的關(guān)鍵就在于怎么盡可能地縮小(alpha,beta)這個(gè)窗口的大小而又不失其正確性。 } } } return pos。 int value=generate(cboard,BLACK,depth1,pE,alpha,beta)。 if(board[y][x]) continue。 } } }else{ for(int i=0。 int value=generate(cboard,WHITE,depth1,pE,alpha,beta)。 if(board[y][x]) continue。 if(side==BLACK){ for(int i=0。 if(valuebeta) beta=value。//返回最大值 }else{ for(each possible move){ if(alpha=beta) return beta。 int value=alphbeta(board,anotherside,depth1,alpha,beta)。綜合兩種情況，由此而得到alphabeta算法，下面用偽碼表示:int generate(board,int side,int depth,int alpha,int beta){ 游戲結(jié)束估值返回?！璶1n2nknn21n2m…………n2kn為極大值節(jié)點(diǎn)（黑方）n1到nk為極小值節(jié)點(diǎn)（白方）n1=50……nxnx1…………nxknxmnx極小值節(jié)點(diǎn)（白方）極大值節(jié)點(diǎn)再推廣到搜索深度很深的情況，如上圖（圖82）所示，取極大的值節(jié)點(diǎn)n的不知道哪一代孫子節(jié)點(diǎn)nx，它的祖先為n2m，n2，n，它為取極小值節(jié)點(diǎn)，假設(shè)它的某子節(jié)點(diǎn)的值小于n1=50，假如是nx1=40，那么nx是否應(yīng)該放棄其子節(jié)點(diǎn)的搜索而截枝呢？我們可以這樣推論：n的子節(jié)點(diǎn)現(xiàn)在搜索得到的最大值是50，alpha=50,對于n的子節(jié)點(diǎn)n2……nk，它們在搜索過程中，所產(chǎn)生的不被截枝的任一子節(jié)點(diǎn)必須大于50（否則必被截枝），故n2m未被截枝大于50,n2m是取極大值的節(jié)點(diǎn)，所以其子節(jié)點(diǎn)中必有大于50的節(jié)點(diǎn)，故可得到在n2m這一層所得到的最大節(jié)點(diǎn)值alpha≥50，由此可以再推而廣之，n2m的子孫中，凡是取極大值的節(jié)點(diǎn)，它們的子孫節(jié)點(diǎn)的最大值都應(yīng)該≥50，到了nx這一層，nx是取極小值的節(jié)點(diǎn)，它的父親是取極大值的節(jié)點(diǎn)，所以alpha也應(yīng)該≥50，故nx1=40應(yīng)該被截枝。它調(diào)用generate函數(shù)計(jì)算得出子節(jié)點(diǎn)的值，然后選擇一個(gè)最佳子節(jié)點(diǎn)的坐標(biāo)返回，作為下子的位置。 if(side==BLACK) best=max(value,best)。程序中極大極小搜索引擎的類為CMaxMinSearch，它繼承至CSearch，按指定的深度，搜索產(chǎn)生一個(gè)走法：其搜索引擎?zhèn)未a表示如下：int generate(board,int side,int depth){ int best。// }。}有了這個(gè)算法，計(jì)算機(jī)勉強(qiáng)有點(diǎn)智能，可以下一下棋了，但它還是比較笨，只管眼前這一步，而不能看到兩步，三步，或者以后更多步的結(jié)果。 if(valuebest){ best=value。x15。 else best=MAX_VALUE。其中pvalue是父棋局的估值，(x,y)指出了下子的位置167。board傳入棋局狀態(tài)，value給出估值，所得值是相對于黑方來說的，黑方局勢越好，估值越大，反之，白方就要盡可能讓這個(gè)值越小。//活4分?jǐn)?shù)MAX_VALUE是最大值表示會贏的局面分?jǐn)?shù)，沖表示一端處于邊界或者被對方棋子所堵的情況，活表示兩端都有空位，如果兩端都沒有空位，則不可能形成五子相連，沒有意義，不計(jì)分?jǐn)?shù)。//活2分?jǐn)?shù)const int HTHREE=100。所以僅需要掃描棋局中二子相連，三子相連，四子相連，五子相連的數(shù)量。第7章 計(jì)算機(jī)智能設(shè)計(jì)機(jī)器智能設(shè)計(jì)需要解決的關(guān)鍵問題是估值和搜索技術(shù)。 人類玩家的Think操作玩家通過Think操作得出下子位置，人類下棋通過鼠標(biāo)，當(dāng)鼠標(biāo)按下，CFiveChessDlg中的OnLButtonDown被執(zhí)行，記錄下鼠標(biāo)是否按下bMouse，以及按下位置（mx,my）。棋盤繪制好后繪制棋子，掃描全局對象chessBoard中棋盤數(shù)據(jù)board[15][15]，繪制出所有棋子。文件擴(kuò)展名為fsv，用戶指定文件名按確定后，先寫入4字節(jié)的文件標(biāo)識(‘f’,’i’,’v’,’e’),然后寫入棋盤數(shù)據(jù)(board[15][15])，再寫入下子位置歷史棧，棧因?yàn)轫樞蚴窍喾吹?，為以后載入方便，這里又建立了一個(gè)棧，將數(shù)據(jù)倒置后再保存。為兩個(gè)下拉列表框里面有“人”和“計(jì)算機(jī)”兩項(xiàng)，默認(rèn)是“人”這一項(xiàng)，用戶重新選擇玩家類型時(shí)，則改變玩家類型，如果是計(jì)算機(jī)玩家，則彈出設(shè)置計(jì)算機(jī)等級對話框（用CLevelDlg對話框類表示），確認(rèn)后創(chuàng)建相應(yīng)等級的計(jì)算機(jī)玩家。 if(side){//游戲結(jié)束 顯示游戲結(jié)束信息 } } return CDialog::ContinueModal()。 游戲循環(huán)游戲進(jìn)程的調(diào)度在游戲循環(huán)中完成，在windows程序中，最適合的位置就是消息循環(huán)處理中。如果合法，則更新棋盤數(shù)據(jù)，畫該棋子，如果該方勝利，則顯示勝利信息并開始新局，否則把當(dāng)前玩家設(shè)為對方。 控制流程由于在Windows環(huán)境下程序采用事件驅(qū)動，因此，整個(gè)程序采用事件驅(qū)動機(jī)制，而這一控制最好放在消息循環(huán)中。//根據(jù)傳入的棋盤信息產(chǎn)生一種走法 cPlayer(char side){ Side=side。（1）屬性：Side，表示該玩家所持什么棋子。bool SaveBoard(char filename[])。Int IsGameOver(void)。//游戲是否結(jié)束，返回1表示黑方勝利，返回2表示白方勝利，返回3表示和局，0表示游戲仍然進(jìn)行。SaveBoard(char filename[])，把當(dāng)前的棋局保存到filename指定的文件中。pBlackPlayer,pWhitePlayer,pCurrentPlayer：分別表示持黑子的玩家和持白子的玩家以及指向當(dāng)前應(yīng)下子玩家的指針。是否結(jié)束：該操作判斷當(dāng)前游戲是否結(jié)束，以及哪一方結(jié)束。 動態(tài)模型棋盤的動態(tài)模型持白子玩家下子持黑子玩家下子開始黑子玩家勝利do:顯示勝利信息開始新局持黑子玩家下子等待持黑子玩家下子do:接收下子持黑子玩家下子持白子玩家下子白子玩家勝利do:顯示勝利信息開始新局持白子玩家下子和局do:顯示和局信息開始新局等待持白子玩家下子do:接收下子 動態(tài)模型圖167。其屬性如下：（1）Side，表示該玩家所持什么棋子。（2） BlackPlayer，表示持黑棋的玩家。 是否退出對話框選擇“是”按鈕則退出，“否”繼續(xù)下。 系統(tǒng)平臺要求編程語言：C++操作系統(tǒng)：windows開發(fā)工具：microsoft Visual C++5畢業(yè)設(shè)計(jì)論文——博弈算法的設(shè)計(jì)及其實(shí)現(xiàn)第3章 人機(jī)界面設(shè)計(jì) 五子棋程序界面，在左邊的為1515的棋盤，右邊的“黑子”和“白子”下接列表框設(shè)定持黑子和白子的玩家類型，各有三項(xiàng)，分別是“人”，“計(jì)算機(jī)”，“當(dāng)選擇“人”后，就可以用鼠標(biāo)在棋盤下放該類型的棋子，當(dāng)為“計(jì)算機(jī)”，則由計(jì)算機(jī)自動產(chǎn)生走法并在棋盤上下該種類型的棋子，并且會彈出一個(gè)選擇智力級別的對話框。能保存棋局狀態(tài)，同時(shí)也能讀入上一次保存的棋局狀態(tài)，并且能夠接著上一次繼續(xù)下棋。 使用范圍要求五子棋規(guī)則簡單，男女老幼都可以玩，不但能讓人們在對弈過程中得到娛樂，而且還能開發(fā)智力。167。五子棋的規(guī)則很簡單，如果不考慮禁手，任意空位都可以放棋子，只要一方有五個(gè)棋子連成一線，則判勝。它所包含的內(nèi)容有：知識表示、自動推理和搜索方法、機(jī)器學(xué)習(xí)和知識獲取、知識處理系統(tǒng)、自然語言理解、計(jì)算機(jī)視覺、智能機(jī)器人、自動程序設(shè)計(jì)等方面。 人工智能提到人工智能，可能最著名的便是1997年超級計(jì)算機(jī)“深藍(lán)”戰(zhàn)勝國際象棋冠軍卡斯帕羅夫的事，可以說“深藍(lán)”的獲勝是人工智能影響力的一個(gè)里程碑。 有限范圍限定 33167。 Alphabeta算法 24167。 界面設(shè)計(jì)及事件處理 17167。 類設(shè)計(jì) 14167。 系統(tǒng)平臺要