【正文】 同時(shí)，通過(guò)自己平時(shí)下五 子棋不斷總結(jié)經(jīng)驗(yàn)教訓(xùn)，希望在下一版本中能寫(xiě)出更合理、更快速的估值函數(shù)來(lái)。通過(guò)這次畢業(yè)設(shè)計(jì)，全面回顧了大學(xué)四年里學(xué) 習(xí)的核心專業(yè)知識(shí)，特別是對(duì)VC 開(kāi)發(fā)工具更加熟悉了；對(duì) C++語(yǔ)言和面向?qū)ο缶幊逃辛烁由羁痰睦斫?；?duì)計(jì)算機(jī)博弈技術(shù)也略知一二。服務(wù)用一個(gè)臨時(shí)的 CFiveSocket 對(duì)象和請(qǐng)求連接者建立暫時(shí)連接，并發(fā)送 FM_SERVER_BUSY 給連接者，然后馬上斷開(kāi)連接。 對(duì)方姓名消息 —— FM_NAME_INFO 用來(lái)獲取對(duì)方玩家的姓名， szText 表示對(duì)方的姓名， stonePos 成員無(wú)效。 編輯框聊天消息 —— FM_EDIT_CHAT 表明對(duì)方在組合框的編輯框輸入一條聊天信息并發(fā)送， szText 表示對(duì)方的輸入的信息內(nèi)容， stonePos 成員無(wú)效。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 26 頁(yè) 圖 黑方認(rèn)輸 圖 白方認(rèn)輸 請(qǐng)求再玩一局消息 —— FM_REQUEST_REPLAY 表明對(duì)方希望開(kāi)始一局新的棋局，除 uID 成員外其余成員皆無(wú)效。接到這個(gè)消息后，整個(gè)界面將恢復(fù)發(fā)送和棋請(qǐng)求前的狀態(tài)。 圖 請(qǐng)求和棋 同意和棋消息 —— FM_AGREE_DRAW 表明對(duì)方接受了玩家的和棋請(qǐng)求（如圖 所示），除 uID 成員外其余成員皆無(wú)效。接到這個(gè)消息后，整個(gè)界面將恢復(fù)發(fā)送悔棋請(qǐng)求前的狀態(tài)。另外，在發(fā)送這個(gè)消息之后，主界面上的某些元素將暫時(shí)不響應(yīng)用戶的操作。 落子消息 —— FM_PUTSTONE 表明對(duì)方落下了一個(gè)棋子，其中 uID、 、 ， szText成員無(wú)效。 // 落子坐標(biāo) STONEPOS stonePos。 智能 五子棋程序也模仿 Windows 系統(tǒng)實(shí)現(xiàn)了自己的 消息機(jī)制，主要為網(wǎng)絡(luò)對(duì)弈服務(wù)，以響應(yīng)多種多樣的網(wǎng)絡(luò)消息（ 如 圖 ）。 最后提一下程序的一個(gè)重要菜單 (如圖 )。它能快速地隱藏和顯示程序主界面。 圖 播放列表對(duì)話框 設(shè)置對(duì)話框 現(xiàn)在每一款 軟 件都有“設(shè)置”對(duì)話框?！?+”之下的按鈕用來(lái)保存 /打開(kāi)播放列表文件 （ FPL格式）。這個(gè)播放列表可以像 那樣自動(dòng)隱藏到屏幕上端（如果它被拖放到屏幕邊緣）。在設(shè)計(jì)上和前兩個(gè)頁(yè)面在功能上有許多相似性：如支持棋譜文件（ DAN 格式）的拖放；在棋譜分析模式下，輸入框也會(huì)檢查用戶輸入數(shù)字的合法性，并彈出圖 。該頁(yè)面支持拖放功能，用戶可以將一個(gè)或多個(gè)音樂(lè)文件（格式為 MP WAV 或 WMV）直接拖放到頁(yè)面上進(jìn)行 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 21 頁(yè) 播放。其中長(zhǎng)度信息欄（格式為 MM:SS） 隨著歌曲的播放進(jìn)度而實(shí)時(shí)更新（圖上的 4:29 表明這首歌長(zhǎng)度為 4 分 29 秒，而 4:21是說(shuō)剩余時(shí)間為 4分 21秒）。 這種汽球提示不會(huì)打擾用戶的任何操作，而且會(huì)自動(dòng)隱藏。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 20 頁(yè) 圖 聊天頁(yè)面 圖 音樂(lè)頁(yè)面 圖 單機(jī)頁(yè)面 (1) 聊天頁(yè)面 在程序啟動(dòng)時(shí)它 是 被 禁用的 ，如果用戶選擇聯(lián)機(jī)對(duì)戰(zhàn)，則在雙方連接成功后被啟用 。 最后棋盤(pán)邊上的坐標(biāo)數(shù)值（ 11 AO）和棋子上在數(shù)值 [1， 225]也是在 OnPaint 函數(shù)中畫(huà)出來(lái)的。程序中正是用雙緩沖技術(shù)解決閃爍問(wèn)題的 。包括播放、暫停、停止、上一首、下一首等功能的實(shí)現(xiàn) [17]。 （ 5） CTabMusicDlg（音樂(lè)播放器頁(yè)面類）。如發(fā)送及顯示聊天內(nèi)容（包括文字聊天消息和語(yǔ)音聊天消息）、對(duì)和棋，悔棋，認(rèn)輸響應(yīng)后進(jìn)行善后處理等等。 （ 2） CChessBoard（棋盤(pán)類） 棋盤(pán)類自然是處理用戶與棋盤(pán)的交互消息。 主要類及其關(guān)系 用戶界面設(shè)計(jì)的 6 個(gè)核心類 （ 1） CFiveDlg（主對(duì)話框類） 智能 五子棋啟動(dòng)過(guò)程絕大多數(shù)的初始化工作在該類的 OnInitDialog 函數(shù)中完成，包括棋盤(pán)加載、主界面元素（比如游戲雙方姓名顯示）初始化等。 從而避免用戶下次重新設(shè)定而浪費(fèi)時(shí)間。 （ 2）程序可以自動(dòng)隱藏，還能方便、快速地呼出。在 Windows大行其道的今天，任何一款成功的商業(yè)軟件都在界面設(shè)計(jì)上 都 下足了功夫，因?yàn)檫@是吸引用戶興趣的第一道門(mén)檻。當(dāng)輪到白棋走時(shí)，估值函數(shù)返回值為：白值價(jià)值 黑棋價(jià)值，而輪到黑棋走時(shí)，返回：黑棋價(jià)值 白棋價(jià)值。如果輪到某一方落子，而此時(shí)某一方出現(xiàn)多 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 16 頁(yè) 于 1個(gè)的活三棋型，返回極值。兩個(gè)沖四看成一個(gè)活四。最基本的棋型優(yōu)先順序?yàn)椋何暹B 活四 沖四 活三 眠三 活二 眠二。同 時(shí)在實(shí)現(xiàn)這個(gè)數(shù)學(xué)模型的過(guò)程中，必須考慮運(yùn)算的耗費(fèi)，因?yàn)檫\(yùn)算量太大的估值計(jì)算，往往影響了整個(gè)搜索的速度，降低了搜索的深度，而運(yùn)算量少的一些近似估值，通過(guò)搜索深度的增加，仍能大大彌補(bǔ)近似估值所丟失的不準(zhǔn)確性。 // 返回最佳值 } 估值函數(shù) 在搜索 之 外，估值函數(shù)是最重要的部分，因?yàn)閷?duì)實(shí)際局面的評(píng)價(jià)好壞，影響著今后局勢(shì)發(fā)展的趨勢(shì)。m_MoveList[depth][bestmove], depth )。m_MoveList[depth][i], depth )。 // 精確值 a = t。m_MoveList[depth][i], CurPosition )。 /* 重新搜索 */ eval_is_exact = 1。amp。 // 產(chǎn)生子節(jié)點(diǎn)的哈希值 Hash_MakeMove( amp。 i count。 a = alpha。 ++i ) { // 取所有走法的歷史得分 m_MoveList[depth][i].score = GetHistoryScore( amp。 if( depth == m_nMaxDepth ) { // 在根節(jié)點(diǎn)設(shè)定進(jìn)度條 ( 0, count )。 // 命中 ,直接返回查得數(shù)據(jù) if( depth = 0 ) /* 葉結(jié)點(diǎn) */ { score = m_pEvalEvaluate( CurPosition, 0 )。 if( depth 0 ) { i = IsGameOver( CurPosition, depth )。 在搜索的過(guò)程中，每當(dāng)找到一個(gè)好的走法，就將與該走法相對(duì)應(yīng)的歷史得分作一個(gè)增量，一個(gè)多次被搜索并確認(rèn)為好的走法的歷史紀(jì)錄 就會(huì)較高，當(dāng)搜索中間 結(jié)點(diǎn)時(shí)，將走法根據(jù)其歷史得分排列順序，以獲得較佳的排列順序。如何調(diào)整待展開(kāi)的走法排列的順序，是提高搜索效率的關(guān)鍵。 歷史啟發(fā)（ History Heuristic） 在介紹 NegaScout 算法中曾經(jīng)提到， AlphaBeta 搜索的剪枝效率，幾乎完全取決于節(jié)點(diǎn)的排列順序（ Move Ordering） 。一般只有 Exact 類型，才可作為當(dāng)前結(jié)點(diǎn)的準(zhǔn)確值存入 Transposition Talbe，但 Fail High(=Beta)、 Fail Low(=Alpha)所對(duì)應(yīng)的邊界值仍可幫助我們作進(jìn)一步的剪枝，所以我們?cè)?Transposition Table用字段 entry_type表示 類型，其中 Exact類型為準(zhǔn)確值，其余的是表示值的范圍 [12]。 Transposition Table 是一種空間換取時(shí)間的思想。在程序根部，作一次加總操作求出根節(jié)點(diǎn)的哈希值，當(dāng)搜索一個(gè)新 結(jié) 點(diǎn)時(shí)只要將該位置對(duì)應(yīng)的隨機(jī)數(shù) 和根 結(jié) 點(diǎn)哈希值相加即可。 Zobrist Hash 方法：在程序啟動(dòng) 或棋局開(kāi)始 的時(shí)候，建立一個(gè)多維數(shù)組（在五子棋中是三維 ） Z[pieceType][boardWidth][boardHeight]， 其中 pieceType 是棋子種類，五子棋中為黑、白兩種； boardWidth 為棋盤(pán)寬度，五子棋為 15； boardHeight為棋盤(pán)高度，五子棋為 15。 置換表（ Transposition Table） 在一棵搜索樹(shù)中，不 少結(jié)點(diǎn)之間雖然是經(jīng)過(guò)不同的路徑到達(dá)的，但其狀態(tài)是完全一致的。 // (Beta)剪枝 b = a + 1。amp。amp。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 11 頁(yè) for( i = 1。 生成局面 p的后繼局面 p1, p2, ..., pw。雖然當(dāng)無(wú)法 Beta Cutoff需要重新搜索的時(shí)候，實(shí)際比原來(lái)多出了 Minimal Window [Beta1,Beta]的搜索過(guò)程，但是由于 Minimal Window內(nèi)的子樹(shù)產(chǎn)生剪枝的概率比較大，所以實(shí)際增加的搜索結(jié)點(diǎn)數(shù)相對(duì)比較少，同時(shí)當(dāng)Move Ordering比較好的時(shí)候，大部分結(jié)點(diǎn)能夠產(chǎn)生 Beta剪枝的概率相當(dāng)大，這樣我們就可以避免更繁重的全 AlphaBeta窗口搜索。同理，可以分析出對(duì) C的右子樹(shù)進(jìn)行 類似的 Alpha剪枝。因 6 6 7 4 極小值結(jié)點(diǎn) A (∞ , ∞ ) (∞ , 6) B C 5 3 7 1 4 2 6 6 4 F G E D L (∞ , ∞ ) (∞ ,∞ ) (∞ , 6) (∞ , 6) (∞ , 6) Beta 剪枝 (6, ∞ ) Alpha 剪枝 (∞ , 6) (∞ , 6) (∞ , 6) 極大值結(jié)點(diǎn) 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 10 頁(yè) 此 B的右子 結(jié) 點(diǎn) E的搜索窗口為（ ∞ ,6）。 // (Beta)剪枝 } return ( a )。 i = w。 生 成局面 p的后繼局面 p1, p2, ..., pw。 AlphaBeta 算法通過(guò)下界（ Alpha）上界（ Beta）對(duì)搜索樹(shù)值的最終范圍進(jìn)行了劃定，當(dāng)某些子樹(shù)其值被證明會(huì)在上述界限之外，無(wú)法影響整顆樹(shù)的值時(shí)，便可進(jìn)行剪枝 [5]。 // 使用位置價(jià)值表評(píng)估當(dāng)前走法的價(jià)值 m_MoveList[nPly][++m_nMoveCount].score = g_arrPosValue[i][j]。 ++i ) 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 8 頁(yè) { for( j = 0。 // 用以產(chǎn)生局面 position 中所有可能 的走法 // position是包含所有棋子位置信息的二維數(shù)組 // nPly指明當(dāng)前搜索的層數(shù)，每層將走法存在不同的位置，以免覆蓋 // nSide指明產(chǎn)生哪一方的走法， WHITE為白方， BLACK為黑方 int CreatePossibleMove( BYTE position[15][15], int nPly, int nSide ) { int i, j。 // 棋子位置 int score。 // x, y 是棋盤(pán)坐標(biāo)值，取值范圍 [0,14] } STONEPOS。系統(tǒng)特別重視出錯(cuò)處理，能夠?qū)Α靶涡紊钡腻e(cuò)誤 作出對(duì)應(yīng)的提示，避免在錯(cuò)誤發(fā)生以后，用戶不知所措，其中絕大多數(shù)錯(cuò)誤以ToolTip 的形式 呈現(xiàn) 給用戶。 系統(tǒng)交互性 如摘要中提到的，本程序非常注重界面的友好性和操作的簡(jiǎn)單性。網(wǎng)絡(luò)通信基于客戶機(jī) /服務(wù)器（ Client/Server）模式，但它的工作方式卻更類似于 P2P[16]。 界面生成 涉及 MFC 控件 14 種（ Button、 Check Box、 ComboBox、 Edit Control、 Group Box、Radio Button、 Static Text、 Picture Control、 Slider Control、 Spin Control、Progress Control、 Hot Key、 Tree Control、 Tab Control）；系統(tǒng)托盤(pán)（用戶可控制其顯示和隱藏） [22]；拖放 功能 （ Drag and Drop） [20]；老板鍵 功能 （用戶可自行設(shè)定）；輸贏平 和 下子聲音提示、聊天聲音發(fā)送及整點(diǎn)報(bào)時(shí)；自動(dòng)窗口閃爍；讀寫(xiě)注冊(cè)表；簡(jiǎn)單多線程搜索音樂(lè)等等。 系統(tǒng)功能劃分 系統(tǒng)主體分為三大功能模塊：界面模塊、網(wǎng)絡(luò) 連接 模塊 及單機(jī) AI 算法模塊。 第六章則是全文總結(jié)