【正文】 5 在編譯時(shí)支持OpenMP 的語(yǔ)法了；而在編寫(xiě)使用OpenMP 的程序時(shí)，則需要先include OpenMP的頭文件：。167。另外，我還要感謝在這幾年來(lái)對(duì)我有所教導(dǎo)的老師，他們孜孜不倦的教誨不但讓我學(xué)到了很多知識(shí)，而且讓我掌握了學(xué)習(xí)的方法，更教會(huì)了我做人處事的道理，在此表示感謝。從表（）可以看出，極小窗口算法PVS效率是比AlphaBeta效率要高的，因?yàn)樗婚_(kāi)始就用很小的窗口搜索，但加入預(yù)估值排序后PVS算法比AlphaBeta算法效率要低一些了，大概是因?yàn)轭A(yù)估值的關(guān)系，一開(kāi)始搜索到了比較好的節(jié)點(diǎn)，減小了AlphaBeta的窗口，剪枝效率已經(jīng)很高，而PVS算法畢竟要多搜索一次，故反而不如預(yù)估值排序的AlphaBeta算法。167。x15。//64位校驗(yàn)生成隨機(jī)數(shù) unsigned long hash32[3][15][15]。預(yù)估值排序的PVS實(shí)現(xiàn)在CSortedPVS類(lèi)中。if(valuealpha) value=generate(cboard,WHITE,depth1,pe,value,beta)。 if(valuebeta){ beta=value。 int cboard[15][15]。 board[y][x]=NONE。 else best=min(value,best)。 =。計(jì)算值的過(guò)程實(shí)際上就是統(tǒng)計(jì)連續(xù)相同二子，三子，四子，五子的過(guò)程，依次按左下方，下方，右下方，右方掃描棋盤(pán)上每個(gè)棋子連續(xù)相連數(shù)目，然后計(jì)算分?jǐn)?shù)，最后加上每個(gè)棋子所在位置的分?jǐn)?shù)。167。 設(shè)置計(jì)算機(jī)智力對(duì)話框 悔棋、新局、保存、載入、退出按鈕在棋盤(pán)類(lèi)（CChessBoard）中用一個(gè)棧來(lái)保存下棋歷史，該棧中數(shù)據(jù)元素為POINT類(lèi)型，悔棋時(shí)進(jìn)行出棧操作，每次出棧兩個(gè)棋子位置，將它們對(duì)應(yīng)棋盤(pán)坐標(biāo)設(shè)置為無(wú)子(NONE)。在界面建立時(shí)把設(shè)置玩家對(duì)象的列表框都選擇為人玩家對(duì)象，并建立人玩家對(duì)象，并調(diào)用該函數(shù)在改變?cè)O(shè)置玩家對(duì)象的下拉列表框時(shí)調(diào)用，用來(lái)設(shè)置好玩家對(duì)象。//判斷游戲是否已經(jīng)結(jié)束，沒(méi)有則返回0，否則返回哪方勝利 void NewRound(void)。34第5章 面向?qū)ο笤O(shè)計(jì)167。8第4章 面向?qū)ο蠓治?67。 Visual C++ 本次的開(kāi)發(fā)工具為Microsoft visual c++ 2005，它是微軟公司推出的win32的開(kāi)發(fā)工具，本次實(shí)現(xiàn)之所以選用Visual C++作為開(kāi)發(fā)工具，除因個(gè)人使用習(xí)慣外，主要是它生成的代碼高效，具有靈活方便的類(lèi)管理，以及界面設(shè)計(jì)的可視化特點(diǎn)。 多核優(yōu)化 33第8章 總結(jié)結(jié)論 35167。 對(duì)象設(shè)計(jì) 11167。 動(dòng)態(tài)模型 12167。 各算法效率對(duì)比 35167。另外，在Visual C++ 2005中引入了OpenMp的支持，OpenMp為快速開(kāi)發(fā)具有多核優(yōu)化的程序提供簡(jiǎn)單方便的支持，使得博弈程序更加高效。 對(duì)象設(shè)計(jì)根據(jù)需求分析中的要求，初步的對(duì)象設(shè)計(jì)如下：11對(duì)手下棋棋盤(pán)玩家12人玩家計(jì)算機(jī)玩家各對(duì)象說(shuō)明如下：棋盤(pán)對(duì)象：表示1515的五子棋棋盤(pán)，表示上面放了哪些子以及它們的位置，或者是每一個(gè)位置放了什么子。 類(lèi)設(shè)計(jì) 由《五子棋程序面向?qū)ο蠓治觥房傻贸鲈摮绦蛞还灿兴膫€(gè)類(lèi)。public: bool PutChess(int x,int y,char side)。改變玩家對(duì)象時(shí)所進(jìn)行的操作，用戶在改變玩家對(duì)象的下拉列表框中選擇了另一種玩家對(duì)象時(shí)，系統(tǒng)會(huì)調(diào)用相應(yīng)的事件處理函數(shù)，在該函數(shù)中刪除原有的玩家對(duì)象，并創(chuàng)建一個(gè)新的玩家對(duì)象。新局操作將棋盤(pán)所有位置設(shè)置為無(wú)子(NONE)，清空下子歷史棧，將當(dāng)前玩家設(shè)置為黑方。 棋局估值人們?cè)谙缕暹^(guò)程中，走哪一步棋好，哪一步棋壞，有一定的評(píng)判標(biāo)準(zhǔn)，這個(gè)評(píng)判標(biāo)準(zhǔn)就是估值?？梢钥闯?，上面的效率并不高，實(shí)際上，父棋局的值估計(jì)好后，其子棋局與父棋局僅多一個(gè)棋子，所以其它棋子不需要再重復(fù)計(jì)算，只需要計(jì)算由于這一棋子所帶來(lái)的分?jǐn)?shù)變化即可。=y。 } return best。 if(valuealpha) alpha=value。 memcpy(cboard,board,sizeof(cboard))。 =x。將白方處的代碼：int value=generate(board,BLACK,depth1,pe,alpha,beta)。二、歷史啟發(fā)歷史啟發(fā)簡(jiǎn)單地說(shuō)就是根據(jù)部分已經(jīng)搜索的結(jié)果來(lái)調(diào)整將要搜索的節(jié)點(diǎn)順序。//32位hash值生成隨機(jī)數(shù)public: CBoardHash(int size)。x++){ key^=hash32[board[y][x]][y][x]。 多核優(yōu)化現(xiàn)在，計(jì)算機(jī)已經(jīng)具有一定程度的智能了，但該程序效率仍然不高，當(dāng)深度為3時(shí)，現(xiàn)在的計(jì)算機(jī)可能仍然要花費(fèi)以分為計(jì)時(shí)間，第一步用時(shí)達(dá)85秒，現(xiàn)代的計(jì)算機(jī)已經(jīng)向多核發(fā)展，4核已經(jīng)很普及，所以，可以考慮讓每個(gè)cpu核心都能能發(fā)揮作用。當(dāng)引入預(yù)估值排序后，由于一開(kāi)始就搜索了比較好的走法，所以AlphaBeta的截枝效率大大地提高，加入hash表后效率基本差不多，但第2步卻花了較長(zhǎng)時(shí)間，再看后面的幾步的時(shí)間差，基本上是差不多的。 綜上所述，計(jì)算機(jī)博弈中的搜索算法是以AlphaBeta截枝為基礎(chǔ)的，其截枝效率的高低取決于AlphaBeta表示的窗口大小，窗口越小，截枝效率越高，其后的各種算法都是圍繞減小AlphaBeta的這個(gè)窗口來(lái)進(jìn)行改進(jìn)的。一、 OpenMP簡(jiǎn)介OpenMP是由OpenMP Architecture Review Board牽頭提出的，并已被廣泛接受的，用于共享內(nèi)存并行系統(tǒng)的多線程程序設(shè)計(jì)的一套指導(dǎo)性注釋(Compiler Directive)。}該函數(shù)根據(jù)當(dāng)前棋局棋盤(pán)上各位置的棋子狀態(tài)使用hash32數(shù)組中的不同隨機(jī)數(shù)進(jìn)行異或運(yùn)算，生成hash碼，從而保證不同的棋局hash碼盡可能不同。 unsigned long hashCode(int board[][15])。hash表由于五子棋的子節(jié)點(diǎn)很多（每層最多15*15個(gè)），不可能保存所有的搜索節(jié)點(diǎn)，故只能保存部分節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)很多時(shí)，當(dāng)前搜索的節(jié)點(diǎn)是否被搜索過(guò)，如何快速地取得該節(jié)點(diǎn)，這個(gè)時(shí)間最好是常量。if(valuealpha) value=generate(cboard,WHITE,depth1,pe,alpha,value)。 } } } return pos。 int value=generate(cboard,WHITE,depth1,pE,alpha,beta)。//返回最大值 }else{ for(each possible move){ if(alpha=beta) return beta。它調(diào)用generate函數(shù)計(jì)算得出子節(jié)點(diǎn)的值，然后選擇一個(gè)最佳子節(jié)點(diǎn)的坐標(biāo)返回，作為下子的位置。}有了這個(gè)算法，計(jì)算機(jī)勉強(qiáng)有點(diǎn)智能，可以下一下棋了，但它還是比較笨，只管眼前這一步，而不能看到兩步，三步，或者以后更多步的結(jié)果。其中pvalue是父棋局的估值，(x,y)指出了下子的位置167。所以僅需要掃描棋局中二子相連，三子相連，四子相連，五子相連的數(shù)量。文件擴(kuò)展名為fsv，用戶指定文件名按確定后，先寫(xiě)入4字節(jié)的文件標(biāo)識(shí)(‘f’,’i’,’v’,’e’),然后寫(xiě)入棋盤(pán)數(shù)據(jù)(board[15][15])，再寫(xiě)入下子位置歷史棧，棧因?yàn)轫樞蚴窍喾吹?，為以后載入方便，這里又建立了一個(gè)棧，將數(shù)據(jù)倒置后再保存。如果合法，則更新棋盤(pán)數(shù)據(jù)，畫(huà)該棋子，如果該方勝利，則顯示勝利信息并開(kāi)始新局，否則把當(dāng)前玩家設(shè)為對(duì)方。bool SaveBoard(char filename[])。pBlackPlayer,pWhitePlayer,pCurrentPlayer：分別表示持黑子的玩家和持白子的玩家以及指向當(dāng)前應(yīng)下子玩家的指針。（2） BlackPlayer，表示持黑棋的玩家。 使用范圍要求五子棋規(guī)則簡(jiǎn)單，男女老幼都可以玩，不但能讓人們?cè)趯?duì)弈過(guò)程中得到娛樂(lè)，而且還能開(kāi)發(fā)智力。 人工智能提到人工智能，可能最著名的便是1997年超級(jí)計(jì)算機(jī)“深藍(lán)”戰(zhàn)勝?lài)?guó)際象棋冠軍卡斯帕羅夫的事，可以說(shuō)“深藍(lán)”的獲勝是人工智能影響力的一個(gè)里程碑。 類(lèi)設(shè)計(jì) 14167。 功能要求 7167。 預(yù)估排序和歷史啟發(fā) 30167。它在博弈技術(shù)中也是很重要的，從某種意義上來(lái)說(shuō)，搜索也是為了估值，或者說(shuō)對(duì)估值作修正。如果退出程序，此時(shí)顯示“確認(rèn)退出”對(duì)話框。接收下子：該操作由棋盤(pán)對(duì)象負(fù)責(zé)，它接收玩家發(fā)來(lái)的下子位置，同時(shí)判斷是否合法，不合法則不作任何操作，合法則改變棋盤(pán)狀態(tài)，以及把當(dāng)前玩家更改為另一方。CPlayer *pBlackPlayer,*pWhitePlayer,*pCurrentPlayer。167。如下圖所示： 五子棋程序界面 黑方，白方下拉列表框黑白下拉列表框在CFiveChessDlg類(lèi)中類(lèi)型為CComboBox類(lèi)的成員對(duì)象， 名稱(chēng)分別為m_boBlack、m_boWhite。一直在正確位置按下了鼠標(biāo)為止，然后清除掉bMouse標(biāo)志（表示我已經(jīng)下過(guò)棋子了，需要重新接收鼠標(biāo)按下）。其定義如下：int value(int board[][15],int side)。 board[y][x]=NONE。 board[y][x]=NONE。 board[y][x]=side。int x=i%15。 c