【正文】 第 11 頁 for( i = 1。 置換表（ Transposition Table） 在一棵搜索樹中，不 少結(jié)點之間雖然是經(jīng)過不同的路徑到達的，但其狀態(tài)是完全一致的。一般只有 Exact 類型，才可作為當前結(jié)點的準確值存入 Transposition Talbe，但 Fail High(=Beta)、 Fail Low(=Alpha)所對應(yīng)的邊界值仍可幫助我們作進一步的剪枝，所以我們在 Transposition Table用字段 entry_type表示 類型，其中 Exact類型為準確值，其余的是表示值的范圍 [12]。 if( depth 0 ) { i = IsGameOver( CurPosition, depth )。 a = alpha。 /* 重新搜索 */ eval_is_exact = 1。m_MoveList[depth][bestmove], depth )。兩個沖四看成一個活四。 （ 2）程序可以自動隱藏，還能方便、快速地呼出。如發(fā)送及顯示聊天內(nèi)容（包括文字聊天消息和語音聊天消息）、對和棋，悔棋，認輸響應(yīng)后進行善后處理等等。 最后棋盤邊上的坐標數(shù)值（ 11 AO）和棋子上在數(shù)值 [1， 225]也是在 OnPaint 函數(shù)中畫出來的。該頁面支持拖放功能，用戶可以將一個或多個音樂文件（格式為 MP WAV 或 WMV）直接拖放到頁面上進行 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 21 頁 播放。 圖 播放列表對話框 設(shè)置對話框 現(xiàn)在每一款 軟 件都有“設(shè)置”對話框。 // 落子坐標 STONEPOS stonePos。 圖 請求和棋 同意和棋消息 —— FM_AGREE_DRAW 表明對方接受了玩家的和棋請求（如圖 所示），除 uID 成員外其余成員皆無效。 對方姓名消息 —— FM_NAME_INFO 用來獲取對方玩家的姓名， szText 表示對方的姓名， stonePos 成員無效。 同時，通過自己平時下五 子棋不斷總結(jié)經(jīng)驗教訓(xùn)，希望在下一版本中能寫出更合理、更快速的估值函數(shù)來。 編輯框聊天消息 —— FM_EDIT_CHAT 表明對方在組合框的編輯框輸入一條聊天信息并發(fā)送， szText 表示對方的輸入的信息內(nèi)容， stonePos 成員無效。接到這個消息后，整個界面將恢復(fù)發(fā)送悔棋請求前的狀態(tài)。 智能 五子棋程序也模仿 Windows 系統(tǒng)實現(xiàn)了自己的 消息機制，主要為網(wǎng)絡(luò)對弈服務(wù)，以響應(yīng)多種多樣的網(wǎng)絡(luò)消息（ 如 圖 ）?！?+”之下的按鈕用來保存 /打開播放列表文件 （ FPL格式）。其中長度信息欄（格式為 MM:SS） 隨著歌曲的播放進度而實時更新（圖上的 4:29 表明這首歌長度為 4 分 29 秒，而 4:21是說剩余時間為 4分 21秒）。程序中正是用雙緩沖技術(shù)解決閃爍問題的 。 （ 2） CChessBoard（棋盤類） 棋盤類自然是處理用戶與棋盤的交互消息。在 Windows大行其道的今天，任何一款成功的商業(yè)軟件都在界面設(shè)計上 都 下足了功夫，因為這是吸引用戶興趣的第一道門檻。最基本的棋型優(yōu)先順序為：五連 活四 沖四 活三 眠三 活二 眠二。m_MoveList[depth][i], depth )。amp。 ++i ) { // 取所有走法的歷史得分 m_MoveList[depth][i].score = GetHistoryScore( amp。 在搜索的過程中，每當找到一個好的走法，就將與該走法相對應(yīng)的歷史得分作一個增量，一個多次被搜索并確認為好的走法的歷史紀錄 就會較高，當搜索中間 結(jié)點時，將走法根據(jù)其歷史得分排列順序，以獲得較佳的排列順序。 Transposition Table 是一種空間換取時間的思想。 // (Beta)剪枝 b = a + 1。 生成局面 p的后繼局面 p1, p2, ..., pw。 // (Beta)剪枝 } return ( a )。 // 使用位置價值表評估當前走法的價值 m_MoveList[nPly][++m_nMoveCount].score = g_arrPosValue[i][j]。 // x, y 是棋盤坐標值，取值范圍 [0,14] } STONEPOS。 界面生成 涉及 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ā)送及整點報時；自動窗口閃爍；讀寫注冊表；簡單多線程搜索音樂等等。 Pentium174。 甲： 1 乙： 2 乙： 3 甲： 4 乙： 8 乙： 9 甲： 5 乙： 10 乙： 11 甲： 6 甲： 7 乙： 12 乙： 13 乙： 14 乙： 15 ?? ?? ?? 圖 博弈樹的例子 圖 博弈樹的例子 甲： 1 2 3 M+1 ?? 圖 乙： 2 AlphaBeta剪枝實例圖 乙： 1 K+1 K+2 K+N ?? 圖 乙方面對的局勢 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 3 頁 五子棋基本知識介紹 五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。 本文以計算機五子棋博弈系統(tǒng)作為研究課題。主要是考慮到當前網(wǎng)絡(luò)上流傳的五子棋游戲功能并不盡善盡美，其中最主要的問題就是人機對戰(zhàn)和網(wǎng)絡(luò)對戰(zhàn)沒有結(jié)合在一起實現(xiàn)；同時還存在游戲界面簡單、計算機智能水平不足、也沒有諸如保存棋譜和背景音樂等極有用的附加功能，所以不能吸引玩家興趣?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“ Renju”，英文稱之為“ Gobang”或“ FIR”（ Five in a Row 的縮寫），亦有“連五子” 、 “五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。 2及以上處理器， 128M 以上內(nèi)存 ? Microsoft174。 網(wǎng)絡(luò) 連接 使用的 WinSock 版本號為 。 （ 2）用數(shù)字“ 0”和“ 1”來表示不同顏色的棋子，其中黑色棋子用“ 0”表示，白色棋子用“ 1”表示。 } } } // 為了提高剪枝效率 ,對走法隊列進行 (從大到小的 )排序 MergeSort_Desc( m_MoveList[nPly], m_nMoveCount )。 } 圖 NegaMax形式的 AlphaBeta類 C偽代碼 下圖 AlphaBeta剪枝實例圖： 圖 AlphaBeta剪枝實例圖 在上圖中，最左邊的分枝先以初始窗口（ ∞ ,∞）進行搜索。 if( w == 0 ) return ( Evalutate(p) )。 // 設(shè)置新的空窗 } return ( a )。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 12 頁 Transposition Table 結(jié)合 AlphaBeta 搜索：在 AlphaBeta 搜索的過程中，一個結(jié) 點會出現(xiàn)以下三種情況之一： （ 1） Fail High，結(jié)點值至少 =Beta，但不知道其具體值。 本 系 統(tǒng) 在實 現(xiàn) 時使 用 NegaScout 算法 并 配 合 上面 介 紹過 的 置換 表（ Transposition Table） 和歷史啟發(fā)（ History Heuristic） 增強 ，核心搜索算法源代碼 如下 [613]： 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 13 頁 // 主調(diào)例程必須將 alpha設(shè)為 COMP_LOSS,將 beta設(shè)為 COMP_WIN int CNegaScout_TT_HH::NegaScout_MAX( int depth, int alpha, int beta ) { // 用于偶數(shù)層 (從算起 ) int count, i。m_MoveList[depth][i] )。 t beta amp。 return a。具體的過程如下：對棋盤上所有棋子在水平、垂直、左斜和右斜方向上進行分析。 智能 五子棋界面設(shè)計思想主要有如下幾點： （ 1）盡量少用模態(tài)對話框，大量使用非模態(tài)對話框。包括清 空 棋盤、設(shè)置 游戲模式（單機 或 網(wǎng)絡(luò)）、畫棋子，坐標，數(shù)字，跟隨框，十字形提示、響應(yīng)右鍵彈出菜單消息等等。棋盤和棋子相對來說是 繪制比較容易， 直接位圖 拷貝 就 可以 了。標題和路徑信息欄可能會遇到文件名過長而省略的情況（見圖 路徑欄后面的省略號），如果 文字 有省略，用戶只需將鼠標移動到相應(yīng)的信息欄，程序即會在它們的上面用 ToolTip 控件彈出包含完整信息的提示。 這個對話框當然 也 少不了支持拖放功能 的 ，而且支持更加強大的拖放功能。 消息機制的架構(gòu) 當繼承自 CAsyncSocket 的套接字類 CFiveSocket 收到消息時，會觸發(fā)CFiveSocket::OnReceive 事件，這個事件里調(diào)用 CChessBoard::Receive， 該函數(shù)開始按照自定義的消息格式接收套接字發(fā)送的數(shù)據(jù)，并對不同的消息類型進行分發(fā)處理 [3]。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 25 頁 圖 拒絕悔棋 請求和棋消息 —— FM_REQUEST_DRAW 表明對方請求和棋，除 uID 成員外其余成員皆無效。接到這個信息后，會將對方聊天的內(nèi)容顯示在主對話框的聊天記錄窗口內(nèi)。此外， 將來還 可以考慮加入開局庫（ Opening Book） 和殘局庫（ Endgame Database），來進一步加 快 程序的運行速度。接到這個信息后，會將對方選擇了列表框某項文本內(nèi)容顯示在主對話框的聊天記錄窗口內(nèi)，同時如果 szText[1]為 1，系統(tǒng)將用聲音讀出該文本的內(nèi)容，這里所用到的聲音 WAV 文件是從 游戲 的斗地主目錄里 拷貝 過來的。另外，在發(fā)送這個消息之后，主界面上的某些元素將暫時不響應(yīng)用戶的操作。 各種消息說明 網(wǎng)絡(luò)間傳遞的消息，都遵循以下一個結(jié)構(gòu)體的形式： 網(wǎng)絡(luò)數(shù)據(jù) CFiveSocket CFiveSocket::OnReceive CChessBoard::Receive 對各種消息分發(fā)處理 調(diào)用 CFiveSocket::Send 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 24 頁 // 摘自 typedef struct _tagFiveMsg { // 消息 ID USHORT uID。甚至是多個快捷方式也是支持的 [20]。剩下的一些 Buttons、Check box、 Slider Volume Control就不 在此 詳細介紹 了。特別是指示框：在 OnMouseMove函數(shù)中捕獲鼠標當前屏幕坐標值 x, y，程序通過宏 DATA_X(x)和 DATA_Y(y)將當前鼠標 位置轉(zhuǎn) 換為棋盤坐標值 x1， y1（ [0,14]數(shù)值），然后根據(jù)棋盤坐標值確定指示框的十字交叉點的屏幕坐標值（通過 CUR_X(x1)和 CUR_Y(y1)宏 ） ，從而進一步確定提示框四個角的坐標值，最后根據(jù)這些坐標值畫出 8 條紅線（長度為 4Pixels，寬度為 1Pixel）。 （ 3） CTabChatDlg（聊天頁面類） 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 18 頁 這個類主要負責(zé)處理網(wǎng)絡(luò)對戰(zhàn)過程中來自雙方的消息。對用戶來說，這是非常不 友好的功能，因為太多數(shù)信息都不是特別地緊急，用戶完全有可能選擇忽略或者延后處理它們。如果已五連，直接返回極值 （極值并不是真正數(shù)學(xué)意義上的無窮大 /小，在本系統(tǒng)中絕對值大于 8000 的數(shù)值看成是極值，下同） 。 /* 設(shè)置新 的空 窗 */ } if( bestmove != 1 ) //