【正文】 序由 37 個類、 6 個結(jié)構(gòu)體、 12 個全局函數(shù)以及若干其它變量、枚舉類型、宏等組成。其中核心類 11 個，包括用于實(shí)現(xiàn)單機(jī) AI 算法的 4 個類： CEvaluation（估值核心）、 CHistoryHeuristic（歷史啟發(fā)增強(qiáng)）、 CTranspositionTable（置換表增強(qiáng)）和 CNegaScout_TT_HH（ 核心的 NegaScout 算法類）；用于實(shí)現(xiàn)網(wǎng)絡(luò)通信的CFiveSocket 類和用于用戶界面交互的 6 個類： CChessBoard（棋盤類）、 CFiveDlg（主對話框類）、 CMusic 類（音樂 類 ）、 CTabChatDlg（聊天頁面類）、 CTabHCGameDlg（單機(jī)游戲頁面類）和 CTabMusicDlg（迷你音樂播放器頁面類）。 系統(tǒng)功能劃分 系統(tǒng)主體分為三大功能模塊：界面模塊、網(wǎng)絡(luò) 連接 模塊 及單機(jī) AI 算法模塊。邏輯上，網(wǎng)絡(luò)連接模塊與單機(jī) AI 算法模塊相互獨(dú)立，而界面模塊則時時 負(fù)責(zé) 與這兩大模塊交互，接受用戶所有的消息以及 對 界面進(jìn)行相應(yīng)輸出和更新。 系統(tǒng)總體邏輯流程 關(guān)鍵技術(shù)點(diǎn) 通過對 系統(tǒng) 功能的分析和設(shè)計，在實(shí)現(xiàn)過程中需要解決如下幾個關(guān)鍵技術(shù)點(diǎn)： 系統(tǒng)啟動運(yùn)行 用戶選擇游戲模式 單機(jī)版 網(wǎng)絡(luò)版 看棋譜 播放音樂 保存棋譜 兩人聊天 保存棋譜 播放音樂 游戲 結(jié)束 游戲結(jié)束 圖 系統(tǒng)流程圖 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 6 頁 AI算法 包括估值核心和 搜索算法 。其中搜索算法涉及 技術(shù) 有 ： AlphaBeta 剪枝、NegaScout 算法、歷史啟發(fā)（ History Heuristic）、置換表（ Transposition Talbe）和 Zobrist 哈希方法等。 界面生成 涉及 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)托盤（用戶可控制其顯示和隱藏） [22]；拖放 功能 （ Drag and Drop） [20]；老板鍵 功能 （用戶可自行設(shè)定）；輸贏平 和 下子聲音提示、聊天聲音發(fā)送及整點(diǎn)報時；自動窗口閃爍；讀寫注冊表；簡單多線程搜索音樂等等。 網(wǎng)絡(luò) 連接 使用的 WinSock 版本號為 。程序中使用 CFiveSocket 類負(fù)責(zé)收發(fā)網(wǎng)絡(luò)消息。該類派生自 MFC的 CAsyncSocket類。網(wǎng)絡(luò)通信基于客戶機(jī) /服務(wù)器（ Client/Server）模式，但它的工作方式卻更類似于 P2P[16]。因?yàn)榭蛻舳嗽谂c服務(wù)器斷開后，自己也可以選擇做服務(wù)器，而原來的服務(wù)端也可以 迅速轉(zhuǎn)換角色，反過來做客戶端。所以，在邏輯上可以說這種工作方式是類似于 P2P 的。因?yàn)橥ㄐ烹p方既可以做服務(wù)端也可以做客戶端。 系統(tǒng)交互性 如摘要中提到的，本程序非常注重界面的友好性和操作的簡單性。如老板鍵功能，可以使程序“招之即來，揮之即去”。棋盤右鍵快捷菜單可以使用戶迅速地對相應(yīng)功能進(jìn)行設(shè)置。棋譜的“靜默保存”模式，省去了用戶在每局棋結(jié)束之后，必須：點(diǎn)擊保存按鈕 設(shè)定文件名 點(diǎn)擊“確定”按鈕，這一系列煩瑣工作，程序在后臺靜靜地為用戶處理好了一切。系統(tǒng)特別重視出錯處理，能夠?qū)Α靶涡紊钡腻e誤 作出對應(yīng)的提示，避免在錯誤發(fā)生以后，用戶不知所措，其中絕大多數(shù)錯誤以ToolTip 的形式 呈現(xiàn) 給用戶。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 7 頁 3 人機(jī)對弈中 AI的實(shí)現(xiàn) 數(shù)據(jù) 結(jié)構(gòu) 單機(jī) AI 算法中用到的核心數(shù)據(jù) 結(jié)構(gòu) 總結(jié)為如下幾個 ： （ 1）程序包括一個 記錄 棋盤數(shù)據(jù)二維數(shù)組 BYTE m_FiveBoard[15][15]和一個走步記錄棧 std::vectorSTONEPOS m_vecStepList。 m_FiveBoard 數(shù)組中存儲當(dāng)前棋盤格子落子顏色，而 m_vecStepList 存儲走步 STONEPOS 值，它主要用于支持悔棋功能。 STONEPOS 結(jié)構(gòu)體定義如下： typedef struct _tagStonePosition { BYTE x, y。 // x, y 是棋盤坐標(biāo)值，取值范圍 [0,14] } STONEPOS。 （ 2）用數(shù)字“ 0”和“ 1”來表示不同顏色的棋子，其中黑色棋子用“ 0”表示，白色棋子用“ 1”表示。沒有棋子的格子用 0xFF 表示。這三個數(shù)值都有相應(yīng)的宏，以避免出差錯： define BLACK 0 define WHITE 1 define NOSTONE 0xFF （ 3）搜索算法還用到了一個重要的走法結(jié)構(gòu)體 STONEMOVE typedef struct _tagStoneMove { STONEPOS stonePos。 // 棋子位置 int score。 // 走法得分 } STONEMOVE。 走法產(chǎn)生 相對于象棋等游戲來說，五子棋的走法產(chǎn)生規(guī)則是十分簡單的：棋盤上所有空白的位置都是合法的落子點(diǎn)（本論文并沒有討論禁手規(guī)則，詳見第一章 節(jié) 規(guī)則說明）。搜索類 CNegaScout_TT_HH的 CreatePossibleMove函數(shù)用來完成走法產(chǎn)生 [4]。 // 用以產(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。 m_nMoveCount = 0。 for( i = 0。 i GRID_NUM。 ++i ) 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 8 頁 { for( j = 0。 j GRID_NUM。 ++j ) { if( position[i][j] == NOSTONE ) { m_MoveList[nPly][m_nMoveCount]. = j。 m_MoveList[nPly][m_nMoveCount]. = i。 // 使用位置價值表評估當(dāng)前走法的價值 m_MoveList[nPly][++m_nMoveCount].score = g_arrPosValue[i][j]。 } } } // 為了提高剪枝效率 ,對走法隊(duì)列進(jìn)行 (從大到小的 )排序 MergeSort_Desc( m_MoveList[nPly], m_nMoveCount )。 return m_nMoveCount。 // 返回合法走法的個數(shù) } 搜索算法 及增強(qiáng) 傳統(tǒng) AlphaBeta 算法介紹 在極大極小樹搜索的過程中，實(shí)際相當(dāng)一部分結(jié)點(diǎn)的搜索并不會影響最終搜索樹的值， Bruno 在 1963 年首先提出了 AlphaBeta 算法， 1975 年 Knuth 和 Moore 給出了 AlphaBeta 的數(shù)學(xué)正確性證明。 AlphaBeta 算法通過下界（ Alpha）上界（ Beta）對搜索樹值的最終范圍進(jìn)行了劃定，當(dāng)某些子樹其值被證明會在上述界限之外，無法影響整顆樹的值時，便可進(jìn)行剪枝 [5]。 AlphaBeta 剪枝算法的效率與子結(jié)點(diǎn)擴(kuò)展的先后順序相關(guān)，在最理想情況下，其生成的結(jié)點(diǎn)數(shù)目為： ND=2BD/21（ D為偶數(shù)） ND=2B（ D+1） /2+B(D1)/21 (D 為奇數(shù) ) 其中， B為 Branch Factor， D 為深度 由于不使用 AlphaBeta 剪枝算法時， ND=BD，所以最理想 情況下 AlphaBeta 算法搜索深度為 D 的結(jié)點(diǎn)數(shù)僅相當(dāng)于不使用 AlphaBeta 時搜索深度為 D/2 的結(jié)點(diǎn)數(shù)。但在最壞的情況下， AlphaBeta 算法產(chǎn)生的結(jié)點(diǎn)數(shù)與極大極小算法完全一樣 [9]！ 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 9 頁 下圖 是 以 NegaMax 形式（每層之間更改 Alpha,Beta 值符號，使 Alpha 剪枝在代碼中也簡化成 Beta 剪枝的形式表現(xiàn)出來）表現(xiàn)的 AlphaBeta 算法偽代碼 [7]： int AlphaBeta( 局面 p。 int α, int β ) { // 計算局面 p的的極大極小值 int a, t, i。 生 成局面 p的后繼局面 p1, p2, ..., pw。 if( w == 0 ) return ( Evalutate(p) )。 // 葉結(jié)點(diǎn)返回估值 a = α。 for( i = 1。 i = w。 i++ ) { t = AlpahBeta( pi, β, a )。 // 遞歸調(diào)用 .注意返回值取負(fù) a = max( a, t )。 if( a = β ) return ( a )。 // (Beta)剪枝 } return ( a )。 } 圖 NegaMax形式的 AlphaBeta類 C偽代碼 下圖 AlphaBeta剪枝實(shí)例圖： 圖 AlphaBeta剪枝實(shí)例圖 在上圖中，最左邊的分枝先以初始窗口（ ∞ ,∞）進(jìn)行搜索。完成對 D的 左子結(jié) 點(diǎn)估值后， D的估值至少為 6，故以窗口（ ∞ ,6）對 D中間子 結(jié) 點(diǎn)進(jìn)行搜索。在節(jié)點(diǎn) E， Alpha已經(jīng)被更新為 6了（因?yàn)?對結(jié)點(diǎn) B的左子 結(jié) 點(diǎn) D的遍歷 已經(jīng)完成 ）。因 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) 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 10 頁 此 B的右子 結(jié) 點(diǎn) E的搜索窗口為（ ∞ ,6）。在對 E的左子 結(jié) 點(diǎn)完成遍歷后， Alpha值被調(diào)整為新值 7（ beta），因此 可以 對 E的右子 結(jié) 點(diǎn) L進(jìn)行（ Beta） 剪枝。我們也可以將這個過程從負(fù)極大值觀點(diǎn)上看成是確定 min(6,max(7 ,L))或者是max(6,max(7,L))的值。不管 L的值是多少，我們獲得的值總是 6， 或者用負(fù)極大值形式來說 6。同理，可以分析出對 C的右子樹進(jìn)行 類似的 Alpha剪枝。 NegaScout 算法及 Minimal Window Minimal Window：是指窗口為 0的 Alpha、 Beta限制范圍，譬如 [N,N+1]，因?yàn)椴豢赡艽嬖谝粋€整數(shù)既 大于 N又小于 N+1，所以這個范圍內(nèi)不可能存在真實(shí)結(jié)果。同時因 Minimal Window的 Alpha、 Beta限制范圍最小，所以產(chǎn)生剪枝的概率也比正常的搜索窗口的大 [10]。 采用 Minimal Window的意義：如果搜索一個子結(jié)點(diǎn)的時候，當(dāng)其值大于 Beta，即產(chǎn)生 Beta剪枝的概率比較大的時候，我們可以先用 [Beta1,Beta]進(jìn)行搜索，如果搜索的結(jié)果 Fail High，即說明了結(jié)果 =Beta，這時我們可以立刻進(jìn)行 Beta剪枝，相反如果結(jié)點(diǎn) Fail Low，則說明結(jié)果不可能大于 Beta，也就是說無 法剪枝，那么我們剛才用 [Beta1,Beta]的 MinimalWindow就無法得到真實(shí)結(jié)果，所以我們必須重新用 [Alpha,Beta]進(jìn)行搜索。雖然當(dāng)無法 Beta Cutoff需要重新搜索的時候，實(shí)際比原來多出了 Minimal Window [Beta1,Beta]的搜索過程，但是由于 Minimal Window內(nèi)的子樹產(chǎn)生剪枝的概率比較大，所以實(shí)際